数据结构 认识二叉树

数据结构 认识二叉树

越行勤 718 2021-07-04

在离散的学习中，图论有探讨过树（在这里我们讨论的为有向树），在计算机领域中树型结构是非常重要的非线性结构，树型结构在客观事件普遍存在，比如族谱哇，各种社会组织的结构等。本章重点介绍 树，二叉树 ，森林，并且研究ta们的性质和相互转换关系。

认识树 Tree

树的定义

树，从形态上就是一颗倒着的树。

树

树 ： n个节点的有限集合 (n>=0)。这里要和前面的学习的广义表区别开来。

广义表是线性表)的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。

也就是构成广义表的元素可以是一个广义表（套娃结构）。

广义表的长度：广义表中所包含的数据元素的个数，即为 最大括号中的逗号数加1。

广义表的深度：是指广义表展开后所含括号的层数，即为 每个元素的括号匹配数加1的最大值。

虽说广义表也看似有和树一样的结构，但是广义表在图上的每一个节点有可能树一个元素，也有可能是一个广义表。对于树来说，是元素有层次结构的组合在一起，并且有前驱后继之分，一个结点前驱只能有一个。

空树： 树的元素个数为零的树 n=0

非空树: 元素个数不为0 n>0

  1. 任意的非空树，有且仅有一个根结点 (Root) ，根结点没有前驱

  2. 同时具有前驱结点和后继结点的结点叫做 分支节点

  3. 没有后继结点的结点叫做 叶子结点

  4. 结点的度 ，出度的个数（孩子节点的个数）。树的度为所有结点中的最大度数

  5. 当n>1时，除去根节点，我们有可以分成m>0个子树

    image-20210421220251424

  6. 祖先结点 ：从根结点到该节点所需要经历的所有结点

  7. 子孙结点：从该节点向下出发，可以到达的所有结点

  8. 孩子结点：该结点的直接后驱结点

  9. 双亲结点：该 结点的直接前驱结点

  10. 兄弟结点：该结点的双亲结点的其他孩子结点

  11. 堂兄弟结点：从该结点的双亲结点的兄弟节点的孩子结点

这里的描述和我们在家里的辈分的描述时大致一致的。

树的深度: 从根节点开始 ，根节点层次为第一层，其的孩子深度是第二次，...，以此类推，树的深度就是所有结点的最大层次。

二叉树

二叉树是树中最特殊的一种，也是我们要重点学习的一种。

  1. 二叉树要么没有根结点，是一棵空树。
  2. 二叉树要么由根结点、左子树。右子树组成，且左子树和右子树都是二叉树。
  3. 二叉树的左子树与右子树有顺序而言。

特殊二叉树

满二叉树：

每一层的结点个数都达到了当层能达到的最大结点数

完全二叉树：

除了最下面一层之外，其余层的结点个数都达到了当层能达到的最大结点数，且最下面一层只从左到右连续存在若干结点，而这些结点右边的结点全部不存在。

完全二叉树相比满二叉树来说，条件不是太严苛，只需最下面一层从左至右树 结点时连续的，也就是说不允 结点 空结点 结点 或者 空结点 结点 结点 这个样情况出现。倘若给完全二叉树每一个位置从左至右，从上到下编号， 结点序号一定是连续的才可被叫 完全二叉树。如下图，是一个完全二叉树。

完全二叉树

如下图，不是一个完全二叉树。

不是完全二叉树

二叉排序树：

一颗非空二叉树必须满足如下性质：

  1. 左子树上的所有结点的数字均小于根节点
  2. 右子树上的所有结点的数字均大于根节点
  3. 左右子树又分别是一颗二叉排序树

平衡二叉树

树上的任意结点的左子树和右子树的深度只差都不大于1. 如下图的二叉树

image-20210505145327512

如果不是一颗平衡二叉树，那么就会像毛毛虫一样

image-20210505145523138

我们在写程序的时候，经常使用 if else or if else if语句，其实这就可以看作一颗二叉树，通常希望判断条件可以和平衡二叉树一样，这执行目标语句的所经过的判断是最少的， 如果是毛毛虫一样，那么需要做很多判断。

