[数据结构与算法] 我的数据结构与算法「树形结构」

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 我的数据结构与算法「树形结构」 -> 正文阅读

[数据结构与算法]我的数据结构与算法「树形结构」

文章目录

- 树形结构

树形结构

树形结构是一层次的嵌套结构，数据元素之间存在着一对多的树形关系的数据结构，多棵树的集合是森林，树形结构中最简单最重要的是二叉树

一般树

一般树即树是 $n\;(n\geq0)$ 个结点的有限集。当 $n = 0$ 时，称为空树；任意一棵非空树有且仅有一个特定的称为根的结点，当 $n > 1$ 时，其余结点可分为 $m\;(m>0)$ 个互不相交的有限集 $T_1,T_2,\cdots,T_m$ ，其中每个集合本身又是一棵树，并且称为根的子树

树的定义是递归的（树的定义中又用到了其自身）即树是递归的数据结构。树是一种非线性逻辑结构，根结点没有前驱，除根结点外的所有结点有且只有一个前驱，树中所有结点可以有零个或多个后继

树适合表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点（即父结点）有直接关系，根结点没有直接上层结点，因此在 $n$ 个结点的树中有 $n ? 1$ 条边。而树中每个结点与其下一层的零个或多个结点（其子结点）有直接关系

考虑结点 $K$ 。根 $A$ 到结点 $K$ 的唯一路径上的任意结点，称为结点 $K$ 的祖先。如结点 $B$ 是结点 $K$ 的祖先，而结点 $K$ 是结点 $B$ 的子孙。路径上最接近结点 $K$ 的结点 $E$ 称为 $K$ 的双亲，而 $K$ 为结点 $E$ 的孩子。根 $A$ 是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点 $K$ 和结点 $L$ 有相同的双亲 $E$ ，即 $K$ 和 $L$ 为兄弟
树中一个结点的孩子个数称为该结点的度，树中结点的最大的度称为树的度。如结点 $B$ 的度为 $2$ ，结点 $D$ 的度为 $3$ ，树的度为 $3$ ；度大于 $0$ 的结点称为分支结点（又称非终端结点）；度为 $0$ 即没有子结点的结点，称为叶子结点（又称终端结点）。分支结点的分支数就是其度
结点的深度、高度和层次。结点的层次从树根开始定义，根结点为第 $1$ 层，它的子结点为第 $2$ 层，以此类推。双亲在同一层的结点互为堂兄弟，结点 $G$ 与 $E, F, H, I, J$ 互为堂兄弟

结点的深度是从根结点开始自顶向下逐层累加的

结点的高度是从叶结点开始自底向上逐层累加的

树的高度（深度）是树中结点的最大层数
有序树与无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。假设为有序树，若将子结点位置互换，则变成一棵不同的树
路径与路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数，由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径
树的基本性质

树中的结点数等于所有结点的度之和加 $1$

度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点其中 $i\geq1$

高度为 $h$ 的 $m$ 叉树至多有 $(m^h-1)\over(m一1)$ 个结点

具有 $n$ 个结点的 $m$ 叉树的最小高度为 $\lceil log_m[n(m-1)+1]\rceil$
树的顺序存储结构

双亲表示法。用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点的双亲结点在数组中的位置
树的链式存储结构

孩子表示法。把每个结点的孩子结点排列起来存储成一个单链表。所以 $n$ 个结点就有 $n$ 个链表，如果是叶子结点，那这个结点的孩子单链表就是空的，然后 $n$ 个单链表的的头指针又存储在一个顺序表（数组）中

孩子兄弟表示法。顾名思义就是要存储子结点与子结点的兄弟，具体来说，就是设置两个指针，分别指向该结点的第一个子结点和这个子结点的兄弟结点

森林是 $m\;(m\geq0)$ 棵互不相交的树的集合。森林的概念与树的概念十分相近，只要把树的根结点删去其子树就成了森林。反之，只要给 $m$ 棵树一个共同的结点，并把这 $m$ 棵树作为该结点的孩子，森林就变成了树

二叉树

二叉树是有序树，特点是每个结点至多只有两个子结点即子树（二叉树中不存在度大于 2 的结点）并且二叉树的子树有左右之分，其次序不能任意频倒。二叉树由一个根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树又分别是一棵二叉树。二叉树是 $n\;(n\geq0)$ 个结点的有限集合，空二叉树 $n = 0$

