7、树和二叉树
7.1、树的基本概念
概念：
空树：结点数为0的数
非空树的特性：
- 有且仅有一个根结点
- 没有后继的结点称为”叶子结点”（或终端结点）
- 有有后继的结点称为”分支结点”（或非终端结点）
- 除了根结点外，每个结点都有且仅有一个前驱
- 每个结点可以有0个或者多个后继
属性描述：
- 结点的层次（深度）：从上往下数
- 结点的高度：从下往上数
- 数的高度（深度）：总共有多少层
- 结点的度：有几个孩子（分支）
- 树的度：各结点度的最大值
有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能交换
无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以交换
森林：是m（m>=0）棵互不相交的树的集合
树的常考性质1
结点数 = 总度数 + 1
树的常考性质2
树的度：各个结点的度的最大值 m叉树：每个结点最多只能有m个孩子的树
树的常考性质3
度为m的树第i层至多有\(m^{i-1}\)个结点（i>=1)
树的常考性质4
高度为h的m叉树至多有\(\frac{m^i-1}{m-1}\)个结点
总共有：$m^0 + m^1 + m^2 + … + m^i $
树的常考性质5
高度为h的m叉树至少有h个结点
高度为h，度为m的树至少有\(h+m-1\)个结点
树的常考性质6
具有n个结点的m叉树的最小高度为$\left \lceil log_n(n(m-1)+1) \right \rceil $
答：最小高度就所有结点有m个孩子
\(\frac{m^{h-1}-1}{m-1} < n <= \frac{m^h-1}{m-1}\)
\(m^{h-1} < n(m-1) + 1 <= m^h <\)
\(h-1 < log_m(n(m-1)+1) <= h\)
\(h_{min} = \left \lceil log_n(n(m-1)+1) \right \rceil\)
7.2、二叉树
二叉树是n（n >= 0）个结点的有限集合
- 空二叉树，即n=0
- 有一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树分别又是一颗二叉树
特点：
- 每个结点至多有两颗子树，
- 左右子树不能颠倒（二叉树是有序数）
几个特殊二叉树
-
满二叉树。一颗高度为h，且含有\(2^h – 1\)个结点的二叉树
特点：
- 只有最后一层有叶子结点
- 不存在度为1的结点
- 按层次从1开始编号，结点为i的左孩子为\(2i\)，右孩子为\(2i+1\)，结点为i的父节点为$\left \lfloor \frac{i}{2} \right \rfloor $
-
完全二叉树。当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。
特点：
- 还有最后两层可能出现叶子结点
- 最多只有一个度为1的结点
- 按层次从1开始编号，结点为i的左孩子为\(2i\)，右孩子为\(2i+1\)，结点为i的父节点为$\left \lfloor \frac{i}{2} \right \rfloor $
- \(i <=\left \lfloor \frac{n}{2} \right \rfloor\)为分支结点，\(i > \left \lfloor \frac{n}{2} \right \rfloor\)为叶子结点
-
二叉排序树。一颗二叉树或者空二叉树，或者是具有如下性质的二叉树
- 左子树的上所有结点的关键字均小于根结点的关键字
- 右子树的上所有结点的关键字均大于根结点的关键字
- 左子树和右子树又各是一颗二叉排序树
-
平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1
二叉树的常见考点
-
设非空二叉树中度为0、1和2的结点数分别为\(n_0、n_1、n_2\)，则\(n_0 = n_2+1\)
解答：
设总的结点数为n
\(n = n_0 + n_1 + n_2\)
\(n = n_1 + 2n_2 + 1\)
所以：\(n_0 = n_2+1\)
-
具有n个（n>0）结点的完全二叉树的高度h为$\left \lceil log_2(n+1) \right \rceil \(或者\)\left \lfloor log_2(n) \right \rfloor + 1$
推导：$\left \lceil log_2(n+1) \right \rceil $
n个结点：h层最多为\(2^h-1\)，h-1层最多有\(2^{h-1}-1\)
所以：\(2^{h-1}-1<n<=2^h-1\)
所以：$h = \left \lceil log_2(n+1) \right \rceil $
推导：\(\left \lfloor log_2(n) \right \rfloor + 1\)
n个结点：h+1层至少有\(2^h\)个结点；h层至少有有\(2^{h-1}\)个结点
所以：\(2^{h-1}<=n<2^h\)
所以：\(\left \lfloor log_2(n) \right \rfloor + 1\)
-
对于完全二叉树，可以由的结点数n推出度为0、1和2的结点个数\(n_0、n_1、n_2\)
完全二叉树最多只有一个度为1的结点，
即：\(n_1 = 0或1\)
由于\(n_0 = n_2+1\) ==> \(n_0 + n_2\)为奇数
所以：
若完全二叉树有\(2k\)个（偶数）个结点，则必有\(n_1 = 1;n_0 = k;n_2 = k-1\)
若完全二叉树有\(2k-1\)个（奇数）个结点，则必有\(n_1 = 0;n_0 = k ;n_2 = k-1\)
原文地址：http://www.cnblogs.com/shuisanya/p/16849409.html
