数据结构入门--树

数据结构

发布日期: 2022-09-19

更新日期: 2022-09-23

文章字数: 10.5k

阅读时长: 38 分

阅读次数:

树

树的定义

可以从集合论和图论两个角度定义树。本章从集合论的角度递归定义树，后续将从图论的角度再次定义树，读者可以体会两种定义的不同之处。

树（tree）是 n（n≥0）个节点的有限集合，当 n=0 时，为空树；n>0 时，为非空树。

任意一棵非空树，满足以下两个条件：

有且仅有一个称为根的节点
除根节点以外，其余节点可分为 m（m＞0）个互不相交的有限集 T1 , T2 , …, Tm，其中每一个集合本身又是一棵树，并且称为根的子树（subtree）

与树相关的术语：

节点——节点包含数据元素及若干指向子树的分支信息。
节点的度——节点拥有的子树个数。
树的度——树中节点的最大度数。
终端节点——度为 0 的节点，又称为叶子。
分支节点——度大于 0 的节点。除了叶子都是分支节点。
内部节点——除了树根和叶子都是内部节点。
节点的层次——从根到该节点的层数（根节点为第 1 层）。
树的深度（或高度）——指所有节点中最大的层数。例如，一棵树如图所示，根为第 1 层，根的子节点为第 2 层…该树的最大层次为 4，因此树的深度为 4。
路径——树中两个节点之间所经过的节点序列。
路径长度——两节点之间路径上经过的边数。例如，一棵树如图所示，D 到 A的路径为 D—B—A，D 到 A 的路径长度为 2。由于树中没有环，因此树中任意两个节点之间的路径都是唯一的。
双亲、孩子——节点的子树的根称为该节点的孩子，反之，该节点为其孩子的双亲。
兄弟——双亲相同的节点互称兄弟。
堂兄弟——双亲是兄弟的节点互称堂兄弟。
祖先——从该节点到树根经过的所有节点称为该节点的祖先。
子孙——节点的子树中的所有节点都称为该节点的子孙。
有序树——节点的各子树从左至右有序，不能互换位置。
无序树——节点各子树可互换位置。
森林——由 m（m≥0）棵不相交的树组成的集合。

树的存储结构

顺序存储

顺序存储采用一段连续的存储空间，因为树中节点的数据关系是一对多的逻辑关系，不仅要存储数据元素，还要存储它们之间的逻辑关系。

以下图为例，讲述三种顺序存储方法：双亲表示法、孩子表示法和双亲孩子表示法。

双亲表示法

双亲表示法，除了存储数据元素之外，还存储其双亲节点的存储位置下标，其中“−1”表示不存在。

每一个节点有两个域，即数据域 data 和双亲域 parent：

树根 A 没有双亲，双亲记为−1，B、C、D 的双亲为 A，而 A 的存储位置下标为 0，因此，B、C、D 的双亲记为 0。同样，E、F 的双亲为 B，而 B 的存储位置下标为 1，因此，E、F 的双亲记为 1。同理，其他节点也这样存储。
孩子表示法

孩子表示法是指除了存储数据元素之外，还存储其所有孩子的存储位置下标。

A 有 3 个孩子 B、C 和 D，而 B、C 和 D 的存储位置下标为 1、2 和 3，因此将 1、2 和 3 存入 A 的孩子域。同样，B 有 2 个孩子 E 和 F，而 E 和 F 的存储位置下标为 4 和 5，因此，将 4 和 5 存入 B 的孩子域。因为本题中每个节点都分配了 3 个孩子域（想一想，为什么？–树的度即节点的最大度为3），B 只有两个孩子，另一个孩子域记为−1，表示不存在。同理，其他节点也这样存储。
双亲孩子表示法

双亲孩子表示法是指除了存储数据元素之外，还存储其双亲和所有孩子的存储位置下标。此方法其实就是在孩子表示法的基础上增加了一个双亲域，其他
的都和孩子表示法相同，是双亲表示法和孩子表示法的结合体。

三种方法的优缺点：

双亲表示法只记录了每个节点的双亲，无法直接得到该节点的孩子。
孩子表示法可以得到该节点的孩子，但是无法直接得到该节点的双亲，而且由于不知道每个节点到底有多少个孩子，因此只能按照树的度（树中节点的最大度）分配孩子空间，这样做可能会浪费很多空间。
双亲孩子表示法是在孩子表示法的基础上，增加了一个双亲域，可以快速得到节点的双亲和孩子，其缺点和孩子表示法一样，可能浪费很多空间。

链式存储

由于树中每个节点的孩子数量无法确定，因此在使用链式存储时，孩子指针域不确定分配多少个合适。

如果采用“异构型”数据结构，每个节点的指针域个数按照节点的孩子数分配，则数据结构描述困难；如果采用每个节点都分配固定个数（如树的度）的指针域，则浪费很多空间。

一种是采用邻接表的思路，将节点的所有孩子存储在一个单链表中，称为孩子链表表示法；