二叉树有五种基本形态

空的，没有结点
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树

二叉树与度为 $2$ 的有序树不同

二叉树可以为空而度为 $2$ 的有序树至少有 $3$ 个结点
度为 $2$ 的有序树的子结点的左右次序是相对于另一子结点而言的，若某个结点只有一个子结点，则这个子结点就无须区分左右次序，而二叉树的结点无论其子结点是否为 $2$ 均需事先定义左右次序，即二叉树的结点次序不是相对于另一结点而言，而是事先确定的

特殊二叉树

斜树

左斜树中所有结点都只有左子树

右斜树中所有结点都只有右子树
满二叉树

一棵高度为 $h$ ，且含有 $2^h-1$ 个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为 $2$ 。可以对满二叉树按层序编号，约定编号从根结点（根结点编号为 $1$ ）起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为 $i$ 的结点，若有双亲，则其双亲为 $\lfloor {i\over2} \rfloor$ ，若有左子结点则为 $2 i$ ，若有右子结点则为 $2 i + 1$
完全二叉树

高度为 $h$ 、 $n$ 个结点的二叉树，当且仅当其每个结点都与高度为 $h$ 的满二又树中编号为 $1 ～ n$ 的结点一一对应时，称为完全二叉树，若 $i\leq \lfloor \frac{n}{2}\rfloor$ ，则结点 $i$ 为分支结点，否则为叶子结点

只可能有一个度为 $1$ 的结点，且该结点只有左孩子而无右孩子。若 $n$ 为奇数，则每个分支结点都有左孩子和右孩子；若 $n$ 为偶数，则编号最大的分支结点（编号为 $n\over2$ ）只有左孩子，没有右孩子，其余分支结点左、右孩子都有
二叉排序树

左子树上所有结点的值均小于根结点的值；右子树上的所有结点的值均大于根结点的值；左子树和右子树又各是一棵二叉排序树
平衡二叉树

树的任一结点的左子树和右子树的深度之差不超过 $1$

二叉树的性质

非空二叉树上叶子结点数等于度为 $2$ 的结点数加 $1$ ，即 $n_0=n_2+1$
非空二叉树上第 $K$ 层上至多有 $2^k?1$ 个结点 $(k \geq 1)$
高度为 $h$ 的二叉树至多有 $2^h-1$ 个结点 $(h \geq 1)$
具有 $n$ 个 $(n > 0)$ 结点的完全二叉树的高度为 $\lceil log_2(n+1)\rceil$ 或 $\lfloor log_2n\rfloor+1$

二叉树的存储结构

有一棵二叉树，高为 $4$ ，结点数为 $6$ 各数据元素分别为 $123456$

顺序存储

二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点
链式存储
二叉树每个结点最多两个孩子，所以设计二叉树的结点结构时考虑两个指针指向两个子结点

定义二叉树数据结构
```
typedef struct BiTNode{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
```

二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，进而便于遍历。由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 $N$ 、左子树 $L$ 和右子树 $R$ 的访问顺序。按照先遍历左子树再遍历右子树的原则，对于孩子兄弟表示法二叉树以二叉链表存储，常见的遍历次序有先序 $(N L R)$ 、中序 $(I N R)$ 和后序 $(I R N)$ 等算法，其中“序”是指访问根结点相对于左子结点与右子结点的顺序，以及层次遍历算法

先序遍历

如果二叉树不为空，则按照从上往下从左往右的顺序先访问树与子树根结点，接着遍历访问左子树，再遍历访问右子树

递归方法

void PreOrder(BiTree T){
if(T!=NULL){
 visit(T);  // 访问根结点
 PreOrder(T->lchild);  // 找到全部的左结点
 PreOrder(T->rchild);  // 找到全部的右结点
}
}

void visit(BiTree T){
printf("%c", T->data);
}

非递归方法

void PreOrderTraverse(BiTree T){
initStack(S);  // 开辟存储指针的栈空间
BiTree P = T;
while(P || !isEmpty(S)){
 while(P){
   visit(P);  // 根结点到左结点依次压栈
   Push(S, P);
   P = P->lchild;
 }
 if(!isEmpty(S)){
   P = Pop(S);  // 最后一层的右叶子结点依次出栈
   P = P->rchild;
 }
}
}

