在离散的学习中,图论有探讨过树(在这里我们讨论的为有向树),在计算机领域中树型结构是非常重要的非线性结构,树型结构在客观事件普遍存在,比如族谱哇,各种社会组织的结构等。本章重点介绍 树,二叉树 ,森林,并且研究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同理。

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

本文由 越行勤 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://blog.yxqin.top/2021/07/04/bitree
最后更新于:  109  天前,内容可能已经不具有时效性,请谨慎参考。

Q.E.D.


努力学习的小菜鸟