二叉树

二叉树的定义

1.本身是有序树

2.树中包含的各个结点的度不超过2,即只能是0、1、2


二叉树的性质

1.二叉树中,第 i 层最多有 2^(i-1) 个结点。

找规律,一个节点最多延申两个结点,那必定是2*2*2*……

2.如果二叉树的深度为 K,那么此二叉树最多有 2^K – 1 个结点。

同上因为根节点永远只有一个必定不能成双

3.二叉树中,终端结点数(叶子结点数)为 n0,度为 2 的结点数为 n2,则 n0=n2+1。

性质 3 的计算方法为:对于一个二叉树来说,除了度为 0 的叶子结点和度为 2 的结点,剩下的就是度为 1 的结点(设为 n1),那么总结点 n=n0+n1+n2。
同时,对于每一个结点来说都是由其父结点分支表示的,假设树中分枝数为 B,那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的,即 B=n1+2*n2。所以,n 用另外一种方式表示为 n=n1+2*n2+1。
两种方式得到的 n 值组成一个方程组,就可以得出 n0=n2+1。


满二叉树

二叉树中除了叶子节点每个结点的度数都为2,则此二叉树为满二叉树

满二叉树除了满足普通二叉树的性质,还具有以下性质:

  1. 满二叉树中第 i 层的节点数为 2^(i-1) 个。

必定是最多的情况

2.深度为 k 的满二叉树必有 2k-1 个节点 ,叶子数为 2k-1

同上,必定是最多的情况

3.满二叉树中不存在度为 1 的节点,每一个分支点中都两棵深度相同的子树,且叶子节点都在最底层。

4.具有 n 个节点的满二叉树的深度为 log2(n+1)。


完全二叉树

如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布,则此二叉树被称为完全二叉树。

如图 a) 所示是一棵完全二叉树,图 b) 由于最后一层的节点没有按照从左向右分布,因此只能算作是普通的二叉树。

完全二叉树除了具有普通二叉树的性质,它自身也具有一些独特的性质,

比如说,n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。
⌊log2n⌋ 表示取小于 log2n 的最大整数。例如,⌊log24⌋ = 2,而 ⌊log25⌋ 结果也是 2。

对于任意一个完全二叉树来说,如果将含有的结点按照层次从左到右依次标号(如图 a)),对于任意一个结点 i ,完全二叉树还有以下几个结论成立:

当 i>1 时,父亲结点为结点 [i/2] 。(i=1 时,表示的是根结点,无父亲结点)
如果 2*i>n(总结点的个数) ,则结点 i 肯定没有左孩子(为叶子结点);否则其左孩子是结点 2*i 。
如果 2*i+1>n ,则结点 i 肯定没有右孩子;否则右孩子是结点 2*i+1 。


二叉树的顺序存储结构

最好是在遇到完全二叉树或者满二叉树的时候使用

其它情况下都会变得很麻烦

像这样,按照从左到右的顺序把元素填到数组里

就相当于记忆了这棵树的排列

也是为什么建议在完全二叉树或者满二叉树的时候使用

遇到不齐的排列时咋办呢

补上0或者其它不会混淆的符号就可以了

遇上分支比较多深度比较大的树时,这样存储就会称为巨大的负担

由于基本不用所以这里就不贴实现了


二叉树的链式存储结构

通过指针我们可以把它转为下面这样的形式

结点主要由三部分构成

Lchild 指向左孩子结点的指针

data 存放数据元素

Rchild 指向右孩子结点的指针

在某些场景中可能需要去求这个结点的父节点

可以多添加一个指针用来指向父节点

这样的链表通常被称为三叉链表


二叉树的遍历

按照一定的次序去访问二叉树中的所有结点且每个节点仅被访问一次

是二叉树的基本运算,是所有其它运算实现的基础

在这里我们主要讲四种遍历的算法(除最后一种层次以外可以递归也可以用栈来实现)

先序遍历

  1. 访问根节点
  2. 访问当前节点的左子树
  3. 若当前节点无左子树则访问右子树

中序遍历

  1. 访问当前节点的左子树
  2. 访问根节点
  3. 访问当前节点的右子树

后序遍历

从根节点出发,依次遍历各节点的左右子树

直到当前节点左右子树遍历完成后,才访问该节点元素

层次遍历

通过使用队列的数据结构,从树的根结点开始,依次将其左孩子和右孩子入队

而后每次队列中一个结点出队,都将其左孩子和右孩子入队,直到树中所有结点都出队

出队结点的先后顺序就是层次遍历的最终结果

对于图中这棵二叉树,用上面四种算法遍历的顺序分别为

先序:1245367

中序:4251637

后序:4526731

层次:1234567


线索二叉树

二叉树如果用二叉链表来存储的话

每个节点有两个指针域,那么总共就有2n个指针域

扣掉根节点的话只有n-1个指针域有指向,剩下的n+1个都是空的

遍历二叉树干的事情就是把这些空指针域利用起来

用来存放指向节点前驱节点和后驱节点的地址

这样的指针就叫做线索

而不同遍历次序得到的线索二叉树是不同的

通过不同遍历方式把二叉树变成线索二叉树的过程就叫做线索化

目的是为了提高遍历的效率,节约空间,同时方便查找节点的前驱和后继

线索化二叉树

大致的过程其实都差不多

先遍历,在遍历的同时检查当前节点的左右指针是否为空

如果为空的话,把它改为指向前驱节点或者后继节点

具体算法待补充

发表评论

您的电子邮箱地址不会被公开。