数据结构 5 树

树

5.1 树和二叉树的定义

5.1.1 树的定义

树的定义

树

树的其它表示方式

比如课本的目录就是凹入表示

5.1.2 树的基本术语

树的结点(node)： 包含一个数据元素及若干指向其子树的分支

结点的度(degree)：结点具有子树的个数

树的度：树中所有结点的度的最大值

分支结点(或者叫非终端结点)：度大于0的结点，根结点以外的分支节点称为内部结点

叶子(或者叫终端结点)：度为0的结点

结点的孩子：结点子树的根，该结点为孩子的双亲

兄弟：同一双亲的孩子

堂兄弟：其双亲在同一层的结点间互称堂兄弟

结点的祖先：从根到该结点所经分支上的所有结点

结点的子孙：一个结点的所有子树中的结点.

结点的层次：根为第一层，其孩子结点为第二层，如此类推到每个结点层次

树的层数(或者叫结点的层次)：根节点的层数为1，其他结点的层数为根节点到该结点的分支数+1

树的高度(或者叫深度)：树中结点的最大层数

树的基本术语

A结点的三个孩子：B、C、D

B、C、D的双亲：A

D结点的三个孩子：H、I、J

M结点的祖先：A、D、H

A结点的子孙：除了A之外的所有结点

有序树：若将树中结点的各子树看成从左至右是有序的(不能互换)，则称该树为有序树，否则为无序树。

森林：0个或多个互不相交的树的集合

image-20231205111033912

5.1.3 二叉树的定义

为何要重点研究每结点最多只有两个“叉” 的树？

• 二叉树的结构最简单，规律性最强

• 可以证明，所有树都能转为唯一对应的二叉树，不失一般性

普通树 (多叉树) 若不转化为二叉树，则运算很难实现

二叉树在树结构的应用中起着非常重要的作用，因为对二叉的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性

定义：二叉树是\(n(n≥0)\) 个结点的有限集，它或者是空集\((n =0)\)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成

特点

1、每个结点最多有俩孩子(二叉树中不存在度大于 2 的结点)

2、子树有左右之分，其次序不能颠倒（次序颠倒了就是另外一棵树）

3、二叉树可以是空集合，根可以有空的左子树或空的右子树

注⭐：

二叉树不是树的特殊情况，它们是两个概念

二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树

树当结点只有一个孩子时，就无须区分它是左还是右的次序。因此二者是不同的。这是二又树与树的最主要的差别。

(也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了)， 可以理解为二叉树不是树不是有序树，是一个独立的概念

虽然二叉树与树的概念不同，但有关树的基本术语对二叉树都适用

二叉树的五种基本形态：

二叉树的五种基本形态

5.2 树和二叉树的抽象数据类型定义

(以二叉树为例来学习)

二叉树的抽象数据类型定义

ADT BinaryTree{

  	数据对象 D：具有相同特性的数据元素集合。
  	数据关系 R：若D为空集，则称为空树。否则R={H}, H是如下关系：
    （1）在D中存在唯一的称为根的数据元素root；
    （2）若D除了根结点外，D中还有其它结点，则其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。
	基本操作P:
   	 
    CreateBiTree(&T, definition)     
    	初始条件: definition给出二叉树T的定义
        (后面会学二叉树的遍历方法,对于不同的建立方式definition 指的是建立方式)
        操作结果: 按definition构造二叉树T
	PreOrderTraverse(T)
        初始条件: 二叉树T存在
        操作结果: 先序遍历T，对每个结点访问一次
    InOrderTraverse(T)
        初始条件: 二叉树T存在
        操作结果: 中序遍历T，对每个结点访问一次
   	PostOrderTraverse(T)
        初始条件: 二叉树T存在
        操作结果: 后序遍历T，对每个结点访问一次
	……
    ……

}

5.3 二叉树的性质和存储结构

5.3.1 基本的性质

性质1：在二叉树的第 \(i\) 层上至多有\(2^{i-1}\)个结点\((i≥1)\)

第一层：\(2^0=1\)

第二层：\(2^1=2\)