遍历得到的结点序列为 $124635$

中序遍历

如果二叉树不为空，则按照从上往下从左往右的顺序先访问左子树，接着访问根结点，再遍历访问右子树

递归方法
void InOrder(BiTree T){
if(T!=NULL){
 InOrder(T->lchild);  // 找到全部的左结点
 visit(T);  // 访问根结点
 InOrder(T->rchild);  // 找到全部的右结点
}
}
非递归方法
void InOrderTraverse(BiTree T){
initStack(S);
BiTree P = T;
while(P || !isEmpty(S)){
 while(P){
   Push(S, P);
   P = P->lchild;
 }
 if(!isEmpty(S)){
   P = Pop(S);
   visit(P);
   P = P->rchild;
 }
}
}
遍历得到的结点序列为 $264135$ ，直观来看，就是将二叉树的结点投影到一条水平的坐标上

后序遍历

如果二叉树不为空，则按照从下往上从左往右的顺序先访问左子树，接着后序遍历右子树，再访问根结点

递归方法

void PostOrder(BiTree T){
if(T!=NULL){
 PostOrder(T->lchild);  // 找到全部的左结点
 PostOrder(T->rchild);  // 找到全部的右结点
 visit(T);  // 访问根结点
}
}

非递归方法

void PostTraverse(BiTree T){
initStack(S);
BiTree P = T, R = NULL;
while(P || !isEmpty(S)){
 // 从左子树的左叶子结点入栈
 if(P){
   Push(S, P);
   P = P->lchild;
 }
 else{
   GetTop(S, P);  // 取顶栈
   if(P->rchild && P->rchild != R){
     P = P->rchild;
   }
   else{
     P = Pop(S);
   	 visit(P);
     R = P;
     P = NULL;
   }
 }
}
}

遍历得到的结点序列为 $642531$

递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是 $O (n)$ 。在递归遍历中，递归工作栈的栈深怡好为树的深度，所以在最坏情况下，二叉树是有 $n$ 个结点且深度为 $n$ 的单支树，遍历算法的空间复杂度为 $O (n)$ 。实际上，访问一个结点 $p$ 时，栈中结点恰好是 $p$ 结点的所有祖先，从栈底到栈顶结点再加上 $p$ 结点，刚好构成从根结点到 $p$ 结点的一条路径。在很多算法设计中都可以利用这一思路来求解，如求根到某结点的路径、求两个结点的最近公共祖先等

层次遍历
如果二叉树不为空，则从树的第一层开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问

进行层次遍历需要使用队列，先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队，若它有右子树，则将右子树根结点入队，然后出队，访问出队结点??如此反复，直至队列为空
```
void LevelOrder(BiTree T){
  initQueue(Q);
  BiTree P;
  enQueue(Q, P);  // 根结点入队
  while(!isEmpty(Q)){
    deQueue(Q, P);  // 队头结点出队
    visit(P);  // 访问出队结点
    if(P->lchild != NULL)
      enQueue(Q, P->lchild);  // 左子树根结点入队
    if(P->rchild != NULL)
			enQueue(Q, P->rchild);  // 右子树根结点入队
  }
}
```
遍历得到的结点序列为 $123456$

线索二叉树

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（除第一个和最后一个结点外）都有一个直接前驱和直接后继。传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。

例如 $n$ 个结点的二叉树，每个结点都有指向左右孩子的结点指针，所以一共有 $2 n$ 个指针，而 $n$ 个结点的二叉
树一共有 $n ? 1$ 条分支，也即存在 $2 n ? (n ? 1) = n + 1$ 个空指针，可以利用空余的指针实现指向结点前驱与后继的指针即线索，具有线索的二叉树就称为线索二叉树

规定无左子树，令 $l c h i l d$ 指向其前驱结点，无右子树，令 $r c h i l d$ 指向其后继结点，还需增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继）

$ltag=\begin{cases} 0,\quad lchild\;域指示结点的左孩子\\ 1,\quad lchild\;域指示结点的前驱 \end{cases}\\ rtag=\begin{cases} 0,\quad rchild\;域指示结点的右孩子\\ 1,\quad rchild\;域指示结点的后驱 \end{cases}$

typedef struct ThreadNode{
	int data;
	struct ThreadNode *lchild, *rchild;
  int ltag, rtag;
}ThreadNode, *ThreadTree;

