数据结构二叉树知识点总结
- 格式：pdf
- 大小：63.60 KB
- 文档页数：1
数据结构⼆叉树知识点总结
术语
1. 节点的度：⼀个节点含有的⼦树的个数称为该节点的度；
2. 叶节点或终端节点：度为零的节点；
3. ⾮终端节点或分⽀节点：度不为零的节点；
4. ⽗亲节点或⽗节点：若⼀个节点含有⼦节点，则这个节点称为其⼦节点的⽗节点；
5. 兄弟节点：具有相同⽗节点的节点互称为兄弟节点；
6. 节点的层次：从根开始定义起，根为第1层，根的⼦节点为第2层，以此类推；
7. 树的⾼度或深度：树中节点的最⼤层次；
8. 堂兄弟节点：⽗节点在同⼀层的节点互为堂兄弟；
9. 节点的祖先：从根到该节点所经分⽀上的所有节点；
10. 孙：以某节点为根的⼦树中任⼀节点都称为该节点的⼦孙。
11. 森林：由m（m>=0）棵互不相交的树的集合称为森林；
12. 满⼆叉树：⼀棵深度为k，且有2^k-1 (2的k次⽅减⼀)个节点称之为满⼆叉树
13. 完全⼆叉树：完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从1⾄n的结点⼀⼀对应时称之为完全⼆叉树。叶节点只能出现在最下层和次下层，并且最下⾯⼀层的结点都集中在该层最左边的若⼲位置的⼆叉树
⼆叉树的性质
1.在⾮空⼆叉树中，第i层的结点总数不超过2^(i-1),i>=1；
2.深度为h的⼆叉树最多有2^h-1个结点(h>=1)，最少有h个结点；
3.对于任意⼀棵⼆叉树，如果其叶结点数为N0，⽽度数为2的结点总数为N2，则N0=N2+1；
4.具有n个结点的完全⼆叉树的深度为K =[log2n」+1(取下整数)
5.有N个结点的完全⼆叉树各结点如果⽤顺序⽅式存储，则结点之间有如下关系： 若I为结点编号则 如果I>1，则其⽗结点的编号为I/2；
6.完全⼆叉树，如果2*I<=N，则其左⼉⼦（即左⼦树的根结点）的编号为2*I；若2*I>N，则⽆左⼉⼦； 如果2*I+1<=N，则其右⼉⼦的结点编号为2*I+1；若2*I+1>N，则⽆右⼉⼦。7.给定N个节点，能构成h(N)种不同的⼆叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
8.设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i
⼆叉树的遍历三种⽅式，如下：
（1）前序遍历（DLR），⾸先访问根结点，然后遍历左⼦树，最后遍历右⼦树。简记根-左-右。
（2）中序遍历（LDR），⾸先遍历左⼦树，然后访问根结点，最后遍历右⼦树。简记左-根-右。
（3）后序遍历（LRD），⾸先遍历左⼦树，然后遍历右⼦树，最后访问根结点。简记左-右-根。