第三层：\(2^2=4\)

第四层：\(2^3=8\)

……

提问：第 \(i\) 层上至少有几个结点？---------1个

性质2：深度为 \(k\) 的二叉树至多有\(2^k-1\)个结点\((k≥1)\)

（都怪第一层只有一个结点

提问：深度为 \(k\) 的二叉树至少有几个结点？---------k个

性质3：对任何一颗二叉树T，如果其叶子结点数为\(n_0\)，度为2的结点数为\(n_2\)，则\(n_0=n_2+1\)，

（度为2的结点数又称双分支结点数）

非空二叉树上叶子结点数等于双分支结点数加1

性质3的本身的用处其实不是很大，用处大的是我们分析证明的过程

5.3.2 满二叉树

两种特殊形式的二叉树：满二叉树和完全二叉树

为什么要研究这两种特殊形式？

——因为它们在顺序存储方式下可以复原

满二叉树：

一棵深度为 \(k\) 且有 \(2^k -1\) 个结点的二叉树称为满二叉树

即所有分支结点都存在左子树和右子树，并且所有叶子结点都在最底层上，其特点是每一层上的结点数都是最大结点数。

满二叉树

对满二叉树结点位置进行编号：

• 编号规则：从根结点开始，自上而下，自左而右。
• 每一结点位置都有元素

满二叉树在同样深度的二叉树中结点个数最多

满二叉树在同样深度的二叉树中叶子结点个数最多

5.3.3 完全二叉树

完全二叉树：

深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

完全二叉树例子

注：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树

一定是连续的去掉！！！

特点：

（1）叶子结点只可能在层次最大的两层上出现，即最下层和次最下层；

（2）对任一结点，如果其右子树的最大层次为 \(i\)，则其左子树的最大层次必为 \(i\) 或 \(i+1\)，即最下层的叶子结点集中在树的左部。

5.3.4 完全二叉树的性质

性质4：具有n个结点的完全二叉树的深度为 \(\lfloor log_2n \rfloor+1\)

注意：\(\lfloor x \rfloor\)：称作x的底，表示不大于x的最大整数（向下取整），例如：\(\lfloor 3.5 \rfloor=3\)

比如上图，\(n=12\)，所以完全二叉树的深度为 \(\lfloor log_212 \rfloor+1=4\)

性质5：对有n个结点的完全二叉树的结点按层序编号(从上至下，从左至右)，则对任一结点 \(i(1≤ i≤n)\) ，有：

• 如果\(i=1\)，则结点为根；如果\(i>1\)，则其双亲是结点\(\lfloor i/2 \rfloor\)
• 如果 \(2i>n\)，则结点 \(i\) 为叶子结点，无左孩子；否则其左孩子是结点 \(2i\)
• 如果 \(2i+1>n\)，则结点 \(i\) 为叶子结点，无右孩子；否则其右孩子是结点 \(2i+1\)

这里大部分情况下就只看标粗的部分，

举例：5，双亲是\(\lfloor 5/2 \rfloor=2\)，左孩子是结点 \(2*5=10\)，右孩子是结点 \(2*5+1=11\)，，就是这么easy的性质

性质5表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系

具体证明先不用了解

作用：在顺序存储的时候，操作下标为i的结点的双亲或者后继的时候

5.3.5 二叉树的存储结构

二叉树的顺序存储

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素

二叉树的顺序存储例子

//二叉树顺序存储表示，Binary Tree
#define MAXTSIZE 100
Typedef TELemType SqBiTree[MAXTSIZE]; //TELemType根据具体情况换，比如char、int
SqBiTree bt; //定义了一个数组bt

二叉树的顺序存储例子2

其实这里不是给0，是给一个空值NULL，

优点：简单

缺点：

① 顺序存储通用的缺点：大小固定，数组中元素个数变化特别大，就不适用了

② 对二叉树的存储，还有一个缺点：

本来顺序存储的存储密度可以达到1，因为它只存数据元素本身，存储密度很大，但对于二叉树，为了描绘出双亲和孩子的关系，必须把对应的元素放到对应的位置，导致必须空一些元素，导致了空间的浪费