二叉排序树

二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有以下性质的二叉树

若左子树不空，则左子树上所有结点的值均小于它的根结点的值
若右子树不空，则右子树上所有结点的值均大于它的根结点的值
它的左右子树也是一棵二叉排序树

由于二叉排序树的特点（左子树<根结点<右子树），所以每次查找一个关键字，需要先和根结点进行较，如果这个关键字小于根结点的值，则再到这个根结点的左子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。如果这个关键字大于根结点的值，则再到这个根结点的右子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，如果是空指针，表示查找失败

查找关键字

递归方法

BSTNode *BST_Search（BiTree *t, int key)
{
  if(t==NULL) return NULL;
  else
  {
    if(t->key==key) return t;
    else if(key<t->key) return BST_Search(t->lchild, key);
    sles return BST_Search(t->rchild, key);
  }
}

非递归方法

BSTNode *BST_Search（BiTree *t, int key)
{
  BiTree *p = t;
  while(p!=NULL && key!=p->data)
  {
    if(key<p->data) p=p->lchild;
    else p=p->rchild;
  }
  return p;
}

插入关键字

二叉排序树为空树则直接插入新结点，树非空则检查是否存在关键字重复的结点，存在则插入失败，不存在则检查根结点的值和待插入关键字值的大小关系递归插入左右子树
int BST_Insert(BiTree &t, int k)
{
  if(t==NULL)
  {
    t=(BiTree)malloc(sizeof(BSTNode));
    t->key=k;
    t->lchild=t->rchild=NULL;
    return 1;
  }
  else if(k==t->key) return 0;
  else if(k<t->key) return BST_Insert(t->lchild, k);
  else return BST_Insert(t->rchild, k);
}

构造二叉排序树

void Creat_BST(BiTree &t, int str[], int n)
{
  t=NULL;
  int i=0;
  while(i<n)
  {
    BST_Insert(t, str[i]);
    i++;
  }
}

删除关键字

删除的是叶子结点则直接删去该结点即可，删除的是仅有左子树或右子树的结点则直接子承父业，删除的是有左右子树的结点则找到待删除结点的直接前驱或直接后继结点，用该结点来替代待删除结点

从查找过程看，二叉排序树与二分查找相似。就平均时间性能而言，二叉排序树上的查找和二分查找相近，但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键宇其插入顺序不同可能生成不同的二叉排序树，在最坏情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数 $n$ ，查找的时间复杂度是 $O (n)$

平衡二叉树

平衡二叉树是特殊的二叉排序树，要求左右子树的高度之差绝对值不超过 $1$ ，且左右子树也是一棵平衡二叉树，含有 $n$ 个结点平衡二叉树的最大深度为 $O(log_2n)$

平衡因子

结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是 $? 1$ 、 $0$ 或 $1$
平衡调整

平衡二叉树的建立过程和二叉排序树的建立过程是相似的，都是从一棵空树开始陆续插入结点。不同的地方在于对于平衡二叉树的建立过程中，需要进行平衡调整，防止插入结点破坏树的平衡性

$L L$ 平衡旋转（左孩子的左子树上插入结点导致）
最小不平衡子树根结点的平衡因子为 2>0，它的左孩子结点平衡因子为1>0，两个都大于0，所以直接右旋就可以调整，即该结点的根结点变成该结点的右子树的根结点，该结点的原右子结点变成此时右子结点的左子结点，简称正则右旋

$R R$ 平衡旋转（右孩子的右子树上插入结点导致）
最小不平衡子树根结点的平衡因子为 $? 2 < 0$ ，它的右孩子结点平衡因子为 $? 1 < 0$ ，两个都小于 $0$ ，所以直接左旋就可以调整，即该结点的根结点变成该结点的左子树的根结点，该结点的原左子结点变成此时左子结点的右子结点，简称负则左旋

$L R$ 调整（左孩子的右子树上插入结点导致）与 $R L$ 调整（右孩子的左子树上插入结点导致），先局部转换为 $L L$ 或 $R R$ ，再进行调整即可

哈夫曼树

哈夫曼树可以实现哈夫曼编码，令左子树为边值 $0$ ，右子树边值为 $1$ ，从哈夫曼树的根结点顺着边到目标子结点的边的序列值就是哈夫曼编码

哈夫曼树的定义