一种是采用二叉链表的思路，左指针存储第一个孩子，右指针存储右兄弟，称为孩子兄弟表示法。

孩子链表表示法

孩子链表表示法类似于邻接表，表头包含数据元素并指向第一个孩子指针，将所有孩子放入一个单链表中。

在表头中，data 存储数据元素，first 为指向第 1 个孩子的指针。单链表中的节点记录该节点的下标和下一个节点的地址。

孩子链表表示法中，如果在表头中再增加一个双亲域 parent，则为双亲孩子链表表示法。
孩子兄弟表示法

节点除了存储数据元素之外，还有两个指针域 lchild 和 rchild，被称为二叉链表。lchild 存储第一个孩子地址，rchild 存储右兄弟地址。

孩子兄弟表示法的秘诀：长子当作左孩子，兄弟关系向右斜。

树、森林和二叉树的转换

树和二叉树的转换

根据树转换为二叉链表的秘诀，可以把任何一棵树转换为二叉树：
森林和二叉树的转换

森林是由 m（m≥0）棵不相交的树组成的集合。

可以把森林中的每棵树的树根看作兄弟关系，因此 3 棵树的树根 B、C 和 D 是兄弟，兄弟关系在右斜线上，其他的转换和树转二叉树一样，长子当作左孩子，兄弟关系向右斜。

或者把森林中的每一棵树转换成二叉树，然后把每棵树的根节点连接在右斜线上即可。

由于普通的树每个节点的子树个数不同，存储和运算都比较困难，因此在实际应用中，可以将树或森林转换为二叉树，然后进行存储和运算。

二者存在唯一的对关系，因此不影响其结果。

二叉树

二叉树（binary tree）是 n（n≥0）个节点构成的集合，它或为空树（n=0），或满足以下两个条件：

有且仅有一个称为根的节点；
除根节点以外，其余节点分为两个互不相交的子集 T1 和 T2，分别称为 T 的左子树和右子树，且 T1 和 T2 本身都是二叉树。

二叉树是一种特殊的树，它最多有两个子树，分别为左子树和右子树，二者是有序的，不可以互换。

也就是说，二叉树中不存在度大于 2 的节点。

二叉树一共有 5 种形态：

二叉树的结构最简单，规律性最强，因此通常被作为重点讲解。

二叉树的性质

性质 1：在二叉树的第 i 层上至多有 2⁽ⁱ⁻¹⁾个节点。

因为上一层的每个节点最多有两个孩子，因此当前层最多是上一层节点数的 2 倍：

性质 2：深度为 k 的二叉树至多有 2^k−1 个节点。

把每层的节点数加起来就是整棵二叉树的最大节点数:

性质 3：对于任何一棵二叉树，若叶子数为 n₀，度为 2 的节点数为 n₂，则 n₀=n₂+1。

**证明：**二叉树中的节点度数不超过 2，因此一共有 3 种节点，即度为 0、度为 1、度为 2。设二叉树总的节点数为 n，度为 0 的节点数为 n₀，度为 1 的节点数为 n₁，度为 2 的节点数为n₂，总节点数等于 3 种节点数之和，即 n=n₀ +n₁ +n₂。

而总节点数又等于“分支数 b+1”，即 n=b+1。为什么呢？

从下向上看，每一个节点对应一个分支，只有树根没有对应分支，因此总的节点数为“分支数 b+1”：

而分支数 b 怎么计算呢？

从上向下看，每个度为 2 的节点产生 2 个分支，度为 1 的节点产生 1个分支，度为 0 的节点没有分支，因此分支数 b=n₁ +2n₂，则 n=b+1=n₁+2n₂ +1。而前面已经得到 n=n₀ +n₁ +n₂，两式联合得：n₀ =n₂ +1。

有两种比较特殊的二叉树：满二叉树和完全二叉树。

满二叉树：一棵深度为 k 且有 2^k −1 个节点的二叉树。满二叉树每一层都“充满”了节点，达到最大节点数。
**完全二叉树：**除了最后一层外，每一层都是满的（达到最大节点数），最后一层节点是从左向右出现的（必须从左向右排列）。

深度为 k 的完全二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中编号 1～n 的节点一一对应。

也就是说，如果 2 没有左孩子，就不可以有右孩子；如果 2 没有右孩子，3 不可以有左孩子。

性质 4：具有 n 个节点的完全二叉树的深度必为⎣log₂n⎦ +1。

证明：假设完全二叉树的深度为 k，那么除了最后一层外，前 k−1 层都是满的，最后一层最少有一个节点，最后一层最多也可以充满节点，即 2^k−1个节点：

因此，2^k−1≤n≤2^k−1，右边放大后，2^k−1≤n<2^k，同时取对数，k−1≤log₂n<k，所以k=⎣log₂n⎦+1。其中，⎣⎦表示取下限，⎣x⎦表示小于 x 的最大整数，如⎣3.6⎦=3。

