数据结构--树

树的基本概念

• 树：一个或多个节点的有限集合。
  存在一个称为根的特定节点，其余的节点被分为n个互不相交的集合T1，T2，…，Tn，其中的每一个集合都是一棵树。T1，T2，…，Tn称为根节点的子树。
  

• 结点：树中的一个独立单元

• 结点的度：结点拥有的子树数称为结点的度。

• 树的度：树内各结点度的最大值。

• 叶子：度为0的节点或终结结点。

• 非叶子结点（非终端结点）：度不为0的结点。

• 双亲，孩子，兄弟，堂兄弟结点：

  • 1.结点的子树的根称为该结点的孩子。
  • 2.该结点称为孩子的双亲。
  • 3.同一双亲结点的所有子节点互称为兄弟节点。（eg:图6-1中结点B、C、D是兄弟节点，E、F是兄弟结点）
  • 4.双亲结点在同一层上的所有结点互称为堂兄弟结点（图6-1中结点EFGHIJ互称为堂兄弟结点）

• 层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。以此类推。

• 层次路径：从根节点开始，到达某结点p所经过的所有结点称为结点p的层次路径。（有且仅有一条）

• 祖先(ancester)：结点p的层次路径上的所有结点(p除外).

• 子孙节点(descent)：以某一结点为根的子树中的任意结点称为该结点的子孙结点

• 树的深度（depth）：树中结点的最大层次，即树总共的层数。也称为树的高度

• 有序树和无序树：对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树为有序树，否则称为无序树。

• 森林（forest）：是m(m>=0)课互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。

• 二叉树：二叉树(Binary tree)是n(n>0)个结点的有限集合。
  若n=0时称为空树，否则:
  (1)有且只有一个特殊的称为树的根(Root)结点
  (2)若n>1时，其余的结点被分成为二个互不相交的子集T1，T2分别称之为左、右子树，并且左、右子树又都是二叉树。
  由此可知，二叉树的定义是递归的。
  

• 满二叉树：深度为k且含有2^k-1个结点的二叉树

  • 1.所有的叶子节点只能出现在最后一层
  • 2.对于同样深度的二叉树，满二叉树的节点个数最多，叶子结点的数量也是最多的。
  • 3.如果对满二叉树进行编号，根结点从1开始，从上到下从左到右，对于编号为i的结点，若存在左孩子，则左孩子的编号为2i，右孩子为2i+1

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

  • 1.叶子结点只可能在层数最大的两层上出现
  • 2.对任意结点，若其右分支下的子孙的最大层次为i，则其左分支下的子孙的最大层次必为i或i+1

• 没有左子树，不能有右子树，上一层没有铺满，不能有下一层。

• 线索化：利用叶节点的空余空间记录前驱、后继。

• 线索二叉树:按照某种次序遍历，根据遍历的顺序加上线索的二叉树。

• 结点的权：在实际应用中，给树种的结点赋予代表某种含义的数值

• 结点的带权路径长度：从该节点到树根之间的路径长度与该节点权的乘积

• 树的带权路径长度（WPL）：树中所有节点的带权路径长度之和

• 哈夫曼树：带权路径长度WPL最小的二叉树称为哈夫曼树。
  哈夫曼树的性质

  • 1.哈夫曼树没有度为1的结点
  • 2.树中两个权值最小的节点一定是兄弟结点
  • 3.树中任一非叶结点的权值一定不小于下一层任一结点的权值

• 哈夫曼编码：左0右1，按在哈夫曼树中的路径写出的编码

1. 生成树 (Spanning Tree) 的定义：

生成树 是一个图的子图，包含图中的所有节点，并且是一个树结构。生成树必须满足以下条件：

• 包含所有节点：生成树的节点数与原图相同。
• 无环性：生成树不能包含环。
• 连通性：生成树中的每对节点之间都可以通过生成树中的边连通。
• 边数：对于一个有 (V) 个节点的图，生成树的边数为 (V - 1)。

一个图可以有多个生成树，因为可以从图中选择不同的边组合来构成生成树。

2. 最小生成树 (Minimum Spanning Tree, MST) 的定义：

最小生成树 是一个特殊的生成树，除了满足生成树的基本条件外，它还要求所有边的权重之和最小。换句话说，最小生成树是所有生成树中，边权和最小的那一棵生成树。

最小生成树的构建通常依赖于图中边的权重，而生成树只是关心是否覆盖所有节点且不形成环。

3. 生成树与最小生成树的关系：

