绍兴建设图审网站,广告牌的样式大全,肇庆手机台app下载,哈尔滨网站建设推广专栏#xff1a;数据结构复习之路
复习完上面四章【线性表】【栈和队列】【串】【数组和广义表】#xff0c;我们接着复习 树和二叉树#xff0c;这篇文章我写的非常详细且通俗易懂#xff0c;看完保证会带给你不一样的收获。如果对你有帮助#xff0c;看在我这么辛苦整理…专栏数据结构复习之路
复习完上面四章【线性表】【栈和队列】【串】【数组和广义表】我们接着复习 树和二叉树这篇文章我写的非常详细且通俗易懂看完保证会带给你不一样的收获。如果对你有帮助看在我这么辛苦整理的份上三连一下啦
目录
一、树的定义
1.1 基本术语
1.2 扩展树的四种表示形式
二、二叉树
2.1 二叉树的定义
2.2 二叉树的性质
2.3 满二叉树
2.4 完全二叉树
2.5 二叉排序树
2.6 平衡二叉树
2.7 二叉树的顺序存储结构
2.8 二叉树的链式存储结构 2.9 二叉树的先中后序遍历
① 先序遍历
② 中序遍历
③ 后序遍历 相关题目练习
2.10 先中后序遍历的扩展
2.11 递归实现顺序表存储
2.12 二叉树的层次遍历
2.13 通过二叉树的先、中、后序遍历重构二叉树
三、线索二叉树
3.1 基本概念 3.2 中序线索化
构建
3.3 先序线索化
构建:
3.4 后序线索化
3.5 线索二叉树找前驱和后继
【1】中序线索二叉树
【2】先序线索二叉树 【3】后序线索二叉树
四、树的存储结构
4.1 双亲表示法顺序存储
4.2 孩子表示法顺序链式
4.3 孩子兄弟表示法链式存储 4.4 森林和二叉树的转换
五、树和森林的遍历
5.1 树的先根遍历
5.2 树的后根遍历
5.3 树的层次遍历
5.4 森林的先序遍历
5.5 森林的中序遍历
六、哈夫曼树
基本概念
定义
哈夫曼树的构造 哈夫曼编码
译码
结尾 一、树的定义
树(Tree) 是 n(n≥0)个结点的有限集。若 n0 称为空树
若 n 0则它满足如下两个条件
有且仅有一个特定的称为根 (Root) 的结点。 其余结点可分为 m (m≥0) 个互不相交的有限集 T1 , T2 , T3 , …, Tm 其中每一个集合本身又是一棵树并称为根的子树 (SubTree)。
1.1 基本术语
1、结点拥有的子树数称为 结点的度(degree)如上图结点A的度为3B的度为2。
度为0的结点叫叶子(leaf)终端结点度不为0的结点叫分支结点非终端结点内部结点B、C、D、E、H树的度是树中各结点的最大的度上图树的度为3
2、结点的子树的根称为该结点的孩子(child)
双亲(parent)D为H、I、J的双亲兄弟(sibling)(H、I、J互为兄弟)祖先子孙(B的子孙为E、K、L、FM的祖先为A、D、H)
3、结点的层次
根结点为第一层某结点在第 i 层其孩子在第 i1 层树中结点的最大层次称为树的深度其双亲在同一层的结点互为堂兄弟
4、森林(forest) 是 m (m≥0) 棵互不相交的树的集合。比如上图中除去 A 结点那么分别以 B、C、D 为根结点的三棵子树就可以称为森林。
树可以理解为是由根结点和若干子树构成的而这若干子树本身就是一个森林因此树还可以理解为是由根结点和森林组成的。
1.2 扩展树的四种表示形式 一、树形表示法正如上述所介绍
二、嵌套集合文氏表示法
注它是以嵌套集合的形式表示的集合之间绝不能相交即任意两个圆圈不能有交集
三、凹入表示法
注最长条为根结点相同长度的表示在同一层次。例如 B、C、D 长度相同都为 A 的子结点E 和 F 长度相同为 B 的子结点K 和 L 长度相同为 E 的子结点依此类推。
四、广义表表示法正如在上一章广义表所述
二、二叉树
二叉树在树结构的应用中起着非常重要的作用因为对二叉树的许多操作算法简单而任何树均可与二叉树相互转换这样就解决了树的存储结构及其运算中存在的复杂性。
2.1 二叉树的定义
二叉树是 n (n≥0) 个结点的有限集它或者是 空集 (n 0)或者由一个根结点及两棵互不相交的 分别称作这个根的左子树和右子树的二叉树组成。
特点
每个结点最多有俩孩子 (二叉树中不存在度大于 2 的结点) 。子树有左右之分其次序不能颠倒。二叉树可以是空集合根可以有空的左子树或空的右子树。
⚠️注意二叉树不是树的特殊情况它们是两个概念。
理由二叉树结点的子树要区分左子树和右子树即使只有一棵子树也要进行区分说明它是左子树还是右子树。树当结点只有一个孩子时就无须区分它是左还是右。也就是 二叉树每个结点位置或者说次序都是固定的可以是空但是不可以说它没有位置而树的结点位置是相对于别的结点来说的没有别的结点时它就无所谓左右了因此二者是不同的。这是二叉树与树的最主要的差别。
⚠️注意虽然二叉树与树概念不同 但有关树的基本术语对二叉树都适用。
2.2 二叉树的性质 性质 1在二叉树的第 i 层上至多有 个结点 (i ≥1)。 性质 2深度为 k 的二叉树至多有 个结点k ≥1)。 扩展深度为 k 的 m 叉树至多有 个结点。 性质 3高度为 h 的 m 二叉树至少有 h 个结点。 扩展高度为h、度为 m 的树至少有 h m - 1 个结点。 性质 4具有 n 个结点的 m叉树 的最小高度 h 为 通过 可求出 h 性质 5对任何一棵二叉树 T如果其叶子数为 度为 2 的结点数为 则 2.3 满二叉树
特点每一层上的结点数都达到最大叶子全部在最底层。
编号规则从根结点开始自上而下自左而右。 因此
一棵深度为 k 且有 个结点的二叉树称为满二叉树。按层序从1开始编号结点为 i 的左孩子为 2i 右孩子为 2i 1结点 i 的父节点为 (注意是向下取整)
2.4 完全二叉树
定义深度为 k 的具有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号为 1~ n 的 结点一一对应时称之为完全二叉树。
特点叶子只可能分布在层次最大的两层上。 对任一结点如果其右子树的最大层次为 L则其 左子树的最大层次必为 L 或 L 1。
因此
只有最后两层可能有叶子结点最多只有一个度为1的结点按层序从1开始编号结点为 i 的左孩子为 2i 右孩子为 2i 1结点 i 的父节点为 (注意是向下取整)2i n则结点 i 无左孩子即结点 i 为叶子结点否则其左孩子为 2i2i 1 n则结点 i 无右孩子否则其右孩子为 2i 1
常见考点 考点 1具有 n 个结点的完全二叉树的深度为 (向下取整) 或者 (向上取整)
考点 2 对于完全二叉树可以由结点数 n 推出度为0、1和2的结点个数、 和
2.5 二叉排序树
二叉排序树。一棵二叉树或者是空二叉树, 或者是具有如下性质的二叉树:
左子树上所有结点的关键字均小于根结点的关键字右子树上所有结点的关键字均大于根结点的关键字
左子树和右子树又各是一棵二叉排序树。
好处二叉排序树可用于元素的排序、搜索都是相当高效的
2.6 平衡二叉树
平衡二叉树树上任一结点的左子树和右子树的深度之差不超过1。
好处搭配二叉排序树可以达到更高的搜索效率
2.7 二叉树的顺序存储结构 #define MaxSize 100
struct TreeNode{ElemType value; //结点中的数据元素bool isEmpty; //结点是否为空
} t[MaxSize 1]; 【1】对于完全二叉树用一组地址连续的存储单元依次自上而下、自左至右存储结点元素即将编号为 i 的结点元素存储在一维数组中下标为 i 的分量中。
这里常见的考点就是
i 的左孩子i 的右孩子判断 i 是否有右孩子判断 i 是否是叶子结点或分支结点
这些都是完全二叉树的重要性质上文已讲解。
⚠️注意如果 i 从0开始那么将现有编号 1再按公式算算出结果后再 -1不要糊涂 对于一般二叉树将其每个结点与完全二叉树上的结点相对照存储在一 维数组的相应分量中。 但是这种存储已经不满足完全二叉树的性质。
因此为了能够满足这种性质就需要为这个非完全二叉树依次补上虚拟结点空间。
但是这种存储形式在最坏情况下深度为 k 的且只有 k 个结点的右单支树需要 长度为 的一维数组因此链式存储的优势也就显而易见了。
2.8 二叉树的链式存储结构 typedef struct BiTNode{ElemType data; //数据域 struct BiTNode *lchild , *rchild; //左、右孩子指针
} BiTNode , *BiTree;
除了根结点外每个结点上面都必与一个指针 相连 共有 n - 1 个指针那么剩余的空指针数量应为 2n - (n - 1) n 1个空指针。
找某一结点P的左孩子和右孩子相当轻松 printf(p结点的左孩子结点为%d\n, p-lchild-data);
printf(p结点的右孩子结点为%d\n, p-rchild-data); 但是如果要找到指定结点 P 的父结点就只能从根结点开始遍历寻找因此你可以考虑在结构体中再加一个父节点指针。 typedef struct BiTNode{ElemType data; //数据域 struct BiTNode *lchild , *rchild; //左、右孩子指针 struct BiTNode *parent; //父节点指针
} BiTNode , *BiTree; 这种形式也叫做 三叉链表 。
2.9 二叉树的先中后序遍历
遍历就是按某种次序把所有结点都访问一遍。
这种递归式的遍历只有搞懂递归过程才能真正的理解它的遍历过程因此请务必理解它们的递归代码
对于这三种遍历我将基于如下这种图进行讲述
① 先序遍历 void PreOrderTraverse(BiTree T) {//如果二叉树存在则遍历二叉树if (T) {printf(%d,T-data); //输出结点值PreOrderTraverse(T-lchild);//访问该结点的左孩子PreOrderTraverse(T-rchild);//访问该结点的右孩子}
} 先访问根节点再遍历左子树最后遍历右子树。
遍历结果5 2134 8697
⚠️注意根据它的代码我们发现在递归左右子树前一定是先输出当前结点值并且只有左子树递归完后才会返回上一层递归右子树说明对于每个子树先输出父结点、再输出左孩子最后输出右孩子。因此记住这三句代码的顺序就对遍历过程了如指掌了。
详细递归过程 输出根节点 5进入 5 的左子树执行同样的步骤输出结点 2进入 2 的左子树执行同样的步骤输出结点 1结点 1 没有左子树结点 1 没有右子树进入 2 的右子树执行同样的步骤输出结点 3进入 3 的左子树执行同样的步骤输出结点4结点 4 没有左子树结点 4 没有右子树进入 3 的右子树没有直接返回因为 5 的左子树都已经遍历完了所有一直返回到进入 5 的右子树进入 5 的右子树执行同样的步骤输出结点 8进入 8 的左子树执行同样的步骤输出结点 6进入 6 的左子树没有直接返回再进入 6 的右子树进入 6 的右子树执行同样的步骤输出结点9结点 9 没有左子树结点 9 没有右子树进入 8 的右子树执行同样的步骤输出结点 7结点 7 没有左子树结点 7 没有右子树//运行到这里结点 5 的右子树都已经遍历完了所有就递归回去直到函数结束 ② 中序遍历 void INOrderTraverse(BiTree T) {if (T) {INOrderTraverse(T-lchild);//遍历当前结点的左子树printf(%d ,T-data); //输出当前结点INOrderTraverse(T-rchild);//遍历当前结点的右子树}
} 先遍历左子树再访问根节点最后遍历右子树。
遍历结果1243 5 6987
⚠️注意输出结点值的位置放在了中间说明对于每个子树先输出左孩子再输出它的父结点最后输出其右孩子。
递归过程同上可以自己动手试试画出递归过程~
③ 后序遍历 void PostOrderTraverse(BiTree T) {if (T) {PostOrderTraverse(T-lchild);//遍历左孩子PostOrderTraverse(T-rchild);//遍历右孩子printf(%d , T-data);}
} 先遍历左子树再遍历右子树最后访问根节点。
遍历结果1432 9678 5
⚠️注意输出结点值的位置放在了最后面说明对于每个子树先输出左孩子再输出右孩子最后输出其父结点 相关题目练习
【1】二叉树的先序遍历中任一结点均先于它的左、右子女如果存在访问所有这句话是对的。
【2】在二叉树的定义那里已经讲的非常清楚了这是错的。
【3】因为后序遍历的最后一个结点一定是根结点并且前序遍历的第一个结点也是根结点所以排除法选择D。
【4】 根据前序遍历的结果可知 a 是根结点。由中序遍历的结果dgbaechf 可知d、g、b 是左子树的结点 e、c、h、f 是右子树的结点。再由前序遍历的结果bdg 可知 b 是a左边子树的根由cefh 可知 c 是a右边子树的根。再由中序遍历的结果dgb 可知 d,g 是b 左边子树的结点 g为d的右孩子。至此a 的左子树已完全弄清楚了。同样的道理可以弄清楚以c为根的子树的结点位置。所以可知后序遍历的结果是D。
【5】很明显选择A。
【6】 过程如下 2.10 先中后序遍历的扩展 【1】我们只需要对先序、中序、后序遍历的过程稍加修改就可以设计出构建二叉树的函数
比如通过先序遍历构建下图二叉树只需要少许代码量就能构建好
void CreateBiTree(BiTree* T) {int num;scanf(%d, num);//如果输入的值为 0表示无此结点if (num 0) {*T NULL;}else{//创建新结点*T (BiTree)malloc(sizeof(BiTNode));(*T)-data num;CreateBiTree(((*T)-lchild));//创建该结点的左孩子CreateBiTree(((*T)-rchild));//创建该结点的右孩子}
} 当我们输入的num数依次为5 210034000 860900700
就能将如图的二叉树用链表存储起来超级方便 【2】统计二叉树中叶子结点的个数 实现此操作只需对二叉树“遍历”一遍并在遍历过程中对 “叶子结点计数”即可。显然这个遍历的次序可以随意只是为了在遍历时进行计数需要在算法的参数中设一个“计数器”。 void CountLeaf (BiTree T, int count)
{ // 先序遍历二叉树以 count 返回二叉树中叶子结点的数目if ( T ){ if ((!T−Lchild) (!T−Rchild)) // 无左、右子树{count ; // 对叶子结点计数}CountLeaf ( T−Lchild, count); CountLeaf ( T−Rchild, count); }
} 【3】求二叉树的深度后序。 二叉树的深度 MAX左子树深度右子树深度 1 。 int BiTreeDepth(BiTree T)
{ if (!T) depth 0; else { depthleft BiTreeDepth(T-Lchild); depthright BiTreeDepth(T-Rchild); depth max(depthleft, depthright) 1; } return depth;
}// BiTreeDepth 【4】 通过这种左右子树递归的思想可以计算二叉树的所有叶子的带权路径长度之和WPL。一个叶子结点的带权路径长度为 该结点的权重weight * 该结点的深度depth. (1算法思想 递归遍历二叉树的所有叶节点计算每个叶节点的带权路径长度然后累加得到二叉树的带权路径长度WPL。 (2) typedef struct TreeNode {int weight; struct TreeNode* left;struct TreeNode* right;
} TreeNode; (3) int calculate_WPL(TreeNode *root , int depth)
{if (root NULL) return 0; //如果为空树 WPL为 0 if (root - left NULL root - right NULL) return root - weight * depth; //当前叶子结点的权值乘路径长度 return calculate_WPL(root - left , depth 1) calculate_WPL(root - right , depth 1); //递归求二叉树中所有叶结点的带权路径长度之和} 【5】 通过这种左右子树递归的思想我们还可以处理下述问题
(1) 算法思想 因为括号反映操作符的计算次序观察这两个表达式树的输出结果不难看出应采取中缀表达式的递归遍历算法对于每递归到 深度 1并且不是叶子结点时打印左括号 “ ”当该结点的子孙遍历完后再打印右括号“ ”。 (2) #include stdio.h
#include stdlib.h// 表达式树的结构体
typedef struct node {char data[10]; struct node* left , *right;
} BTree;void infixExpression(BTree* root, int depth) {if (root NULL) return;else if (root - left NULL root - right NULL){ //叶子结点需格外输出 printf(%c,root - data[0]);return;}else {if (depth 1) printf(();infixExpression(root - left , depth 1);printf(%c, root - data[0]);infixExpression(root - right , depth 1);if (depth 1) printf());}
}int main() {// 构造第一个表达式树(可以运行检验自己是否写错哦)BTree* root1 (BTree*)malloc(sizeof(BTree));root1-data[0] *;root1-left (BTree*)malloc(sizeof(BTree));root1-left-data[0] ;root1-left-left (BTree*)malloc(sizeof(BTree));root1-left-left-data[0] a;root1-left-left-left NULL;root1-left-left-right NULL;root1-left-right (BTree*)malloc(sizeof(BTree));root1-left-right-data[0] b;root1-left-right-left NULL;root1-left-right-right NULL;root1-right (BTree*)malloc(sizeof(BTree));root1-right-data[0] *;root1-right-left (BTree*)malloc(sizeof(BTree));root1-right-left-data[0] c;root1-right-left-left NULL;root1-right-left-right NULL;root1-right-right (BTree*)malloc(sizeof(BTree));root1-right-right-data[0] -;root1-right-right-left NULL;root1-right-right-right (BTree*)malloc(sizeof(BTree));root1-right-right-right-data[0] d;root1-right-right-right-left NULL;root1-right-right-right-right NULL;printf(该表达式树的带括号的等价中缀表达式为);infixExpression(root1, 1);return 0;
} 2.11 递归实现顺序表存储
先序遍历
这里数组的下标是从0开始的即根节点是从0开始存储的。 void PreOrderTraverse(Tree T, int p_node) {if (T[p_node].empty) {printf(%d , T[p_node].value);//先序遍历左子树if ((2 * p_node 1 MaxSize) (T[2 * p_node 1].empty) {PreOrderTraverse(T, 2 * p_node 1);}//最后先序遍历右子树if ((2 * p_node 2 MaxSize) (T[2 * p_node 2].empty)) {PreOrderTraverse(T, 2 * p_node 2);}}
} 中序遍历 void INOrderTraverse(Tree T, int p) {if (T[p].empty){//递归遍历左子树if (((2 * p 1) MaxSize) (T[2 * p 1].empty)) {INOrderTraverse(T, 2 * p 1);}//访问当前结点printf(%d , T[p].value);//递归遍历右子树if (((2 * p 2) MaxSize) (T[2 * p 2].empty)){INOrderTraverse(T, 2 * p 2);} }
} 后序遍历 void PostOrderTraverse(Tree T, int p) {if (T[p].empty){if ((p * 2 1 MaxSize) (T[p * 2 1].empty)) {PostOrderTraverse(T, 2 * p 1);}if ((p * 2 2 MaxSize) (T[p * 2 2].empty)) {PostOrderTraverse(T, 2 * p 2);}printf(%d , T[p].value);}
}2.12 二叉树的层次遍历
所谓层次遍历二叉树就是从树的根结点开始一层一层按照从左往右的次序依次访问树中的结点。
层次遍历用链表存储的二叉树可以借助链式队列存储结构实现具体方案是
将根结点入队从队列的头部提取一个结点并访问它将该结点的左孩子和右孩子依次入队重复执行第 2 步直至队列为空
这里以构建这个二叉树以此为例进行层次遍历。
#include stdio.h
#include stdlib.h
//定义二叉树
typedef struct BiTNode {int data;//数据域struct BiTNode* lchild, * rchild;//左右孩子指针
}BiTNode, * BiTree;
//定义链队列
typedef struct LinkNode{BiTNode *value;struct LinkNode *next;
} LinkNode;
typedef struct{LinkNode *front , *rear;
}LinkQueue;void InitQueue(LinkQueue q) //初始化带头结点的链队列
{q.front q.rear (LinkNode *)malloc(sizeof(LinkNode));q.front-next NULL;
}
//通过先序遍历构建二叉树
void CreateBiTree(BiTree* T) {int num;scanf(%d, num);//如果输入的值为 0表示无此结点if (num 0) {*T NULL;}else{//创建新结点*T (BiTree)malloc(sizeof(BiTNode));(*T)-data num;CreateBiTree(((*T)-lchild));//创建该结点的左孩子CreateBiTree(((*T)-rchild));//创建该结点的右孩子}
}
//入队函数
void EnQueue(LinkQueue q, BiTree node) {LinkNode *x (LinkNode *)malloc(sizeof(LinkNode));x-value node;x-next NULL;q.rear-next x; q.rear x;
}
//出队函数
BiTNode* DeQueue(LinkQueue q) {if (q.front q.rear){printf(队列已空); exit(0); }LinkNode *x q.front-next;//从队头开始出队BiTNode* p_node x-value;q.front-next x-next;if (q.rear x){q.front q.rear;}return p_node;
}
//层次遍历二叉树
void LevelOrderTraverse(BiTree T) {//如果二叉树存在才进行层次遍历if (T) {LinkQueue q;InitQueue(q); //根结点入队EnQueue(q, T);//重复执行直至队列为空while (q.front ! q.rear){//从队列取出一个结点BiTNode *p DeQueue(q);//访问当前结点printf(%d , p-data);//将当前结点的左右孩子依次入队if (p-lchild) {EnQueue(q, p-lchild);}if (p-rchild) {EnQueue(q, p-rchild);}}}
}
//后序遍历二叉树释放树占用的内存
void DestroyBiTree(BiTree T) {if (T) {DestroyBiTree(T-lchild);//销毁左孩子DestroyBiTree(T-rchild);//销毁右孩子free(T);//释放结点占用的内存}
}
int main() {BiTree Tree;CreateBiTree(Tree);LevelOrderTraverse(Tree);DestroyBiTree(Tree);return 0;
} 输入 5 2 1 0 0 3 4 0 0 0 8 6 0 9 0 0 7 0 0 输出 5 2 8 1 3 6 7 4 9 2.13 通过二叉树的先、中、后序遍历重构二叉树
由二叉树的遍历序列构造唯一的二叉树
先序中序后序中序层序中序 给定二叉树的前序和后序判断二叉树是否唯一关于二叉树先序遍历和后序遍历为什么不能唯一确定一个二叉树分析 看了这两篇博客我想让大家明白两点
为什么包含中序遍历就能唯一确定一个二叉树先序后序在某些情况下也能唯一确定一个二叉树
三、线索二叉树
3.1 基本概念
在二叉树的结点上加上线索的二叉树称为线索二叉树对二叉树以某种遍历方式如先序、中序、后序或层次等进行遍历使其变为线索二叉树的过程称为对二叉树进行线索化。
对于n个结点的二叉树在二叉链存储结构中有n1个空链域利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针这些指针称为线索加上线索的二叉树称为线索二叉树。
根据线索性质的不同线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 ⚠️注意线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题。 线索二叉树中的线索能记录每个结点前驱和后继信息。为了区别线索指针和孩子指针在每个结点中设置两个标志 ltag 和 rtag。 当 ltag 和 rtag 为0时 leftChild 和 rightChild分别是指向左孩子和右孩子的指针否则leftChild是指向结点前驱的线索(pre)rightChild是指向结点的后继线索(suc)。由于每个标志只占用一个int每个结点所需要的存储空间节省很多。 现将二叉树的结点结构重新定义如下 其中ltag 0 时lchild指向左儿子ltag 1 时lchild指向前驱rtag0 时rchild指向右儿子rtag1 时rchild指向后继。 线索二叉树存储结构 typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild , *rchild;int ltag , rtag;
}ThreadNode , *ThreadTree; 3.2 中序线索化
以中序遍历序列为依据进行 “线索化”。
构建 #include stdio.h
#include stdlib.h
typedef struct ThreadNode{ //将此二叉树线索化 char data;ThreadNode *lchild , *rchild;int ltag , rtag ;
}ThreadNode , *ThreadTree;ThreadNode *pre NULL; //全局变量pre,指向当前访问结点前驱 void CreateTree(ThreadTree tree) //先序遍历构建二叉树
{char node;scanf( %c,node); //%c前面加空格为了过滤空格和回车的影响if (node 0){tree NULL;}else{tree (ThreadNode *)malloc(sizeof(ThreadNode)) ;tree-data node;tree-ltag 0;tree-rtag 0;CreateTree(tree-lchild);CreateTree(tree-rchild);}
}void InThread(ThreadTree T) ;void visit(ThreadNode *q) ;void Create_ThreadTree(ThreadTree T) //中序遍历二叉树一边遍历一边线索化
{if (T ! NULL){InThread(T) ;if (pre-rchild NULL) //处理遍历的最后一个结点 {pre-rtag 1;}}
}void InThread(ThreadTree T) //中序遍历
{if (T ! NULL){InThread(T-lchild);visit(T);InThread(T-rchild);}
}void visit(ThreadNode *q) //线索化
{if (q-lchild NULL){ //左子树为空建立前驱线索 q-lchild pre;q-ltag 1;}if (pre ! NULL pre-rchild NULL){pre-rchild q; //建立前驱结点的后继线索 pre-rtag 1; } pre q;//记得修改当前访问结点的前驱
}void Demo(ThreadTree tree , ThreadNode *G)
{G tree-lchild-lchild-rchild; // 求指定结点“G ” 的前驱结点和后继结点 if (G-ltag 1){printf(结点“G ”的前驱结点为 %c \n , G-lchild-data);}if (G-rtag 1){printf(结点“G ”的后继结点为 %c , G-rchild-data);}
}
int main()
{ThreadTree threadtree;CreateTree(threadtree); Create_ThreadTree(threadtree);ThreadNode G_node;Demo(threadtree , G_node);
} 输入 A B D 0 G 0 0 E 0 0 C F 0 0 0 输出 结点“G ”的前驱结点为 D
结点“G ”的后继结点为 B 3.3 先序线索化
构建: void Create_ThreadTree(ThreadTree T) //先序遍历二叉树一边遍历一边线索化
{if (T ! NULL){PreThread(T) ;if (pre-rchild NULL) //处理遍历的最后一个结点 {pre-rtag 1;}}
} void PreThread(ThreadTree T)
{if (T ! NULL){visit(T);if (T-ltag 0) //【解释】{PreThread(T-lchild);}PreThread(T-rchild);}
} void visit(ThreadNode *q)
{if (q-lchild NULL){ //左子树为空建立前驱线索 q-lchild pre;q-ltag 1;}if (pre ! NULL pre-rchild NULL){pre-rchild q; //建立前驱结点的后继线索 pre-rtag 1; } pre q;//记得修改当前访问结点的前驱
} 上述代码基本和中序线索化一模一样只是PreThread函数做了一点变化
【解释】
假设此时pre 在 B结点 q 在D结点即执行完visitD后D - lchild pre B ; D - ltag 1 pre q。然后接着执行PreThread(D - lchild) 但是D - lchild 已经被修改成了指向 B 结点。如果这里不加 if (T - ltag 0) 这个判断那么接下来就要重新又执行回到B结点开始不断的在B 和 D 间 ”转圈圈“ ………… 3.4 后序线索化
后序没有 ”转圈圈“ 的问题 void Create_ThreadTree(ThreadTree T) //后序遍历二叉树一边遍历一边线索化
{if (T ! NULL){PosThread(T) ;if (pre-rchild NULL) //处理遍历的最后一个结点 {pre-rtag 1;}}
}void PosThread(ThreadTree T)
{if (T ! NULL){PosThread(T-lchild);PosThread(T-rchild);visit(T);}
} void visit(ThreadNode *q)
{if (q-lchild NULL){ //左子树为空建立前驱线索 q-lchild pre;q-ltag 1;}if (pre ! NULL pre-rchild NULL){pre-rchild q; //建立前驱结点的后继线索 pre-rtag 1; } pre q;//记得修改当前访问结点的前驱
}
3.5 线索二叉树找前驱和后继
【1】中序线索二叉树
上面我们已经讲解了中序线索二叉树的线索化并且通过线索化我们可以在O1的复杂度找到某个结点Tag 1的前驱和后继结点例如G结点的前驱为D后继为B。
但是如果 Tag 0就不能通过线索直接找到它的前驱和后继结点。例如B结点的中序后继我们无法直接得到【这里不要以为 B - rchild就可以了这里只是一种特殊的情况如果E结点后面还连接很多子树那么B的中序后继结点就可能在其子树中】。
找后继
假设 E结点 后还有p1 、p2、p3 三个结点
那么根据中序遍历的规则肯定是……B p3 p1 E p2.......
所以B的中序后继结点一定是 B 右子树中最左下结点即 p3 //在中序线索二叉树中找到结点P的后继结点ThreadNode *Nextnode(ThreadNode *p)
{if (p-rtag 0) return Firstnode(p-rchild);else return p-rchild;
} //找到 E 为根的子树中第一个被中序遍历的结点
ThreadNode * Firstnode(ThreadNode *p)
{while(p-ltag 0) p p-lchildreturn p;
} 理解了这个算法思想我们还可以利用它们将递归式的线索化过程改为非递归的线索化过程。
这样做的好处可以将空间复杂度降到O1)。 void Inorder(ThreadNode *T)
{for (ThreadNode *p Firstnode(T) ; p ! NULL ; p Nextnode(p)){visit(p);}
} 找前驱
同理找上图中B结点的前驱结点因为其B - ltag 0所以不能直接通过线索找到它的前驱结点。因此根据中序遍历的特点某结点 p 的中序前驱结点一定是其左子树中最右下结点。 ThreadNode * Prenode(ThreadNode *p)
{if (p-ltag 0) return Firstnode(p-lchild);else return p-lchild;
} ThreadNode* Lastnode(ThreadNode *p)
{while(p-rtag 0) p p-rchild;return p;
} 根据这个算法思想我们还可以对中序线索二叉树进行逆向的中序遍历。 void RevInorder(ThreadNode *T)
{for (ThreadNode *p Lastnode(T) ; p ! NULL ; p Prenode(p)){visit(p);}
} 【2】先序线索二叉树
找后继
根据先序遍历的特点若 p - rtag 0。若 p 结点有左孩子则其先序后继一定为其左孩子。若 p结点没有左孩子则其先序后继一定为其右孩子。 ThreadNode* findnextnode(ThreadNode *p)
{if (p-rtag 0){if (p-lchild ! NULL) return p-lchild;else return p-rchild;}else return p-rchild;
} 找前驱
因为先序遍历中左右子树中的结点只可能是根的后继不可能是其前驱因此要想找到 p-ltag 0 的 p结点的先序前驱结点只能再先序遍历一遍。 BiTNode *p ; //p结点是目标结点即找它的前驱结点BiTNode *pre NULL; //指向当前访问结点的前驱BiTNode *final NULL;//用于记录最终结果即p的前驱结点 void findPrenode(BiTree T)
{if (T ! NULL){visit(T);findPrenode(T-lchild);findPrenode(T-rchild);}
}void visit(BiTNode *q)
{if (q p){final pre;}else pre q;} 【3】后序线索二叉树
找前驱
根据后序遍历的特点若 p - ltag 0。若 p 结点有右孩子则其后序前驱一定为其右孩子。若 p结点没有右孩子则其后序前驱一定为其左孩子。 ThreadNode* findprenode(ThreadNode *p)
{if (p-ltag 0){if (p-rchild ! NULL) return p-rchild;else return p-lchild;}else return p-lchild;
} 找后继
因为后序遍历中左右子树中的结点只可能是根的前驱不可能是其后继因此要想找到 p-rtag 0 的 p结点的后序后继结点只能再后序遍历一遍。 BiTNode *p ; //p结点是目标结点即找它的后继结点int flag 0; BiTNode *final NULL;//用于记录最终结果即p的后继结点 void findnextnode(BiTree T)
{if (T ! NULL){findnextnode(T-lchild);findnextnode(T-rchild);visit(T);}
}void visit(BiTNode *q)
{if (flag 1){final q;Flag 0;}if (q p){Flag 1;}
}
四、树的存储结构
4.1 双亲表示法顺序存储
实现定义结构数组存放树的结点.
每个结点含两个域
数据域存放结点本身信息双亲域指示本结点的双亲结点在数组中的位置。 #define MAX_TREE_SIZE 100
typedef struct PTNode {TElemType data;int parent; // 双亲位置域
} PTNode; typedef struct {PTNode nodes[MAX_TREE_SIZE];int r, n; // 根结点的位置和结点个数
} PTree;从这个顺序存储结构我们不难看出查找指定结点的双亲结点很方便但是查找指定结点的孩子只能从头开始遍历一遍。
特点找双亲容易找孩子难
4.2 孩子表示法顺序链式
把每个结点的孩子结点排列起来看成是一个线性表用单链表存储则 n 个结点有 n 个孩子链表叶子的孩子链表为空表。而 n 个头指针又组成一个线性表用顺序表含 n 个元素的结构数组存储。 typedef struct CTNode {int child; //孩子结点在数组中的位置 struct CTNode *next; //下一个孩子
} *ChildPtr;typedef struct {TElemType data;ChildPtr firstchild; // 孩子链表头指针也是第一个孩子
} CTBox;typedef struct {CTBox nodes[MAX_TREE_SIZE];int n, r; // 结点数和根结点的位置
} CTree;
4.3 孩子兄弟表示法链式存储
实现用二叉链表作树的存储结构链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点
⚠️注意孩子兄弟链表的结构形式与二叉链表完全相同但存储结点中指针的含义不同二叉链表中结点的左右指针分别指向该结点的左右孩子而孩子兄弟链表结点的左右指针分别指向它的“长子” 和“大弟”。 typedef struct CSNode{ElemType data; //数据域 struct CSNode *firstchild , *nextsibling; //第一个孩子 和 右兄弟指针
} CSNode , *CSTree;
这种解释上的不同正是 树 与 二叉树 相互转化的内在基础 4.4 森林和二叉树的转换
森林森林是 m (m 0) 棵互不相交的树的集合。
你可以假想有一个结点是 B、C、D的父节点。
同理二叉树转换成森林也是一样的。
总结
五、树和森林的遍历
5.1 树的先根遍历
若树不空则先访问根结点然后依次先根遍历各棵子树。
和先序遍历换汤不换药
5.2 树的后根遍历
若树不空则先依次后根遍历各棵子树然后访问根结点。
5.3 树的层次遍历
若树不空则自上而下自左至右访问树中每个结点。
5.4 森林的先序遍历
先序遍历森林中除第一棵树之外其余树构成的森林。 即依次从左至右对森林中的每一棵树进行先根遍历。
当然将森林转换成二叉树然后根据二叉树的先序遍历得出的结果也是一样的。
5.5 森林的中序遍历
中序遍历森林中除第一棵树之外其余树构成的森林。 即依次从左至右对森林中的每一棵树进行后根遍历注意不是中序哦
当然将森林转换成二叉树然后根据二叉树的后序遍历得出的结果也是一样的。
六、哈夫曼树
基本概念
路径从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。
结点的路径长度两结点间路径上的分支数。
树的路径长度从树根到每一个结点的路径长度之和。记作TL
TLa01122334420
TLb01122223316
完全二叉树是路径长度最短的二叉树。
权将树中结点赋给一个有着某种含义的数值则这个数值称为该结点的权。
结点的带权路径长度从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度树中所有叶子结点的带权路径长度之和。 记作
定义
哈夫曼树也叫最优树 带权路径长度 (WPL) 最短的树。
⚠️注意“带权路径长度最短”是在“度相同”的树中比较而得的结果因此有最优二叉树、最优三叉树之称等等。
带权路径长度 (WPL) 最短的二叉树叫最优二叉树。
因为构造这种树的算法是由哈夫曼于 1952 年提出的 所以被称为哈夫曼树相应的算法称为哈夫曼算法。
哈夫曼树的构造
观察上图我们可以推出如下重要的结论 包含 n 棵树的森林要经过 n–1 次合并才能形成哈夫曼树共产生 n–1 个新结点 包含 n 个叶子结点 的哈夫曼树中共有 2n – 1 个结点。 哈夫曼树的结点的 度数为 0 或 2 没有度为 1 的结点。 权值越小的叶子结点到根节点的路径长度越大 哈夫曼树并不唯一但WPL必然相同且为最优 哈夫曼编码
哈夫曼树的应用很广哈夫曼编码就是其在电讯通信中的应 用之一。在电讯通信业务中通常用二进制编码来表示字母或其他字符并用这样的编码来表示字符序列。
一个好的编码一定
编码总长度更短译码的唯一性问题
首先解决编码总长度更短的问题就是解决数据的最小冗余编码问题 实际应用中各字符的出现频度不相同 为了达到数据的最小冗余编码就要用短长编码表示频率大小的字符使得编码序列的总长度最小使所需总空间量最少 。 为了解决译码的唯一性问题要求任一字符的编码都不能是另一字符编码的前缀 这种编码称为前缀编码其实是非前缀码。 而利用最优二叉树可以很好地解决上述两个问题
由哈夫曼树得到的二进制前缀编码称为哈夫曼编码
当然上述发送的电文还比较短如果几百上千那么它的总长度就会大幅度缩短这种可变的二进制长度编码显然比固定二进制长度编码好
译码
从哈夫曼树根开始对待译码电文逐位取码。若编码是“0” 则向左走若编码是“1”则向右走一旦到达叶子结点则译出 一个字符再重新从根出发直到电文结束。
结尾
最后非常感谢大家的阅读。我接下来还会更新 图 如果本文有错误或者不足的地方请在评论区(或者私信)留言一定尽量满足大家如果对大家有帮助还望三连一下啦