性质 5：对于完全二叉树，若从上至下、从左至右编号，则编号为 i 的节点，其左孩子编号必为 2i，其右孩子编号必为 2i +1，其双亲的编号必为 i/2。

**例题 1：**一棵完全二叉树有 1001 个节点，其中叶子节点的个数是多少？

**解题思路：**首先找到最后一个节点 1001 的双亲节点，其双亲节点编号为 1001/2=500，该节点是最后一个拥有孩子的节点，其后面全是叶子，即 1001−500=501 个叶子。

**例题 2：**一棵完全二叉树第 6 层有 8 个叶子，则该完全二叉树最少有多少节点，最多有多少个节点？

解题思路：完全二叉树的叶子分布在最后一层或倒数第二层，因此该树有可能为 6 层或 7 层。

节点最少的情况（6 层）：8 个叶子在最后一层，即第 6 层，前 5 层是满的。最少有 2⁵−1+8=39 个节点。

节点最多的情况（7 层）：8 个叶子在倒数第二层，即第 6 层，前 6 层是满的，第 7 层最少缺失了 8×2 个节点，因为第 6层的 8 个叶子如果生成孩子的话，会有 16个节点。最多有 27−1−16=111 个节点。

二叉树的存储结构

顺序存储

二叉树也可以采用顺序存储，按完全二叉树的节点层次编号，依次存放二叉树中的数据元素。

完全二叉树很适合顺序存储方式，而普通二叉树在顺序存储时需要补充为完全二叉树，在对应完全二叉树没有孩子的位置补 0：

显然，普通二叉树不适合顺序存储方式，因为有可能在补充为完全二叉树过程中，补充太多的 0，而浪费大量空间，因此普通二叉树可以使用链式存储。

链式存储

二叉树采用链式存储方式：每个节点包含一个数据域，存储节点信息；还包含两个指针域，指向左右两个孩子。这种存储方式称为二叉链表：

一般情况下，二叉树采用二叉链表存储即可，但是在实际问题中，如果经常需要访问双亲节点，二叉链表存储则必须从根出发查找其双亲节点，这样做非常麻烦。

为了解决这一问题，可以增加一个指向双亲节点的指针域，这样每个节点就包含3 个指针域，分别指向两个孩子节点和双亲节点，还包含一个数据域，用来存储节点信息。这种存储方式称为三叉链表：

二叉树的创建

如果对二叉树进行操作，必须先创建一棵二叉树。如何创建一棵二叉树呢？

从二叉树的定义就可以看出，它是递归定义的（除了根之外，左、右子树也是一棵二叉树），因此可以用递归来创建二叉树。

递归创建二叉树有两种方法，分别是询问法和补空法。

询问法

每次输入节点信息后，询问是否创建该节点的左子树，如果是，则递归创建其左子树，否则其左子树为空；询问是否创建该节点的右子树，如果是，则递归创建其右子树，否则其右子树为空。

算法步骤：

输入节点信息，创建一个节点 T。
询问是否创建 T 的左子树，如果是，则递归创建其左子树，否则其左子树为 NULL。
询问是否创建 T 的右子树，如果是，则递归创建其右子树，否则其右子树为 NULL。

代码实现：

#include<iostream>
using namespace std;

typedef struct Bnode{ 	/*定义二叉树存储结构*/
	char data;
	struct Bnode *lchild,*rchild;
}Bnode,*Btree;

void createtree(Btree &T)	/*创建二叉树函数*/
{
    char check;					/*判断是否创建左右孩子*/
    T=new Bnode;
    cout<<"请输入结点信息:"<<endl;	/*输入根结点数据*/
    cin>>T->data;
    cout<<"是否添加 "<<T->data<<"的左孩子? (Y/N)"<<endl; /*询问是否创建T的左子树*/
    cin>>check;
    if(check=='Y')
        createtree(T->lchild);
    else
        T->lchild=NULL;
    cout<<"是否添加"<<T->data<<"的右孩子? (Y/N)"<<endl; /*询问是否创建T的右子树*/
    cin>>check;
    if(check=='Y')
        createtree(T->rchild);
    else
        T->rchild=NULL;
    return;
}

补空法

补空法是指如果左子树或右子树为空时，则用特殊字符补空，如“#”，然后按照根、左子树、右子树的顺序，得到先序遍历序列，根据该序列递归创建二叉树：

算法步骤：

输入补空后的二叉树先序遍历序列。
如果 ch==‘#’，T=NULL；否则创建一个新节点 T，令 T->data=ch；递归创建 T 的左子树；递归创建 T 的右子树。

代码实现：

#include<iostream>
#include<queue>//引入队列头文件
using namespace std;

typedef struct Bnode{/*定义二叉树存储结构*/
	char data;
	struct Bnode *lchild,*rchild;
}Bnode,*Btree;