• 每个最小生成树都是生成树：最小生成树首先满足生成树的所有基本要求，因为它是一个包含所有节点的连通无环子图。但它进一步满足了最小生成树的特性，即边的总权重最小。

• 每个生成树不一定是最小生成树：虽然所有的最小生成树都是生成树，但并非所有的生成树都是最小生成树。生成树可以有多种形式，不一定考虑边的权重，因此可能有一些生成树的边权和比最小生成树要大。

4. 图的生成树和最小生成树的差异：

特性	生成树 (Spanning Tree)	最小生成树 (MST)
定义	包含所有节点且无环的子图，边数为 (V-1)	除了是生成树，还要求边权和最小
边权要求	不考虑边的权重	边的权重和最小
生成方式	可以随意选择边，不考虑权重	需要选择权重最小的边
多个可能性	对于一个图，生成树可能有多个	对于一个图，最小生成树是唯一的（假设没有相同权重的边）
示例	图中任意选择不形成环的 (V-1) 条边	图中选择边权和最小的边，确保没有环且连通

6. 总结：

• 生成树 是一个无环且连通的子图，包含原图中的所有节点，边数为 (V-1)。
• 最小生成树 是生成树的一种特例，它要求所有边的权重之和最小。
• 每个最小生成树都是生成树，但不是所有生成树都是最小生成树。
• 求解最小生成树的常见算法有 Kruskal 算法 和 Prim 算法，它们都是通过贪心策略选择权重最小的边来构建最小生成树。

树的表示形式

1.倒悬树，最常用的表示形式（eg:图6-1）
2.嵌套集合，是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。（图6-2(a)是图6-1(b)树的嵌套集合形式）
3.广义表形式：eg:图6-2(b)
4.凹入法表示形式

树转化为二叉树：
1.加线，在所有兄弟结点之间加一条线
2.去线，对树中的每一个结点，只保留
它与第一个孩子结点的连线，删除它与
其它孩子结点之间的连线.
3.层次调整，以树的根结点为轴
心，将整棵数顺时针旋转一定角
度，使之层次分明.注意第一个
孩子是二叉树结点的左孩子.兄
弟转过来的孩子是结点的右孩
子.
这样转换后的二叉树的特点是：
1.二叉树的根结点没有右子树，只有左子树
2.左子结点仍然是原来树中相应结点的左子结点，而所有沿右链往下的右子节点均是原来树中该结点的兄弟节点。

二叉树转化为树
1.加线，若某个结点的左孩子存在，则
将这个左孩子的所有右孩子结点都作为
此结点的孩子，将该结点与这些右孩子
结点用线连起来.
2.去线，删除二叉树中所有结点与其右
孩子结点的连线
3.调整，转一下



森林转换成二叉树
当一半的树转换成二叉树后，二叉树的右子树必为空。若把森林中的第二课树（转换成二叉树后）的根结点作为第一棵树（二叉树）的根结点的兄弟结点，则可以导出森林转二叉树的方法。
步骤：
1.将所有树转化成二叉树
2.按照给出的森林中树的次序，从最后一颗二叉树开始，每棵二叉树作为前一颗二叉树的根结点的右子树，依此类推，则第一颗二叉树的根结点就是转换后生成的二叉树的根结点。

二叉树转森林

树的遍历

树：先根遍历 后根遍历
二叉树：先序遍历 中序遍历 后序遍历
森林：前序遍历 后序遍历

树的性质

1.树中所有节点数等于所有节点的度数之和加1
2.对于度为m的树，第i层上最多有m^(i-1)个节点
3.性质三:对于高度为 h，度为 m 的树，最多有(m^h-1)/(m-1)个结点

二叉树的性质

1.二叉树的第i层最多有2^(i-1)个节点
2.深度为k的二叉树最多有2^k-1个节点
3.对于任何非空的二叉树T，如果叶子节点的个数为n0，而度为2的节点数为n2，则n0=n2+1
性质3证明:设二叉树中度为1的结点数为m，二叉树中总结点数为N，因为二又树中所有结点均小于或等于2，则有:N=n0+n1+n2
再看二叉树中的分支数
除根结点外，其余每个结点都有唯一的一个进入分支而所有这些分支都是由度为1和2的结点射出的。设B为二叉树中的分支总数，则有:N=B+1
∴B=n1+2xn2
∴N=B+1=n+2xn2+1
∴n0+n1+n2=n1+2xn2+1
即n0=n2+1

完全二叉树的性质

