数据结构重读 – 二叉树

1、二叉树(Binary Tree)是一种特殊的树形结构:每个结点至多有两棵子树,即二叉树中不存在度大于2的结点。

2、二叉树的子树有左右之分,次序不能任意颠倒。

3、性质1:二叉树的第i层上至多有2^(i-1)个结点,i从1下标开始。所有

4、性质2:深度为k的二叉树至多有2^k -1个结点,k也是从1下标开始。

5、性质3:对于任何一棵二叉树,如果终端结点数为n0,度为2的结点数为n2,则n0 = n2+1。这个很简单:

(1)设度为1的结点数为n1,则总结点数n = n0 + n1 + n2。
(2)根据先前的(任意树)上的公式:结点数量 = 所有结点度之和 + 1,即n = n0+ n1 + n2 = n1 + 2 n2 +1,两边消掉,有:

n0 = n2 + 1。

6、满二叉树:一棵深度为k,且有2^k -1个结点的二叉树。特点是每一层都是满的。

7、完全二叉树不是满二叉树!它的结点可以不足2^k – 1,但是深度必须和对应的满二叉树对应,已经有的结点从1~k必须和同深度的满二叉树一一对应(即在满二叉树的第k层从右向左去掉若干个结点,至少保留一个结点)。

8、满二叉树是完全二叉树,但完全二叉树不是满二叉树!

9、性质4:具有n个结点的完全二叉树,深度为[ log(n)] + 1,其中[]是向下取整。

10、性质5:如果对一棵有n个结点的完全二叉树的结点按层次编号,每层从左到右,层次从上到下。假设根存储在1号单元(设下标从1开始),对任意结点i,
(1) 如果i=1,结点i是二叉树的根,无双亲。i>1,则双亲PARENT(i)是结点[i/2],还是向下取整。
(2) 如果2i>n,则结点无左孩子,否则左孩子是2i。
(3)如果2i+1>n,无右孩子,否则右孩子是2i+1。

如果下标从0开始,上述结论变成:

(1)双亲是i/2-1
(2)左孩子是2i+1,>n无左孩子。
(3)右孩子是2i+2,>n无右孩子。

11、二叉树的遍历,先序、中序、后序遍历分别对应着表达式:前缀表示(又叫波兰式)、中缀表示和后缀表示(又叫逆波兰式)。

二叉树的顺序存储

利用上述性质5,可以把任何一个二叉树映射到完全二叉树上,从而映射到数组上。当然这个数组的中间某些位置可能是“空的”。

代码:包含创建、先、中后序遍历(递归版本)

下面来说说非递归的:

首先是先序非递归,很简单,就是先visit,然后右压栈,然后左压栈。

下面讨论下非递归的版本:

首先中序非递归遍历,略复杂一点:
(1)先root入栈
(2)对所有左子树入栈,直到到达左下角。
(3)依次出栈,对每个出栈元素先visit,然后入右子树,也是循环,直到右下角。

后序非递归:比较复杂,还没写出来。

层序遍历,需要借助队列,比较简单,代码如下:

二叉树的链式存储

基础部分不用多解释了。

然后重点关注下非递归实现后序遍历

算法分为三个部分:

(1)大循环,条件ptr!=NULL或者栈非空
(2)循环内1:压所有左子树,直到左下角
(3)循环内2:对于stack的top结点,如果是第一次visit(tag==false),将它置为tag==true,然后ptr设为右子树。如果是第二次,说明右子树已经访问过了,直接访问自身,然后设置为NULL。

 二叉树求深度

采用递归的方法,max(左子树深度, 右子树深度) +1

 

 

 

Leave a Reply

Your email address will not be published.