void Createtree(Btree &T)	/*创建二叉树函数*/
{
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin>>ch;
	if(ch=='#')
        T=NULL;			//递归结束，建空树
	else{
		T=new Bnode;
		T->data=ch;					//生成根结点
		Createtree(T->lchild);	//递归创建左子树
		Createtree(T->rchild);	//递归创建右子树
	}
}

二叉树的遍历

二叉树的遍历就是按某条搜索路径访问二叉树中的每个节点一次且只有一次。

按照根的访问顺序不同，根在前面称为先序遍历（DLR），根在中间称为中序遍历（LDR），根在最后称为后序遍历（LRD）。

因为树的定义本身就是递归的，因此树和二叉树的基本操作用递归算法很容易实现。

先序遍历：

先序遍历是指先访问根，然后先序遍历左子树，再先序遍历右子树，即 DLR。

算法步骤：

如果二叉树为空，则空操作，否则：

访问根节点
先序遍历左子树
先序遍历右子树

左子树为空或已遍历才可以遍历右子树。

代码实现：

void preorder(Btree T)//先序遍历
{
    if(T)
    {
       cout<<T->data<<"  ";
       preorder(T->lchild);
       preorder(T->rchild);
    }
}

中序遍历：

中序遍历是指中序遍历左子树，然后访问根，再中序遍历右子树，即 LDR。

算法步骤：

如果二叉树为空，则空操作，否则：

中序遍历左子树
访问根节点
中序遍历右子树

左子树为空或已遍历才可以访问根

代码实现：

void inorder(Btree T)//中序遍历
{
    if(T)
    {
       inorder(T->lchild);
       cout<<T->data<<"  ";
       inorder(T->rchild);
    }
}

后序遍历：

后序遍历是指后序遍历左子树，后序遍历右子树，然后访问根，即 LRD。

算法步骤：

如果二叉树为空，则空操作，否则：

后序遍历左子树
后序遍历右子树
访问根节点

左子树、右子树为空或已遍历才可以访问根

代码实现：

void posorder(Btree T)//后序遍历
{
    if(T)
    {
       posorder(T->lchild);
       posorder(T->rchild);
       cout<<T->data<<"  ";
    }
}

投影法：

如果不需要按照程序执行流程，那么只要写出二叉树的遍历序列即可，还可以使用投影法快速得到遍历序列。

原图：

中序遍历：

中序遍历就像在无风的情况下，遍历顺序为左子树、根、右子树，太阳直射，将所有的节点投影到地上
先序遍历：

先序遍历就像在左边大风的情况下，将二叉树树枝刮向右方，且顺序为根、左子树、右子树，太阳直射，将所有的节点投影到地上
后序遍历：

后序遍历就像在右边大风的情况下，将二叉树树枝刮向左方，且顺序为左子树、右子树、根，太阳直射，将所有的节点投影到地上

层次遍历：

首先遍历第 1 层，然后第 2层…同一层按照从左向右的顺序访问，直到最后一层。

程序是怎么实现层次遍历的呢？

通过观察可以发现，先被访问的节点，其孩子也先被访问，先来先服务，因此可以用队列实现

下面以下图中的二叉树为例，展示该二叉树层次遍历的过程：

算法步骤：

首先创建一个队列 Q，令树根入队。（注意：实际上是指向树根 A 的指针入队，这里为了图解方便，直接把数据入队了。）
队头元素出队，输出 A，同时令 A 的孩子 B、C 入队（从左向右顺序，如果是普通树，则包含所有孩子）
队头元素出队，输出 B，同时令 B 的孩子 D、E 入队：
队头元素出队，输出 C，同时令 C 的孩子 F 入队：
队头元素出队，输出 D，同时令 D 的孩子入队，D 没有孩子，什么也不做。
以此类推，直到队列为空，算法结束。

代码步骤：


bool Leveltraverse(Btree T)
{
    Btree p;
    if(!T)
        return false;
    queue<Btree>Q; //创建一个普通队列(先进先出)，里面存放指针类型
    Q.push(T); //根指针入队
    while(!Q.empty()) //如果队列不空
    {
        p=Q.front();//取出队头元素作为当前扩展结点livenode
        Q.pop(); //队头元素出队
        cout<<p->data<<"  ";
        if(p->lchild)
            Q.push(p->lchild); //左孩子指针入队
        if(p->rchild)
            Q.push(p->rchild); //右孩子指针入队
    }
    return true;
}

线索二叉树

二叉树是非线性数据结构，而遍历序列是线性序列，二叉树遍历实际上是将一个非线性结构进行线性化的操作。

根据线性序列的特性，除了第一个元素外，每一个节点都有唯一的前驱，除了最后一个元素外，每一个节点都有唯一的后继。而根据遍历序列的不同，每个节点的前驱和后继也不同。

采用二叉链表存储时，只记录了左、右孩子的信息，无法直接得到每个节点的前驱和后继。

线索二叉树存储结构