后面的堆排序其实就用这种方法存取

二叉树的链式存储结构

（1）二叉链表存储（含有两个指针域的结点结构）

二叉链表存储结构

链表中的每个结点由三个域组成：数据域、左指针域、右指针域，其形式定义如下:

typedef struct BiNode {   // 结点结构
	TElemType data;
    struct BiTNode *lchild, *rchild;   // 左右孩子指针，定义是典中之典的递归定义，跟定义单链表一样
}BiNode, *BiTree; 
//为了用起来方便，又typedef，定义了一个普通的结点类型BiNode，定义了一个指向这种有三个成员的结点类型的指针*BiTree

如果操作经常要操作结点的后继（左右孩子），可以用这种存储结构

二叉链表存储

小性质喵

这里的小性质学到线索二叉树会用，这些空的指针域还可以利用起来

（2）三叉链表存储（含有三个指针域的结点结构）

三叉链表存储结构

每个结点由四个域组成：数据域、左指针域、右指针域和双亲域，

//形式定义如下:
typedef struct TriTNode {
	TElemType data;
	struct TriTNode  *lchild, *rchild; 
	struct TriTNode  *parent;  //双亲指针  
} TriTNode, *TriTree;

如果操作经常要操作结点的前驱，可以用这种存储结构

双亲指针就是指向它的前驱结点，大部分数据结构中的图都画的乱七八糟，不用管

三叉链表存储

⭐5.4 遍历二叉树

5.4.1 遍历二叉树概述

遍历定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次 (又称周游)

• ”访问”的含义很广，可以是对结点作各种处理，如：输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构，即不插入结点和删除结点

遍历目的：得到树中所有结点的一个线性排列

遍历用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

遍历方法：

• 依次遍历二叉树中的三个组成部分，便是遍历了整个二叉树
• 假设：L：遍历左子树，D：访问根结点，R：遍历右子树，则遍历整个二叉树方案共有：DLR、LDR、LRD、DRL、RDL、RLD

若规定先左后右，则只有前三种情况

DLR——先(根) 序遍历

LDR——中(根) 序遍历

LRD——后(根) 序遍历

遍历二叉树方法

5.4.1.1 先序遍历-DLR

若二叉树为空，则空操作；否则：

1. 先访问根结点
2. 再先序遍历左子树
3. 最后先序遍历右子树

访问二叉树中所有结点，且每个结点只访问一次

先序遍历-DLR例子

5.4.1.2 中序遍历-LDR

若二叉树为空，则空操作；否则：

1. 中序遍历左子树
2. 访问根结点
3. 中序遍历右子树

例子：还是上面的图：E L B A M H I D J

5.4.1.3 后序遍历-LRD

若二叉树为空，则空操作；否则：

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根结点

例子：还是上面的图：L E B M I H J D A

5.4.2 根据遍历序列确定二叉树

• 若二叉树中各结点的值均不同，则二叉树结点的先序序列、中序序列和后序序列都是唯一的

• 由中序和先序，或中序和后序遍历序列可以唯一确定一棵二叉树

  但由先序和后序遍历不能唯一确定一棵二叉树。因为对二叉树的先序和后序遍历序列来说，无法根据根结点唯一地划分出左子树和右子树的遍历序列，因此也就不能唯一确定这棵二叉树，除非二叉树为空二叉树或只有一个结点。

根据遍历序列确定二叉树

5.4.3 二叉树遍历的递归算法

实现一个算法前先确定存储结构一一二叉链表（通过指针T访问根节点）

先序遍历算法

//二叉树先序遍历，递归算法
/*
至于这里为什么是Status，我现在是这样理解的：
这里面有个状态码返回，所以void不行，一般也确实需要状态码来确定是否成功执行，所以挺有用的，想用void看下一个代码
等后面代码实现的时候验证一下~
*/
Status PreOrderTraverse(BiTree T){
    if (T == NULL) return OK;//空二叉树
    else{
        visit(T); //访问根结点，visit函数自己定义，看你的访问需求是什么
        PreOrderTraverse(T->lchild); //递归遍历左子树，递归调用进入下一层了
        PreOrderTraverse(T->rchild); //递归遍历右子树
    }
}