如果一颗树即使平衡树又是二叉排序树，这就是排序平衡二叉树，排序平衡二叉树具有更好的搜索效率。 上面两图中，我们发现如果要找到70这个结点，图1只需经过三个结点，但是图2就需要经过7结点。

树的性质

学习树这个结构之前，我们最好先回忆一下离散的相关知识。

  1. 如果该树有 n个结点，那么一定有n-1条边 ，也就说 结点数一定比边数多1， 当然也可以这样说 结点数一定比总度数多1

二叉树的相关性质

  1. 二叉树的第i层 最多有 2i-1 结点
  2. 深度为 h的二叉树最多有 2h -1 结点
  3. 任意二叉树 叶子结点比分支结点多1

完全二叉树的专有性质

  1. 有n个结点的完全二叉树的深度为 [log2n ] +1 ([a]为取不超过a的最大整数符号 ) ，这里就是性质2的一个应用

  2. 给有n个结点完全二叉树每一个位置从左至右，从上到下编号，如下图

    完全二叉树

    对于任意结点 i

    • 除了i=1之外，结点 i的双亲为 结点[i/2]
    • 如果i*2大于 n，那么该结点没有左孩子，否则左孩子为结点2i
    • 同理，如果i*2 +1大于 n，那么该结点没有右孩子，否则该有孩子为 结点i*2 +1

    看下图能够更好的理解

    image-20210505155039853

存储二叉树

顺序结构

#define MaxSize 100
typedef TElemType SqBiTree[MaxSize];

SqBiTree bt;//声明二叉树

顺序存储也可以存储二叉树？是不是很差异，其实我们一切结构都可以转化成线性结构，换句话说，一切结构都起源线性结构。

使用顺序存储二叉树的结构，利用了我们前面探讨的二叉树的结构，给每一个位置编号。

完全二叉树

数组如下：

image-20210507212049163

这里我们不使用 array[0] ,这样为上图的编号能和数组中的编号对应。

如何找到结点的孩子和双亲？

  • 除了i=1之外，结点 i的双亲为 结点[i/2]
  • 如果i*2大于 n，那么该结点没有左孩子，否则左孩子为结点2i
  • 同理，如果i*2 +1大于 n，那么该结点没有右孩子，否则该有孩子为 结点i*2 +1

补充

当然这个最好是存储完全二叉树，如果存储非完全二叉树，为了能够完整的表达树中的结构，没有元素的地方不得不空下来，导致大量的空间浪费！

链式结构

链式结构，这是一般人看到二叉树的能想到的第一存储结构。为树的每一个结点设立一个结点，存储数据和左右孩子结点的指针就可以了。当然这是存储树的最基本的需要，我们在必要的时候添加存储信息。

遍历二叉树

遍历二叉树，我们有多种多样的顺序