二叉树采用二叉链表存储时，每个节点有两个指针域。如果二叉链表有 n 个节点，则一共有 2n 个指针域，而只有 n−1 个是实指针，其余 n+1 个都是空指针，为什么呢？

推导过程：

因为二叉树有 n−1 个分支，每个分支对应一个实指针，每一个节点对应一个分支，只有树根没有对应分支，因此分支数等于节点数减 1，即 b=n−1。

每个分支对应一个实指针，所以有 n−1 个实指针。

总的的指针数减去实指针数，即为空指针数，即 2n− (n−1)=n+1。

n 个节点的二叉链表中有 n+1 个空指针，可以充分利用空指针记录节点的前驱或后继信息，从而加快查找节点前驱和后继的速度。

每个节点还是两个指针域，如果节点有左孩子，则 lchild 指向左孩子，否则 lchild 指向其前驱；如果节点有右孩子，则 rchild 指向右孩子，否则 rchild 指向其后继。

那么怎么区分到底存储的是左孩子和右孩子，还是前驱和后继信息呢？

为了避免混淆，增加两个标志域 ltag 和 rtag：

这种带有标志域的二叉链表称为线索链表，

指向前驱和后继的指针称为线索，

带有线索的二叉树称为线索二叉树，

以某种遍历方式将二叉树转化为线索二叉树的过程称为线索化。

构造线索二叉树

每种遍历顺序不同，节点的前驱和后继也不同，因此二叉树线索化必须指明是什么遍历顺序的线索化

线索二叉树分为前序线索二叉树、中序线索二叉树和后序线索二叉树。

二叉树线索化的过程，实际上是在遍历过程中修改空指针的过程。

可以设置两个指针，一个指针 pre 指向刚刚访问的节点，另一个指针 p 指向当前节点。也就是说，pre 指向的节点为 p 指向的节点的前驱，反之，p 指向的节点为 pre 指向的节点的后继。

在遍历的过程中，如果当前节点 p 的左孩子为空，则该节点的 lchild 指向其前驱，即 p->lchild=pre；

如果 pre节点的右孩子为空，则该节点的 rchild 指向其后继，即 pre->rchild=p。

算法步骤：

指针 p 指向根节点，pre 初始化为空，pre 永远指向 p 的前驱。
若 p 非空，则重复下面操作：
- 中序线索化 p 的左子树。
- 若 p 的左子树为空，则给 p 加上左线索，即 p->ltag=1，p 的左子树指针指向 pre（前驱），即 p->lchild=pre；否则令 p->ltag=0。
- 若 pre 非空，则判断如果 pre 的右子树为空，给 pre 加上右线索，即 pre->rtag=1，pre的右孩子指针指向 p（后继），即 pre->rchild=p，否则令 pre->rtag=0。
- p 赋值给 pre，转向 p 的右子树。
- 中序线索化 p 的右子树。
处理最后一个节点，令其后继为空，即pre->rchild=NULL; pre->rtag=1。

注意：如果在考试当中只要求绘图，则没必要按照程序执行的过程进行线索化，可以直接写出遍历序列。

根据该遍历序列的先后顺序，对所有的空指针域进行线索化，左指针为空，则令其指向前驱；右指针为空，则令其指向后继。

示例：

首先写出二叉树的中序遍历序列，即 DBEAFGC，然后按照该遍历序列，对所有的空指针进行线索化。
D 的左指针为空，但在中序遍历序列中，D 是第一个元素，没有前驱，赋值为 NULL。
D 的右指针为空，中序遍历序列中 D 的后继是 B，因此 D 的右指针指向 B 节点。
同理，从中序遍历序列中可以很清楚地知道每个节点的前驱和后继，分别对所有节点的空指针进行线索化即可。

代码实现：

void InThread(BTtree &p)//中序线索化
{
	//pre是全局变量，指向当前结点p的前驱
	if(p)
	{
		InThread(p->lchild);   //左子树递归线索化
		if(!p->lchild)   //p的左孩子为空
		{
			p->ltag=1;    //给p加上左线索
			p->lchild=pre; 	//p的左孩子指针指向pre（前驱）
		}
		else
			p->ltag=0;
		if(pre)
        {
            if(!pre->rchild)  //pre的右孩子为空
            {
                pre->rtag=1; //给pre加上右线索
                pre->rchild=p; //pre的右孩子指针指向p（后继）
            }
            else
                pre->rtag=0;
        }
		pre=p;                     //保持pre指向p的前驱
		InThread(p->rchild);   //右子树递归线索化
    }
}

遍历线索二叉树

线索二叉树的线索记录了前驱和后继信息，因此可以利用这些信息进行遍历。下面以中序线索二叉树遍历为例，讲述遍历过程。

算法步骤：

指针 p 指向根节点。
若 p 非空，则重复以下操作：
- p 指针沿左孩子向下，找到最左节点，它是中序遍历的第一个节点；
- 访问 p 节点；
- 沿着右线索查找当前节点 p 的后继节点并访问，直到右线索为 0 或遍历结束。
遍历 p 的右子树。