//这个是用void的
void preorderTraverse(BiTree T){
    if (T){
        printf(T->data);
        preorderTraverse(T->lchild);
        preorderTraverse(T->rchild);
    }
}

递归调用中具体的执行过程：

这里看弹幕讨论BiTree T 有错误，不应该带 ，这里等我写代码的时候实践一下看看

递归调用中具体的执行过程

中序遍历算法

中序遍历算法

//二叉树中序遍历，递归算法
Status InOrderTraverse(BiTree T){
    if (T == NULL) return OK;//空二叉树
    else{
        InOrderTraverse(T->lchild); //递归遍历左子树
        visit(T); //访问根结点
        InOrderTraverse(T->rchild); //递归遍历右子树
    }
}

后序遍历算法

//二叉树后序遍历，递归算法
Status PostOrderTraverse(BiTree T){
    if (T == NULL) return OK;//空二叉树
    else{
        PostOrderTraverse(T->lchild); //递归遍历左子树
        PostOrderTraverse(T->rchild); //递归遍历右子树
        visit(T); //访问根结点
    }
}

遍历算法的分析

遍历算法的分析

时间复杂度：\(O(3n)=O(n)\)

空间复杂度：\(O(n)\)，栈占用的最大辅助空间

解释：栈要记录下，虽然我路过它了，但是没有访问，记录下这个结点，访问之后就能从栈中拿出来，最坏的情况下单支的树，每个结点路过的时候都不访问，要存储n个结点

5.4.4 二叉树遍历的非递归算法

以中序遍历非递归算法为例

当遇到根的时候不能访问，先遍历左子树，遍历完左子树之后回来还能找到它，那就需要一个地方把这个根存起来

二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树

基本思想：

1. 建立一个栈
2. 根结点进栈，遍历左子树
3. 根结点出栈，输出根结点，遍历右子树

中序遍历非递归算法gif

//中序遍历非递归算法，二叉链表上实现
Status InorderTraverse(BiTree T){
    BiTree p,q;
    P=T;  //要操作的结点，指针变量p表示，初值指向根结点
    InitStack(S);  //初始化栈
    while (P||!StackEmpty(S)){
        if (P){
            Push(S, p);  //不为空，就当前根结点入栈
            q = p; 
            p = p->lchild;//然后去访问它的左子树，再进入第6句循环 
        }
      	else {  //左子树为空，但是栈还不为空
            Pop(S, q);  //将当前栈顶元素弹出
            printf("%c",q->data);
            p = q->rchild; //其实全用p就行了，感觉这里有点小复杂了 
        }
    }//while
    return OK;
}

5.4.5 二叉树的层次遍历

二叉树的层次遍历

对于一颗二叉树，从根结点开始，按从上到下、从左到右的顺序访问每一个结点。每一个结点仅仅访问一次

上图层次遍历结果为：A B C D E F G

这个算法看起来是很简单的，甚至说第一次接触二叉树我想的就是这种遍历算法，一层一层遍历不就行了，但是实现起来其实不是那么简单，或者说让我自己实现我都想不到怎么实现，是有点小巧妙在里面的

算法设计思路：使用一个队列

1. 将根结点进队
2. 队不空时循环：从队列中出列一个结点*p，访问它
   1. 若它有左孩子结点，将左孩子结点进队
   2. 若它有右孩子结点，将右孩子结点进队

二叉树的层次遍历算法

//使用队列（顺序循环队列）类型定义如下
typedef struct{
    BTNode data[MaxSize]; //存放队中元素
	int front, rear; //队头和队尾指针
}SqQueue;   //顺序循环队列类型

//二叉树层次遍历算法，这里只是类c语言，只提供思路（可能因为用的不太多？后面就不实现了

