| 【数据结构(初稿)】树和二叉树总结 | 您所在的位置：网站首页 › make的五种语法结构归纳和总结的区别 › 【数据结构(初稿)】树和二叉树总结 |
【数据结构(初稿)】树和二叉树总结
|
halo~我是bay_Tong桐小白 本文内容是桐小白个人对所学知识进行的总结和分享，知识点会不定期进行编辑更新和完善，了解最近更新内容可参看更新日志，欢迎各位大神留言、指点 树和二叉树总结——基本知识要点汇总(初稿） 【更新日志】计算机统考408考纲要求 树和二叉树相关概念基本知识概念树和二叉树的性质满二叉树与完全二叉树 二叉树的存储结构二叉树的顺序存储二叉树的链式存储 二叉树的遍历三种基本遍历的递归算法三种基本遍历的非递归算法层序遍历算法（利用队列实现）由两种遍历序列确定二叉树 二叉树的线索化树的存储结构双亲表示法孩子表示法带双亲的孩子表示法孩子-兄弟表示法 树与森林、二叉树三者的联系、遍历与转化哈夫曼树（最优二叉树）相关专题——哈夫曼编码的实现并查集工作原理二叉搜索树（待更新……）平衡二叉树（待更新……） 【更新日志】最近更新： 更新内容——计算机统考408考纲考察目标与变动情况（2020.9.19）新增内容——计算机统考408考纲要求（2020.9.13）更新内容——树与森林、二叉树三者的联系（2020.7.5）内容持续更新中…… 计算机统考408考纲要求2021计算机统考408考纲数据结构学科考察目标 掌握数据结构的基本概念、基本原理和基本方法掌握数据结构的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力2021计算机统考408数据结构考纲变动情况
树：n个结点的有限集合（n>=0）n为0时为空树。树中有一个根结点，它没有直接前驱，有零个或多个直接后继，根结点之外的n-1个结点可以划分成m个互不相交的有限集，这些有限集称为根的子树（子树互不相交）。 二叉树：有限的结点的集合，由根结点和不相交的二叉子树组成 二叉树的五种基本形态 树和二叉树的联系与区别 满足以下两个条件的树形结构叫做二叉树： 每个结点至多只有两棵子树二叉树的子树有左右之分，其次序不能颠倒。树可以有序可以无序因此树和二叉树结构不等价 【孩子与双亲：结点若有直接后继，则可称它为它直接后继结点的父亲或双亲，直接后继结点为它的孩子，位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子】 其它定义和基本术语： 结点的度：结点直接后继的个数树的度：树的所有结点的度的最大值叶子结点：也称终端结点，即度为0的结点分支结点：也称非终端结点，即度不为0的结点孩子结点：结点的直接后继双亲结点：结点的直接前驱兄弟结点：同一双亲结点的孩子结点互称兄弟结点概念区分：树的深度、树的高度、结点的高度 对于整棵树而言，树的深度=树的高度，即树中所有结点层次的最大值，从上往下数结点的高度不同于树的高度和深度，结点的高度指指从该结点到叶子结点的最长简单路径的边的条数，从下往上数（不同教材对结点的高度定义不同，有的从叶结点开始从1计数，有的从叶结点开始从0计数）
树和二叉树的性质
区别于联系：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树 二叉树的顺序存储即令顺序表的下标与二叉树结点的序号进行对应，表单元进行数据元素的存储 二叉树的链式存储实质就是广义表多重链表的一种应用，一个结点可能同时属于多个链，结点中存储内容可以是数据元素，也可以是另一个表结构（广义表工作原理详细见本栏文章《数组和广义表总结——基本知识要点汇总》） 按某种搜索路径，使二叉树每个结点均被访问且仅被访问一次。二叉树的遍历按其构成以及访问结点的顺序分为四种方式，即先序遍历、中序遍历、后序遍历、层次遍历 用L、D、R分别表示遍历左子树、访问根结点、遍历有子树 则 先序遍历：DLR（根左右）中序遍历：LDR（左根右）后序遍历：LRD（左右根）层序遍历：按层次进行遍历
二叉树遍历与前缀、中缀、后缀表达式的联系 假如用二叉树表示表达式(a+b*c)-d/e，运算数均为叶子结点，运算符号均为父节点，进行二叉树的构造 （递归的相关概念详见本栏文章《栈和队列总结——基本知识要点汇总》中的递归函数工作栈部分） 假设结点内容为char类型数据元素 //先序遍历 void PreOrderTraversal(BinTree BT) { if (BT) { printf(" %c", BT->data); PreOrderTraversal(BT->Left); PreOrderTraversal(BT->Right); } } //中序遍历 void InOrderTraversal(BinTree BT) { if (BT) { InOrderTraversal(BT->Left); printf(" %c", BT->data); InOrderTraversal(BT->Right); } } //后序遍历 void PostOrderTraversal(BinTree BT) { if (BT) { PostOrderTraversal(BT->Left); PostOrderTraversal(BT->Right); printf(" %c", BT->data); } } 三种基本遍历的非递归算法先序遍历非递归算法 核心思想：借用栈结构进行父结点的暂存 具体操作： 遇到结点即将其入栈并访问该结点遍历访问它的左子树，遍历结束后弹出该结点按其右指针先序遍历右子树 /*先序遍历（非递归）*/ void PreOrderTraversal(BinTree BT) { BinTree node = BT; Stack S = CreateStack(); while (node || !IsEmptyS(S)) { if (node) { Push(S, node);//结点入栈 printf(" %c", node->data);//访问该结点 node = node->Left;//遍历访问它的左子树 } else { node = Pop(S);//左子树遍历结束后弹出该结点 node = node->Right;//先序遍历右子树 } } printf("\n"); free(S); }（栈的工作原理及基本操作集等内容详见本栏文章《栈和队列总结——基本知识要点汇总》） 中序遍历非递归算法 核心思想：借用栈结构进行父结点的暂存 具体操作： 遇到结点即将其入栈，并遍历其左子树左子树遍历结束后弹出该结点并进行访问按其右指针中序遍历右子树 /*中序遍历（非递归）*/ void InOrderTraversal(BinTree BT) { BinTree node = BT; if (!BT) { printf("空树\n"); return; } Stack S = CreateStack(); while (node || !IsEmptyS(S)) { if (node) { Push(S, node);//结点入栈 node = node->Left;//遍历其左子树 } else { node = Pop(S);//左子树遍历结束后结点出栈 printf(" %c", node->data);//访问该结点 node = node->Right;//中序遍历右子树 } } printf("\n"); free(S); }后序遍历非递归算法 核心思想：借用栈结构进行父结点的暂存，并要防止重复遍历右子树情况的发生 具体操作： 遇到结点即将其入栈，并遍历其左子树左子树遍历结束后，获取栈顶结点，判断该结点是否有右子树且仍未被访问若无仍未被访问的右子树，则访问并该结点，表明该结点已被访问防止重复访问，之后结点出栈若有仍未被访问的右子树则后序遍历右子树 /*后序遍历（非递归）*/ void PostOrderTraversal(BinTree BT) { BinTree node = BT; BinTree p = NULL; if (!BT) { printf("空树\n"); return; } Stack S = CreateStack(); while (node || !IsEmptyS(S)) { if (node) { Push(S, node);//结点入栈 node = node->Left;//遍历左子树 } else { node = GetTop(S);//左子树遍历结束后获取栈顶结点 if ((node->Right == NULL || node->Right == p)) {//判断是否有右子树且仍未被访问 printf(" %c", node->data);//若无仍未被访问的右子树，则访问该结点 p = node;//标记该结点，表明已被访问防止重复访问 Pop(S);//结点出栈 node = NULL; } else { node = node->Right;//若有仍未被访问的右子树则后序遍历右子树 } } } printf("\n"); free(S); } 层序遍历算法（利用队列实现）核心思想：借用队列结构进行父结点的按顺序暂存 具体操作：遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右孩子入队 /*层次遍历*/ void LevelOrderTraversal(BinTree BT) { Queue Q; BinTree T; if (!BT) { printf("空树\n"); return; } Q = CreateQueue(MaxSize_Q); AddQ(Q, BT); while (!IsEmptyQ(Q)) { T = DeleteQ(Q); printf(" %c", T->data); if (T->Left) { AddQ(Q, T->Left); } if (T->Right) { AddQ(Q, T->Right); } } printf("\n"); free(Q); }（队列的工作原理及基本操作集等内容详见本栏文章《栈和队列总结——基本知识要点汇总》） 由两种遍历序列确定二叉树前面提到 先序遍历：DLR（根左右）中序遍历：LDR（左根右）后序遍历：LRD（左右根） 要确定二叉树结构，则需要已知其中两种遍历序列，且其中必须要有中序遍历序列 下图为仅已知先序遍历序列和后序遍历序列无法确定二叉树的一个例子
根据先序和中序遍历序列来确定二叉树的方法： 先序遍历的访问顺序是DLR，则第一个被访问的结点一定是根结点中序遍历的访问顺序是LDR，则根结点将中序序列分割成两部分：在根结点之前是左子树结点的中序遍历，在根结点之后是右子树结点的中序序列根据左子树的中序序列中结点的个数，又可以将前序序列除根以外部分分成左子树的连续序列和右子树的前序序列上述两个步骤依次类推可递归得到整棵二叉树 二叉树的线索化在之前介绍二叉树的链式存储时，提到如下问题 用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器parent指示其双亲结点在表中的位置（与静态链表原理类似，静态链表工作原理详见本栏文章《线性表总结——基本知识要点汇总》静态链表工作原理部分） 用一组连续的空间来存储树中的结点，把每个结点的孩子在表中的位置（并非孩子本身）排列起来构成一个单链表，称为孩子链表。n个结点共有n个孩子链表。 双亲表示法与孩子表示法的一种优势结合 用链表进行树的存储，链表中结点的两个链域分别指向该结点的长子和次子 三者相互联系 三者互相转化
变长指令编码（出现概率大的编以短字长的码，出现概率小的编以长字长的编码）【概念补充-前缀编码：字符只出现在叶子节点，避免编码出现二义性】 图像的无损压缩 图像压缩的算法思想 扫描图像所有像素点统计像素出现的概率并按大小排列建立哈夫曼树进行哈夫曼编码按位存储编码后的二进制位 相关专题——哈夫曼编码的实现哈夫曼编码的构建方法：每次选择两个权重最小的结点进行合并，构建哈夫曼树，哈夫曼树构建完成后从根结点开始编码（递归），例如左孩子标1右孩子标0  相关算法
//并集
void Union(Type L, ElementType x1, ElementType x2) {
int Root1 = Find(L, x1);
int Root2 = Find(L, x2);
if (Root1
L[Root1].Parent = Root2;
L[Root2].Parent += L[Root1].Parent;
}
else { printf("属于同一个集合\n"); }
}
//查集
int Find(Type L, ElementType x) {
int i;
for (i = 0; i = UnionMaxSIze) { return -1; }
for (; L[i].Parent >= 0; i = L[i].Parent);
return i;
}
二叉搜索树（待更新……）
平衡二叉树（待更新……）
持续更新中…… 我是桐小白，一个摸爬滚打的计算机小白 |
2021计算机统考408考纲对树和二叉树部分考察要求
其它特殊二叉树 
树的孩子兄弟表示法在树的存储结构中详细介绍，与此处二叉链表会有联系
二叉树的遍历实际上就是把一个非线性结构转化为一个线性结构
表达式的中缀、后缀转换以及求值等内容详见本栏文章《栈和队列总结——基本知识要点汇总》
而二叉树的遍历实际上就是把一个非线性结构转化为一个线性结构的线索化过程 二叉树的线索化：将二叉链表的空链域利用起来，保存遍历过程中的前驱或后继信息 
如此线索二叉树构造完成后，仅根据后继指针即可对二叉树进行线性的操作 【具体算法后续更新……】
综合上述：
二叉树还原为树和森林即为上述方法的逆过程
哈夫曼树的应用：
【具体代码后续更新……】【本文地址】