1:具有n个结点的完全二叉树的深度为⌊log2(n+1)⌋
2:如果对一棵有n个结点的完全二叉树(其深度为⌊log2(n+1)⌋的结点按层序编号(从第1层到第⌊log2(n+1)⌋，每层左到右)，则对任一结点
(1≤i≤n)，以下结论成立。
(1)如果i=1，则结点i是二叉树的根，无双亲;如果结点i>1则其双亲是结点 ⌊i/2⌋
(2)如果 2i>n，则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i
(3)如果 2i+1>n，则结点i无右孩子;否则其右孩子的结点是 2i+1。

二叉树的存储结构

1.顺序存储结构

用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二又树的数据元素。
对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中，如图6-6©所示。
对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中，如图6-6(d)所示

最坏的情况下，一个深度为k且只有k个结点的单支树需要长度为2^k-1的一维数组。
顺序结构不适合存储非完全二叉树，顺序存储结构并不适合用于存储非完全二叉树，原因在于其存储方式是基于节点的逻辑位置（下标计算）进行的，而非完全二叉树在节点的分布上是不规则的，存在很多空闲位置，空闲位置得用无效标识符填充，不填充没法遍历。如果使用顺序存储，空闲位置会浪费内存，从而导致空间的浪费和不必要的复杂性。

2.链式存储结构

结点的类型及其定义
1.二叉链表结点。有三个域:一个数据域，两个分别指向左右子结点的指针域，如图6-7(a)所示。
2. 三叉链表结点。除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点，如图6-7(b)所示:
链式存储结构是最好用最方便最常用的存储树的方式。


链式存储结构非常适合用于存储任何类型的二叉树（包括非完全二叉树），因为它允许节点动态分配内存，并通过指针灵活地连接树的各个节点。
递归遍历：对于链式存储的树结构，递归遍历（前序、中序、后序）非常自然且简洁。每次遍历只需访问当前节点并递归地遍历其子节点。

遍历二叉树

遍历二叉树（Traversing Binary Tree）：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次
若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案:DLR、LDR、LRD、DRL、RDL、RLD。若规定先左后右，则只有前三种情况三种情况，分别是:
DLR–先(根)序遍历。
LDR–中(根)序遍历。
LRD–后(根)序遍历

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
1.递归算法：利用单线程程序执行的机理，由计算机自动完成压栈出栈的操作。

void PreorderTraverse(BTNode *T)
{if(T!=NULL){printf("%d",T->data);PreorderTraverse("%d",T->Lchild);PreorderTraverse("%d",T->Rchild);}
}

完整代码实现示例

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构
typedef struct TreeNode {int data;           // 数据域struct TreeNode* left;  // 左子节点struct TreeNode* right; // 右子节点
} TreeNode;// 创建新节点
TreeNode* createNode(int value) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));newNode->data = value;newNode->left = newNode->right = NULL;return newNode;
}// 前序遍历（递归）
void preOrder(TreeNode* root) {if (root == NULL) return;printf("%d ", root->data);  // 访问根节点preOrder(root->left);       // 递归遍历左子树preOrder(root->right);      // 递归遍历右子树
}// 中序遍历（递归）
void inOrder(TreeNode* root) {if (root == NULL) return;inOrder(root->left);        // 递归遍历左子树printf("%d ", root->data);  // 访问根节点inOrder(root->right);       // 递归遍历右子树
}// 后序遍历（递归）
void postOrder(TreeNode* root) {if (root == NULL) return;postOrder(root->left);      // 递归遍历左子树postOrder(root->right);     // 递归遍历右子树printf("%d ", root->data);  // 访问根节点
}// 主函数
int main() {// 创建节点并构建树TreeNode* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);root->right->right = createNode(6);// 前序遍历printf("前序遍历: ");preOrder(root);printf("\n");// 中序遍历printf("中序遍历: ");inOrder(root);printf("\n");// 后序遍历printf("后序遍历: ");postOrder(root);printf("\n");return 0;
}//    1//   / \//  2   3// / \    \//4   5    6