![image-20210505155254609](https://halo-yxq-1302651434.cos.ap-beijing.myqcloud.com/halo%E5%8D%9A%E5%AE%A2/%E4%BA%8C%E5%8F%89%E6%A0%91/image-20210505155254609.png

我们规定遍历时候，必须先遍历子树，再遍历右子树，同时遍历子树采取同样的方法，这样我们可以得出四种遍历方式。遍历方式是一种递归定义！

对于下面遍历方式的命令，我更喜欢叫这些命名方式为先根，后根，和中根。这里序就是来形容根节点的。

下面遍历就以这棵树为例子

二叉树

先序遍历

根->左->右 NLR

遍历顺序为 A B D E C F G

我们再遍历完 A 结点之后，就该遍历 B这个结点，B这里是一个分支结点，也就说我们不能只看B是一个结点 ，眼界放宽，要把B D E 整体作为一个子树来看待，如果你遍历顺序为 A B C D E F G ,那这就不是先序遍历 而是 层次遍历。

image-20210505160818427

换句话说 ，A的左孩子，右孩子不单单是一个结点而是二叉树。

遍历完根节点A，我们就要遍历 A的左孩子，再遍历A左孩子的根节点为B，再遍历A左孩子B的左孩子，此时 B的左孩子为叶子结点 ，遍历D即可，当然为了后续的理解，此时我们给D补上两个空结点，

image-20210505162121469

对他进行先序遍历， 发现是 D 空 空 ，和直接遍历 D是一个效果。

此时我们就要遍历结点B的左孩子 ，那么该遍历B的右孩子E。

到这里，我们就完成对 A结点左孩子的遍历，现在继续采用根->左->右的顺序遍历A的孩子即可。

中序遍历

左->根->右 LNR

遍历顺序为 D B E A F C G

有了先序遍历的开头，我们理解中序遍历就快多了。

我们要先遍历左结点，A的左孩子为 B D E ,它的左孩子为 D , D为叶子结点，所以第一个输出D

后序遍历

左->右->根 LRN

遍历顺序为 D E B F G C A

层次遍历

这个就无需多说了 从上到下一层一层遍历，从左到右，一个一个结点遍历

遍历顺序为 A B C D E F G

小结

  1. 如果 先序和中序 一致，那么该树一定没有左节点

  2. 如果 后续和中序一致 ，那么该树一定没有 右孩子

  3. 我们可以通过先序和后续判断出根节点在哪？

    • 先序根节点为第一个
    • 后序根节点为倒数第一个

  4. 如果中序和根节点，我们就可以快速得到那些是左右孩子的结点，

    即根节点的左右两侧分别为左孩子和右孩子

对此，我们可以得出结论，如果知道一棵树的中序 ，以及先序和后续，层序的任意一个，我们就可以得一颗唯一树，或者得到未知的那一个遍历顺序，这就叫二叉树的重构。如果只给先序和后续，那么无法得出唯一的二叉树，或者只给出三种遍历的一种，我们也是无法得出的。

遍历习题

先序+ 中序

先序遍历 D A E F B C H G I

中序遍历 E A F D H C B G I

分析： 我们可以从先序中得出根节点为 D ,再看 中序遍历 ，从而 D的左孩子为 EAF ,右孩子为 HCBGI ;

D为根结点

同理分析 EAF， 从 先序遍历可以得出 A为 根结点 ，这种情况是最简单的 ，一目了然， EF 分别为 A的左右孩子。

EF 分别为 A的左右孩子。

再去分析 HCBGI ， B为根结点， HC，GI为左右孩子。 HC中 ，C为根节点 ，前序和中序相反，那么一定是没有右孩子。

在 GI中 ，I为根结点，前序和中序一致，那么一定没有左孩子。

image-20210506193903029

后序加中序

这个和前面原理差不多，前序是谁在前面谁是根结点，后序是谁在后面谁是根节点。如果 后续和中序一致 ，那么该树一定没有 右孩子。 抓住这两点就好了。

后序遍历： EFAHCIGBD

中序遍历：EAFDHCBGI

答案：这里得到的是和前面一样的树

层序+ 中序

这个和先序大同小异，但是不要有这样的误区，单纯的认为 层序第一层有一个结点 第二次有2个结点 .....,这个是错误的，一个结还有可能没有孩子的呢！

层序遍历： A B C D E

中序遍历 ： A C B E D

image-20210506195328568

线索二叉树

使用顺序结构存储二叉树，为了最大话利用空间，一般我们存储完全二叉树。在链式存储中，叶子结点或者分支结点左右孩子有一个为空，此时这里的指针指向空，我们是否能够把ta也利用起来呢？

何为线索

先序遍历，中序遍历，后序遍历，这其实就是一种转换，将二叉树这种非线性结构，转变成为了线性结构。

在中序遍历后得到的线性结构中,找到二叉树的一个结点的前驱结点，那么得重新遍历二叉树；对于叶子结点如果想要得到ta的后继结点，我们也还得重新遍历此二叉树。

有人就此提出了线索二叉树，n个结点的二叉树，那么一定有 n+1个指针空域，我们可以使用指针空域来存储前驱和后继。

一般我们规定 左空域来存储前驱（前驱线索），右空域指向后继结点（后继线索）。

image-20210506203902312

这个二叉树，我们就叫做中序线索二叉树。

当然，所有的结点不一定都有空域，所有我们要区分开来，

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild,*rchild;
    int ltag,rtag;//左右孩子的标志
}BiTNode,*BiTree;

ltag==0 时，表示 lchild 指向左孩子，等于1时指向右孩子。 rtag同理。

当然有了 中序线索二叉树，那么就有先序和后序线索二叉树。

数据结构