代码实现：

void InorderThread(BTtree T)//遍历中序线索二叉树
{
    BTtree p;
    p=T;
    while(p)
    {
       while(p->ltag==0) p=p->lchild;  //找最左结点
       cout<<p->data<<"  ";//输出结点信息
       while(p->rtag==1&&p->rchild) //右孩子为线索化，指向后继
       {
			p=p->rchild;   //访问后继结点
			cout<<p->data<<"  ";//输出结点信息
       }
       p=p->rchild;//转向p的右子树
    }
}

对于频繁查找前驱和后继的运算，线索二叉树优于普通二叉树。但是对于插入和删除操作，线索二叉树比普通二叉树开销大，因为除插入和删除操作外，还要修改相应的线索。

树和森林的遍历

树的遍历：

树的遍历操作包括先根遍历和后根遍历两种方式。

先根遍历：如果树非空，则先访问根节点，然后按从左向右的顺序，先根遍历根节点的每一棵子树。树的先根遍历顺序与该树对应的二叉树的先序遍历顺序相同。
后根遍历：如果树非空，则按从左向右的顺序，后根遍历根节点的每一棵子树，然后访问根节点。树的后根遍历顺序与该树对应的二叉树的中序遍历顺序相同。

先根遍历

先根遍历时，先访问根，然后按从左向右的顺序，先根遍历根节点的每一棵子树，第一棵子树遍历完毕，才可以遍历第二棵子树…
后根遍历

后根遍历时，先按从左向右的顺序后根遍历每一棵子树，没有子树或子树已遍历完毕，才可以访问根。

森林的遍历：

森林的遍历操作有先序遍历和中序遍历两种方式。

先序遍历：

如果森林非空，则：
- 访问第一棵树的根节点；
- 先序遍历第一棵树的根节点的子树森林；
- 先序遍历除第一个棵树之外，剩余的树构成的森林。
其访问顺序与该森林对应的二叉树的先序遍历顺序相同。
中序遍历

如果森林非空，则：
- 中序遍历第一棵树的根节点的子树森林；
- 访问第一棵树的根节点；
- 中序遍历除第一个棵树之外，剩余的树构成的森林。
其访问顺序与该森林对应的二叉树的中序遍历顺序相同。

树的应用

二叉树的深度

首先考虑特殊情况，如果二叉树为空，则深度为 0；一般情况下，二叉树的深度等于二叉树左右子树的深度最大值加 1。

算法步骤：

如果二叉树为空，则深度为 0。
否则为根的左、右子树的深度最大值加 1。

代码实现：

int Depth(Btree T)//求二叉树的深度
{
    int m,n;
    if(T==NULL)//如果为空树，深度为0
        return 0;
    else
    {
		m=Depth(T->lchild);//递归计算左子树深度
		n=Depth(T->rchild);//递归计算左子树深度
		if(m>n)
			return m+1;//返回左右子树最大值加1
		else
			return n+1;
    }
}

二叉树的叶子数

首先考虑特殊情况，如果二叉树为空，则叶子数为 0；如果根的左、右子树都为空，则叶子数为 1；

一般情况下，二叉树的叶子数等于左子树的叶子数与右子树的叶子数之和。

算法步骤：

如果二叉树为空，则叶子数为 0。
如果根的左、右子树都为空，则叶子数为 1。
否则求左子树的叶子数和右子树的叶子数之和，即为二叉树的叶子数。

代码实现：

int LeafCount(Btree T)//求二叉树的叶子数
{
    if(T==NULL)//如果为空树，深度为0
        return 0;
    else
        if(T->lchild==NULL&&T->rchild==NULL)//左右子树均为空，则叶子数为1
           return 1;
        else
           return LeafCount(T->lchild)+LeafCount(T->rchild);//递归计算左子树和右子树的叶子数之和
}

同样，要计算二叉树的节点数，如果二叉树为空，则节点数为 0；

否则，二叉树的节点数等于左子树与右子树的节点数之和加 1。

代码实现：

int NodeCount(Btree T)//求二叉树的结点数
{
    if(T==NULL)//如果为空树，深度为0
        return 0;
    else
        return NodeCount(T->lchild)+NodeCount(T->rchild)+1;//递归计算左子树和右子树的结点数之和加1
}

此类问题只需要考虑特殊情况，例如树空、只有一个根节点等，一般情况下，直接递归即可。

三元组创建二叉树

假设以三元组(F, C, L/R)的形式输入一棵二叉树的诸边（其中 F 是双亲节点的标识，C是孩子节点标识，L/R 表示 C 为 F 的左孩子或右孩子），且在输入的三元组序列中，C 是按层次顺序出现的。

设节点的标识是字符类型，F 为 NULL 时，C 为根节点标识，若 C 亦为NULL，则表示输入结束。

算法步骤：