2.非递归算法：自己完成栈的操作
前序遍历的非递归算法思路：设T是指向二叉树根结点的指针变量，若二叉树为空，则返回;否则，令p=T;
(1)访问p所指向的结点;
(2)q=p->Rchild，若q不为空，则q进栈;(右边先进)
(3)p=p->Lchild ，若p不为空，转(1)，否则转(4)
(4)退栈到p，转(1)，直到栈空为止。
中序遍历的非递归算法
设T是指向二叉树根结点的指针变量，若二叉树为空，则返回;否则，令p=T
(1)若p不为空，p进栈，p=p->Lchild
(2)否则(即p为空)，退栈到p，访问p所指向的结点
(3)p=p->Rchild，转(1)直到栈空为止。
后序遍历的非递归算法：
在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此根结点还需再次进栈，当其
右子树遍历完后再退栈到到该根结点时，才能被访问。

//非递归实现树的遍历
#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点
typedef struct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;
} TreeNode;// 栈的结构
typedef struct Stack {TreeNode* nodes[100];int top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = -1;
}// 入栈
void push(Stack* stack, TreeNode* node) {stack->nodes[++(stack->top)] = node;
}// 出栈
TreeNode* pop(Stack* stack) {return stack->nodes[(stack->top)--];
}// 栈顶元素
TreeNode* peek(Stack* stack) {return stack->nodes[stack->top];
}// 判断栈是否为空
int isEmpty(Stack* stack) {return stack->top == -1;
}// 创建新节点
TreeNode* createNode(int value) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));newNode->data = value;newNode->left = newNode->right = NULL;return newNode;
}// 非递归前序遍历
void preOrder(TreeNode* root) {if (root == NULL) return;Stack stack;initStack(&stack);push(&stack, root);while (!isEmpty(&stack)) {TreeNode* node = pop(&stack);printf("%d ", node->data);// 先右子树后左子树入栈，保证左子树先被访问if (node->right) push(&stack, node->right);if (node->left) push(&stack, node->left);}
}// 非递归中序遍历
void inOrder(TreeNode* root) {Stack stack;initStack(&stack);TreeNode* curr = root;while (curr != NULL || !isEmpty(&stack)) {// 遍历到最左子节点while (curr != NULL) {push(&stack, curr);curr = curr->left;}// 当前节点为空，说明已经遍历完左子树curr = pop(&stack);printf("%d ", curr->data);// 遍历右子树curr = curr->right;}
}// 非递归后序遍历
void postOrder(TreeNode* root) {if (root == NULL) return;Stack stack1, stack2;initStack(&stack1);initStack(&stack2);push(&stack1, root);while (!isEmpty(&stack1)) {TreeNode* node = pop(&stack1);push(&stack2, node);// 先左子树后右子树入栈if (node->left) push(&stack1, node->left);if (node->right) push(&stack1, node->right);}// stack2 中的节点顺序就是后序遍历的顺序while (!isEmpty(&stack2)) {TreeNode* node = pop(&stack2);printf("%d ", node->data);}
}// 主函数
int main() {// 创建二叉树TreeNode* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);root->right->right = createNode(6);// 非递归前序遍历printf("非递归前序遍历: ");preOrder(root);printf("\n");// 非递归中序遍历printf("非递归中序遍历: ");inOrder(root);printf("\n");// 非递归后序遍历printf("非递归后序遍历: ");postOrder(root);printf("\n");return 0;
}//    1//   / \//  2   3// / \    \//4   5    6

3.层次遍历
层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。
为保证是按层次遍历，必须设置一个队列，初始化时为空。
设T是指向根结点的指针变量，层次遍历非递归算法是:若二叉树为空，则返回;否则，令p=T，P入队;
(1)队首元素出队到p
(2)访问p所指向的结点;
(3)将p所指向的结点的左、右子结点依次入队。直到队空为止。

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点
typedef struct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;
} TreeNode;// 定义队列结构
typedef struct Queue {TreeNode* nodes[100];int front, rear;
} Queue;// 初始化队列
void initQueue(Queue* queue) {queue->front = 0;queue->rear = 0;
}// 入队
void enqueue(Queue* queue, TreeNode* node) {queue->nodes[queue->rear++] = node;
}// 出队
TreeNode* dequeue(Queue* queue) {return queue->nodes[queue->front++];
}// 判断队列是否为空
int isEmpty(Queue* queue) {return queue->front == queue->rear;
}// 创建新节点
TreeNode* createNode(int value) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));newNode->data = value;newNode->left = newNode->right = NULL;return newNode;
}// 层次遍历
void levelOrder(TreeNode* root) {if (root == NULL) return;Queue queue;initQueue(&queue);// 将根节点入队enqueue(&queue, root);while (!isEmpty(&queue)) {TreeNode* node = dequeue(&queue);printf("%d ", node->data);// 如果左子节点存在，入队if (node->left) enqueue(&queue, node->left);// 如果右子节点存在，入队if (node->right) enqueue(&queue, node->right);}
}// 主函数
int main() {// 创建二叉树TreeNode* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);root->right->right = createNode(6);// 层次遍历printf("层次遍历: ");levelOrder(root);printf("\n");return 0;
}