void LevelOrder(BTNode *b){
    BTNode *p;
    SqQueue *qu;
    InitQueue(qu);  //初始化队列
    enQueue(qu, b); //根结点指针进入队列
    while (!QueueEmpty(qu)){   //队不为空，则循环
        deQueue(qu, p);  //出队结点p
        printf("%c", p->data);//访问结点p
        if (p->lchild != NULL) enQueue(qu, p->lchild); //有左孩子时将其进队
        if (p->rchild != NULL) enQueue(qu, p->rchild)//有右孩子时将其进队
    }
}

层次遍历也可以用栈实现但比队列麻烦些不细说有兴趣下去了解

5.4.6 二叉树遍历算法的应用

5.4.6.1 二叉树的建立

按先序遍历序列建立二叉树的二叉链表

例：已知先序序列为ABCDEGF

（1）从键盘输入二叉树的结点信息，建立二叉树的存储结构

（2）在建立二叉树的过程中按照二叉树先序方式建立

Status CreateBiTree(BiTree &T){   //按先序次序创建二叉树
    scanf(&ch); //cin >> ch;
    if (ch=='#') T=NULL;  // *可用空格或一个特殊字符
    else {
        if (!(T=(BiTNode *)malloc(sizeof(BiTNode))))
            exit (OVERFLOW);   //c++语法:T=new BiTNode;
        T->data=ch;                 //生成根结点
        CreateBiTree(T->lchild);   //构造左子树
        CreateBiTree(T->rchild);  //构造右子树
    }
    return OK;
}     
    
//若按中序或后序呢?

二叉树的建立

5.4.6.2 复制二叉树

复制二叉树

5.4.6.3 计算二叉树的深度

如果是空树，则深度为0

否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1。

计算二叉树的深度

md全是递归，全是套娃

5.4.6.4 计算结点总数

如果是空树，则结点个数为0

否则，结点个数为左子树的结点个数+右子树的结点个数再+1.

计算结点总数

5.4.6.5 计算叶子结点数

如果是空树，则叶子结点个数为0

否则，为左子树的叶子结点个数+右子树的叶子结点个数

int LeadCount(BiTree T){
    if(T==NULL) return 0;  //如果是空树返回0
    if(T->lchild == NULL && T->rchild == NULL) return 1; //如果是叶子结点返回1
    else
        return LeafCount(T->lchild) + LeafCount(T->rchild);
}

5.5 线索二叉树

问题：为什么要研究线索二叉树？

问题：为什么要研究线索二叉树？

提出的问题：如何寻找特定遍历序列中二叉树结点的前驱和后继???

解决的方法

1、通过遍历寻找——费时间

2、再增设前驱、后继指针域——增加了存储负担

3、利用二叉链表中的空指针域（※）

回顾：二叉链表中的空指针域的数量：具有n个结点的二叉链表中，有n+1个空指针域

那么能不能把这n+1个空指针域利用起来呢？答案是肯定的

利用二叉链表中的空指针域

• 如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱
• 如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继
• 这种改变指向的指针称为“线索“

加上了线索的二叉树称为线索二叉树 (Threaded Binary Tree)

对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化

中序线索二叉树例子

为区分Irchid和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域 ltag 和 rtag ，并约定如下：

线索二叉树结点结构

typedef struct BiThrNode {
    int data;
    int LTag,RTag; //左右标志
    struct BiThrNode *lchild, *rchild;  //左右孩子指针
                                      
}BiThrNode, *BiThrTree;

线序线索二叉树

后序线索二叉树

中序线索二叉树

为了避免悬空状态，增设一个头结点，让操作更加方便

增设了一个头结点thrt：

ltag=0，lchild指向根结点

rtag=1，rchild指向遍历序列中最后一个结点

遍历序列中第一个结点的lc域和最后一个结点的rc域都指向头结点

中序线索二叉树

5.6 树和森林

由二叉树推而广之，研究一下树和森林

树和森林

5.6.1 树的存储结构

1、双亲表示法：

用一个数组连续存储结点,各结点中附设一个指示其双亲的结点位置(下标).

参考：

数据结构：树(Tree)【详解】_数据结构 树_UniqueUnit的博客-CSDN博客