输入第一组数据，创建根节点入队。因为是按层次输入的，所以可以借助队列实现。
输入下一组数据。
如果队列非空且输入数据前两项非空，则队头元素出队。
判断输入数据中的双亲是否和队头元素相等，如果不相等，则转向第 3 步；如果相等，则创建一个新节点，判断该节点是其双亲的左孩子还是右孩子并做相应的处理，然后新节点入队。输入下一组数据，转向第 4 步（因为一个队头元素可能有两个孩子，所以不能创建一个孩子就结束）
直到队列为空或者输入数据前两项为空，算法停止。
输出先序、中序和后序序列。

代码实现：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
/*
输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识，C 表示孩子结点标识，L/R 表示 C 为 F 的左孩子或右孩子)，
且在输入的三元组序列中，C 是按层次顺序出现的。
设结点的标识是字符类型。F=NULL时 C 为根结点标识，若 C 亦为NULL，则表示输入结束。
试编写算法，由输入的三元组序列建立二叉树的二叉链表,并以先序、中序、后序序列输出。
*/
/*测试数据
NULL A L
A B L
A C R
B D R
C E L
C F R
D G L
F H L
NULL NULL L
*/
struct biTnode
{
    string data;
    biTnode *lChild,*rChild;
};
 biTnode* T=NULL;
void CreatebiTree(biTnode* &T)
{
    string a,b,c;
    biTnode *node,*p;
    queue<biTnode*>q;
    cin>>a>>b>>c;
    if(a=="NULL"&&b!="NULL")//创建根结点
    {
        node=new biTnode;
        node->data=b;
        node->lChild=node->rChild=NULL;
        T=node;
        q.push(T);
    }
    cin>>a>>b>>c;
    while(!q.empty()&&a!="NULL"&&b!="NULL")
    {
        p=q.front();
        q.pop();
        while(a==p->data)
        {
            node=new biTnode;
            node->data=b;
            node->lChild=node->rChild=NULL;
            if(c=="L")
            {
                p->lChild=node;
                cout<<p->data<<"'s lChild is "<<node->data<<endl;
            }
            else
            {
                p->rChild=node;
                cout<<p->data<<"'s rChild is "<<node->data<<endl;
            }
            q.push(node);
            cin>>a>>b>>c;
        }
    }
}

遍历序列还原树

根据遍历序列可以还原树，包括二叉树还原、树还原和森林还原 3 种。

二叉树还原

由二叉树的前序序列和中序序列，或者中序序列和后序序列，可以唯一地还原一棵二叉树。

注意：由二叉树的前序序列和后序序列不能唯一地还原一棵二叉树。

算法步骤：

先序序列的第一个字符为根。
在中序序列中，以根为中心划分左右子树。
还原左右子树。
- 先序序列的第一个字符 A 为根，在中序序列中以 A 为中心划分左右子树，左子树包含 DBE 三个节点，右子树包含 FGC 三个节点：
- 左子树 DBE，在先序序列中的顺序为 BDE，第一个字符 B 为根，在中序序列中以 B为中心划分左右子树，左右子树只有一个节点，因此直接作为 B 的左右孩子即可：
- 右子树 FGC，在先序序列中的顺序为 CFG，第一个字符 C 为根，在中序序列中以 C为中心划分左右子树，左子树包含 FG 节点，右子树为空：
- 左子树 FG，在先序序列中的顺序为 FG，第一个字符 F 为根，在中序序列中以 F 为中心划分左右子树，左为空，右子树只有一个节点 G，作为 F 的右孩子即可：

代码实现：

#include<iostream>
using namespace std;
typedef struct node
{
    char data;
    struct node *lchild,*rchild;
}BiTNode,*BiTree;

BiTree pre_mid_createBiTree(char *pre,char *mid,int len) //前序中序还原建立二叉树
{
    if(len==0)
        return NULL;
    char ch=pre[0];  //找到先序中的第一个结点
    int index=0;
    while(mid[index]!=ch)//在中序中找到的根结点的左边为该结点的左子树，右边为右子树
    {
        index++;
    }
    BiTree T=new BiTNode;//创建根结点
    T->data=ch;
    T->lchild=pre_mid_createBiTree(pre+1,mid,index);//建立左子树
    T->rchild=pre_mid_createBiTree(pre+index+1,mid+index+1,len-index-1);//建立右子树
    return T;
}

代码解释：

BiTree pre_mid_createBiTree(char *pre,char *mid,int len)

这个函数有 3 个参数，pre 和 mid 为指针类型，分别指向前序、中序序列的首地址；len为序列的长度。前序和中序的序列长度一定是相同的。
首先，先序序列的第一个字符 pre[0]为根，然后在中序序列中查找根所在的位置，用 index记录查找长度，找到后以根为中心，划分出左右子树。