第一，我们先得到全部数据元素的权重集合（可用每个数据元素的频率），其中的结点分别作为仅含一个结点的二叉树，构成森林 $f$
第二，构造一个新结点，并从 $f$ 中选取根结点权值最小的两棵树作为新结点的左（最小）、右（次小）子树，并且将新结点的权值设为左、右子树的根结点的权值之和
第三，从 $f$ 中删除刚才选出的两棵树，同时将新得到的树加入 $f$ 中
第四，重复第一与第二直至 $f$ 中只剩一棵树为止

哈夫曼树的实例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
	int data; // data域存储权值
	int parent, lchild, rchild; // 双亲与孩子
} HTNode, *HuffmanTree;

void InitHuffmanTree(HuffmanTree H, int weight, int parent, int lchild, int rchild)
{
	H->lchild = lchild;
	H->rchild = rchild;
	H->parent = parent;
	H->data = weight;
}

void CreateHuffmanTree(HuffmanTree &HT, int n, int *W)
{
	// 叶子结点的初始化，相当于n棵树，每颗树只有一个结点，那么最后构造过程总的结点个数为：2*n-1
	// n-1+n = 2*n-1

	HT = (HuffmanTree)malloc((2 * n - 1) * sizeof(HTNode)); // n个叶子结点的哈夫曼树结点是2n-1;
	for (int i = 0; i < n; i++)
	{
		InitHuffmanTree(HT + i, W[i], -1, -1, -1); // 初始化-1
	}
	// 开始寻找最小的两个叶子结点，构造哈夫曼树
	for (int i = n; i < 2 * n - 1; i++)
	{								   // 我们构造n-1个度为2的结点
		int min1 = 65522, min2 = min1; // 这里的两个数分别代表第一小，第二小
		int x1 = -1, x2 = -1;		   // 用来记录下标
		for (int j = 0; j < i; j++)
		{
			if ((HT + j)->parent == -1) //表示叶子结点没有父母
			{
				if ((HT + j)->data < min1)
				{
					min2 = min1;
					min1 = (HT + j)->data;
					x2 = x1;
					x1 = j;
				}
				else if ((HT + j)->data < min2)
				{
					min2 = (HT + j)->data;
					x2 = j;
				}
			}
		}
		// 合并两个叶子，让他们有同一个双亲
		(HT + x1)->parent = i;
		(HT + x2)->parent = i;
		// 然后我们让HT[i]指向这两个孩子，为了后来的逆序哈夫曼编码

		InitHuffmanTree(HT + i, min2 + min1, -1, x1, x2); // 父结点构造
	}
}

void HuffmanTreeCode(HuffmanTree HT, char *str, int n, int path, int &e)
{
	int i = 0, j = 0, m = 0;
	int child = path; // 假设我们现在在叶子结点为child索引的地方，如1

	int parent = (HT + child)->parent; // 获取第一个叶子结点的父节点 的值
	// printf("leafe node is:%d \n",(HT+child)->data);

	// 开始逆序寻找根节点，及生成编码
	for (i = n - 1; parent != -1; i--) // 当前结点不是根结点 ,逆序
		if ((HT + parent)->lchild == child)
		{ // 他的双亲指向的左孩子是不是我们当前遍历的这个叶子
			str[j++] = '0';
			child = parent; // 此时parent！=-1 ，表示还有父节点
			parent = (HT + child)->parent;
		}
		else
		{
			str[j++] = '1'; // 实现编码
			child = parent;
			parent = (HT + child)->parent;
		}
	e = j; // 表示一个叶子结点的编码结束
}

int main()
{
	int i, n;
	int *w, e;

	HuffmanTree HT;
	printf("Node Number:");
	scanf("%d", &n);					// 权值个数
	w = (int *)malloc(n * sizeof(int)); // 权值数组
	printf("Input weights:");
	for (i = 0; i < n; i++) // 录入权值
		scanf("%d", &w[i]);
	CreateHuffmanTree(HT, n, w);
	printf("the first node is:%d\n",HT->data);
	printf("create sussessfully\n");

	char str[n];
	for (int k = 0; k < n; k++)
	{
		HuffmanTreeCode(HT, str, n, k, e);
		for (int j = e - 1; j >= 0; j--)
			printf("%c", str[j]);
		printf("\n");
	}
	free(HT);
	return 0;
}