线索树

设一棵二叉树有n个结点，则有n-1条边(指针连线)，而n个结点共有2n个指针域(Lchild和Rchild)，显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息：
对结点的指针域做如下规定：
若结点有左孩子，则Lchid指向其左孩子，否则
指向其直接前驱;
若结点有右孩子，则Rchid指向其右孩子，否则
指问其直接后继;
为避免混淆，对结点结构加以改进，增加两个标志域
如图6-10所示。

用这种结点结构构成的二叉树的存储结构，叫做检索链表；指向结点前驱和后继的指针叫做线索；按照某种次序遍历，加上线索的二叉树称之为线索二叉树。

树的存储结构

1.双亲表示法（顺序存储结构）

用一组连续的存储空间来存储树的结点，同时在每个结点中附加一个指示器（整数域），用以指示双亲结点的位置（下标值）。数组元素及数组的类型定义如下：

#define MAX_SIZE 100
typedef struct PTNode
{ElemType data;int parent;
}PTNode;
typedef struct
{
PTNode Nodes[MAX_SIZE];
int root;
int num;
}Ptree;

图6-13所示是一棵树及其双亲表示的存储结构。这种存储结构利用了任一结点的父节点唯一的性质。可以方便的直接找到任一结点的父节点，但求结点的子节点时，需要扫描整个数组。

2孩子链表表示法

（1）定长节点结构
指针域的数目就是数的度
其特点是：链表结构简单，但指针域的浪费明显节点结构如图6-14（a）所示。在一颗有n个结点，度为k的树中必有n(k-1)+1空指针域
证明：
1.树的总指针域：每个节点有 k 个指针域。树中有 n 个节点。因此，总共有 n×k 个指针域（包括有效指针和空指针）。
2.实际有效指针：每个节点的有效指针数量与树的结构和节点的度相关。
假设树中有 𝑛1个叶子节点，叶子节点没有子节点，它们的指针域都为空。
非叶子节点有 k 个指针域，其中只有一部分是有效的指向子节点的指针。
设定：树的总边数为 e，即树中所有的指针指向的子节点数。
对于一个度为 k 的树，它的边数 e 总是等于 n−1（因为树是连通的且无环）。
每一条边从父节点指向一个子节点。因此，树中共有 n−1 条有效边。
3.空指针数量：总指针数为 n×k。有效的指针数为 n−1（即树中有 n−1 条边，每条边对应一个有效的子节点指针）。
所以，空指针的数量为总指针数减去有效指针数：
空指针数=n×k−(n−1)=n×k−n+1=n(k−1)+1
（2）不定长结点结构
树中每个结点的指针域数量不同，是该结点的度，如图6-14（b）所示。没有多于的指针域，但操作不方便。

（3）复合链表结构

对于树中的每个结点，其孩子结点用带头结点的单链表表示，表节点和头结点的结构如图6-15所示。
n哥节点的树有n个（孩子）单链表（叶子结点的孩子链表为空），而n个头结点又组成一个线性表且以顺序存储结构表示。

3孩子兄弟表示法（二叉树表示法）

以二叉链表作为树的存储结构，其结点形式如图6-17(a)所示。
两个指针域:分别指向结点的第一个子节点和下一个兄弟结点。

哈夫曼树的构造

初始化：首先建立一个包含所有字符和其频率的优先队列。
合并最小节点：每次从队列中取出频率最小的两个节点，合并它们形成一个新的节点，并将其放回队列，按照大小排序。
重复合并：继续取出队列中两个最小的元素进行合并后归队，直到队空。

哈夫曼编码

在电报收发等数据通讯中，常需要将传送的文字转
换成由二进制字符0、1组成的字符串来传输。为了使收
发的速度提高，就要求电文编码要尽可能地短.此外，
要设计长短不等的编码，还必须保证任意字符的编码都
不是另一个字符编码的前缀，这种编码称为前缀编码.
哈夫曼树可以用来构造编码长度不等且译码不产生二义性的编码

构造哈夫曼树，左0右1

---

并非我们的所有精力都用于谋生。我们渴望获得思想、获得梦想、获得想象、获得诗的意境。 —弗吉尼亚·伍尔夫