左子树：先序序列中的首地址为 pre+1，中序序列的首地址为 mid，长度为 index
右子树：先序序列中的首地址为 pre+index+1，中序序列的首地址为 mid+index+1，长度为 len−index−1；右子树的长度为总长度减去左子树的长度，再减去根。

由二叉树的后序序列和中序序列也可以唯一确定一棵二叉树，方法和上面一样，只不过后序序列的最后一个字符为根，然后在中序序列中以根为中心划分左右子树。

代码实现：

BiTree pro_mid_createBiTree(char *last,char *mid,int len)//后序中序还原建立二叉树
{
    if(len==0)
       return NULL;
    char ch=last[len-1]; //取得后序遍历顺序中最后一个结点
    int index=0;//在中序序列中找根结点，并用index记录长度
    while(mid[index]!=ch)//在中序中找到根结点，左边为该结点的左子树，右边为右子树
       index++;
    BiTree T=new BiTNode;//创建根结点
    T->data=ch;
    T->lchild=pro_mid_createBiTree(last,mid,index);//建立左子树
    T->rchild=pro_mid_createBiTree(last+index,mid+index+1,len-index-1);//建立右子树
    return T;
}

先序遍历和中序遍历还原二叉树秘籍：先序找根，中序分左右。

后序遍历和中序遍历还原二叉树秘籍：后序找根，中序分左右。

树还原

由于树的先根遍历和后根遍历与其对应二叉树的先序遍历和中序遍历相同，因此可以根据该对应关系，先还原为二叉树，然后再把二叉树转换为树。

森林还原

由于森林的先序遍历和中序遍历与其对应二叉树的先序遍历和中序遍历相同，因此可以根据该对应关系，先还原为二叉树，然后再把二叉树转换为森林。

哈夫曼树

哈夫曼编码的基本思想是以字符的使用频率作为权来构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。

哈夫曼树是通过将所要编码的字符作为叶子节点，将该字符在文件中的使用频率作为叶子节点的权值，以自底向上的方式，做 n−1 次“合并”运算构造出来的。

哈夫曼编码被广泛地应用于数据压缩，尤其是远距离通信和大容量数据存储，常用的 JPEG 图片就是采用哈夫曼编码压缩的。

哈夫曼编码的核心思想是让权值大的叶子离根最近。

哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一棵新树，新树根节点的权值为其左右孩子节点权值之和，并将新树插入树的集合中。

算法步骤：

确定合适的数据结构。编写程序前需要考虑的情况如下：
- 哈夫曼树中没有度为 1 的节点，则一棵有 n 个叶子节点的哈夫曼树共有 2n−1 个节点（n−1 次“合并”，每次产生一个新节点）。
- 构成哈夫曼树后，为求编码需从叶子节点出发走一条从叶子到根的路径。
- 译码需要从根出发走一条从根到叶子的路径。那么对每个节点而言，需要知道每个节点的权值、双亲、左孩子、右孩子和节点信息。
初始化。构造 n 棵节点为 n 个字符的单节点树集合 T={t1, t2 , t3 , …, tn}，每棵树只有一个带权的根节点，权值为该字符的使用频率。
如果 T 中只剩下一棵树，则哈夫曼树构造成功，跳到第 6 步。否则，从集合 T 中取出没有双亲且权值最小的两棵树 t i 和 t j，将它们合并成一棵新树 zk，新树的左孩子为 t i，右孩子为 t j，zk 的权值为 t i 和 t j 的权值之和。
从集合 T 中删去 t i、t j，加入 zk。
重复以上第 3 步和第 4 步。
约定左分支上的编码为“0”，右分支上的编码为“1”。从叶子节点到根节点逆向求出每个字符的哈夫曼编码，那么从根节点到叶子节点路径上的字符组成的字符串为该叶子节点的哈夫曼编码，算法结束。

QT-7274

https://qt-7274.github.io/2022/09/19/shu-ju-jie-gou-ru-men-shu/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 QT-7274 !

数据结构

英雄联盟大乱斗攻略

英雄联盟大乱斗是一个更加偏向于娱乐和随机性的一种娱乐模式，许多玩法和出装值得探讨与开发。

2022-09-20 电子游戏

游戏

PCA算法在人脸识别中的应用

PCA是最简单的以特征量分析多元统计分布的方法。

2022-09-18 QT-7274

图像识别算法 Python

数据结构入门--树

树

树的定义

树的存储结构

顺序存储

链式存储

树、森林和二叉树的转换

二叉树

二叉树的性质

二叉树的存储结构

顺序存储

链式存储

二叉树的创建

二叉树的遍历

先序遍历：

中序遍历：

后序遍历：

投影法：

层次遍历：

线索二叉树

线索二叉树存储结构

构造线索二叉树

遍历线索二叉树

树和森林的遍历

树的遍历：

森林的遍历：

树的应用

二叉树的深度

二叉树的叶子数

三元组创建二叉树

遍历序列还原树

二叉树还原

树还原

森林还原

哈夫曼树

你的赏识是我前进的动力