罗列术语
祖先 – 子孙, 双亲 – 孩子, 兄弟(同一个双亲) – 堂兄弟(同一层)。
树的度 = max{结点的度},分支结点 – 叶结点,层次,高度(自底向上)= 深度(自顶向下)。
有序树(子树间的相对位置不可变)- 无序树
路径(结点ai 到 ak所经过的序列 – 包括ai,ak), 路径长度(ai到ak边的个数)
森林 (n(n>=0)个树组成)
树性质(2个):
- 结点数 = 边数 + 1 (根结点没有双亲)
- 具有 n 个结点的 m 叉树的最小高度 h = ⌈logm (n(m-1)+1)⌉ = ⌊logm (n(m-1))⌋ + 1
阿Q:还有一些最多结点就不写了,写了也不看。
二叉树
阿Q注:二叉树不是树的特殊情况,也不是度为2的有序树。(因为二叉树的左右位置是一直都存在的,不会因为没有子树而抛弃。而树的左右是子树间的相对位置,没有子树就没有对照了哦~) 但是可以说二叉树是有序树(左右严格区分)。
二叉树性质(除树性质外 1个):
- n0(度为0的结点) = n2(度为2的结点) + 1 (由结点数 = 边数 + 1推的)
特殊二叉树
满二叉树
每一层都塞满了,那么孩子和双亲结点编号关系如下:
对于编号为 i 的结点(i>1), 其双亲结点编号为 ⌊i/2⌋;
若有左孩子,则编号为 2i,若有右孩子,编号为 2i + 1。
完全二叉树
与满二叉树类似,只是最后一层没填满,但是仍然严格按照从左到右有结点。(编号连续)
n 个结点的二叉树特点:
- i <= ⌊n / 2⌋,则结点 i 为分支结点,否则为叶结点。
- n 为 奇数,每个分支结点都有俩孩子,n 为偶数,编号最大的分支结点有左孩子,无右孩子。
- 完全二叉树编号关系(和满二叉树是类似的):
阿Q注:此外还有二叉排序树(关键字:左 < 根 < 右)、平衡二叉树(左右树深度差不超过1)
(统考不涉及,但有时间去看看)
两道练习:
评论