本文共 952 字,大约阅读时间需要 3 分钟。
树是一种可以递归定义的数据结构
树是由n个节点组成的集合:<1> 二叉树: 度不超过2的树,每个节点最多有两个孩子节点,两个孩子节点被区分为左孩子节点和右孩子节点
<2> 满二叉树: 一个二叉树,如果每一个层的节点数都达到最大值,则这个二叉树就是满二叉树 <3> 完全二叉树:叶结点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边若干位置的二叉树二叉有两种储存方法: 链式存储方式、顺序存储方式,链式储存方法后面会讲,今天先来讲讲顺序储存方法。
以这棵完全二叉树为例: 那现在问题来了,我知道一个节点,要怎么去找该节点的父节点和子节点呢? 首先,先按层级关系将节点储存在列表中:[A, B, C, D, E, F, G, H, I, J, K]
,索引或者说下标分别为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
。 比如现在我们知道节点E,要去找出它的父节点和子节点: E
的下标为4
,E
的父节点B
的下标为1
,E
左孩子J
的下标为9
,F
右孩子K
的下标为10
这里就直接给出规律了(i是父亲节点的下标): 父亲节点和左孩子节点的编号下标的关系: i——>2i+1 父亲节点和右孩子节点的编号下标的关系: i——>2i+2 子节点找父节点: (i-1)//2 i是子节点下标 //为整除 转载地址:http://qfiwi.baihongyu.com/