广州 营销型网站建设公司,学编程多少钱学费,网站维护会导致打不开网页吗?,湖南省交通建设质量监督站网站提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、树的定义1.结点的度、树的度2.结点的逻辑关系3.树的深度4.有序树和无序树5.森林 二、树的存储结构#xff08;1#xff09;双亲表示法#xff08;2… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、树的定义1.结点的度、树的度2.结点的逻辑关系3.树的深度4.有序树和无序树5.森林 二、树的存储结构1双亲表示法2孩子表示法①每个结点的指针域数量等于整个树的度②每个结点的指针域数量等于自己的度③升级改进后的孩子表示法 (3)孩子兄弟表示法 三、二叉树1.背景引出2.二叉树的特殊形态1斜树2满二叉树3完全二叉树 3.二叉树的性质4.二叉树的存储结构5.二叉树的遍历算法前序、中序、后序①前序遍历②中序遍历③后序遍历 6.已知前序/中序/后序三者中的其二,求另外一个7.建立一颗二叉树 六、线索二叉树七、赫夫曼树 前言
前面说数据的逻辑结构包括线性结构和非线性结构线性结构学了线性表顺序表与链表、栈与队列、串等而现在要接触的树是非线性结构它是一对多的关系更加复杂。
一、树的定义 1.结点的度、树的度
1结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点。除根结点之外分支结点也称为内部结点。比如D有三个子树度为3C有两个子树度为2。
2树的度是树内各结点的度的最大值。如图6-2-4所示因为这棵树结点的度的最大值是结点D的度为3,所以树的度也为3。
2.结点的逻辑关系 结点的子树的根称为该结点的孩子Child)相应地该结点称为孩子的双亲(Parent)。嗯为什么不是父或母叫双亲呢?对于结点来说其父母同体唯一的一个所以只能把它称为双亲了。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说,D、B、A 都是它的祖先。反之以某结点为根的子树中的任一结点都称为该结点的子孙。
3.树的深度
结点的层次Level)从根开始定义起,根为第一层根的孩子为第二层。若某结点在第1层则其子树的根就在第l1层。其双亲在同一层的结点互为堂兄弟。显然图6-2-6中的D、E、F是堂兄弟而G、H、1、J也是。树中结点的最大层次称为树的深度(Depth)或高度当前树的深度为4。
4.有序树和无序树
如果将树中结点的各子树看成从左至右是有次序的不能互换的则称该树为有序树否则称为无序树
5.森林 二、树的存储结构
树的存储结构不同于线性表由于结构的差异很难用顺序结构来表示这里产生了针对树的三种存储结构 1双亲表示法每个节点除了数据域外还包含一个指向父节点的指针。根节点的指针为空。这种存储结构方便查找父节点但是查找子节点需要遍历整个树。
2孩子表示法每个节点包含一个指向第一个子节点的指针以及一个指向兄弟节点的指针。这种存储结构方便查找子节点和兄弟节点但是查找父节点需要遍历整个树。
2孩子兄弟表示法每个节点包含一个指向第一个子节点的指针以及一个指向下一个兄弟节点的指针。这种存储结构比较灵活可以表示任意树形结构但是查找父节点需要遍历整个树。
1双亲表示法
我们人可能因为种种原因没有孩子但无论是谁都不可能是从石头里出来的所以是人一定会有父母。树这种结构也不例外除了根结点外其余每个结点它不一定有孩子但是一定有且仅有一个双亲。 我们假设以一组连续空间存储树的结点同时在每个结点中附设一个指示器指示其双亲结点到链表中的位置。也就是说每个结点除了知道自己是谁以外还知道它的双亲在哪里。它的结点结构为表6-4-1所示。
其中 data是数据域存储结点的数据信息。而 parent是指针域,存储该结点的双亲在数组中的下标。所以它与链表还是有区别的链表指针域存储的是后驱结点的地址。 所以我们可以通过一个结点很容易找到其双亲结点但是很难找到其孩子节点。
如果需要解决找到孩子结点的问题当然可以再拓展一个指针域用来存储一个长子的位置。
2孩子表示法
顾名思义每一个结点除了自己的数据域外指针域存储了自己的孩子结点的位置。
①每个结点的指针域数量等于整个树的度 很明显最大的缺点就是每个结点的子节点个数不一致所以会空出许多空间没有被利用浪费存储空间。
②每个结点的指针域数量等于自己的度 这也有缺点每个结点的存储结构不同看着很费劲。
③升级改进后的孩子表示法
为了既可以节省存储空间又可以将存储结构看起来整齐划一设计了升级版的孩子表示法 如图对于一棵树变成了顺序表链表的形式每个结点的数据和长子指针构成了一个顺序结构的一维数组然后每个节点的长子结点又引出链式结构指向第二个孩子第二个孩子结点又有一个next指针指向后驱结点即第三个孩子如此往复。 孩子表示法结构体
(3)孩子兄弟表示法
刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构如果我们从树结点的兄弟的角度又会如何呢?当然对于树这样的层级结构来说只研究结点的兄弟是不行的我们观察后发现任意一棵树它的结点的第一个孩子如果存在就是唯一的它的右兄弟如果存在也是唯一的。因此我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。 简而言之一个结点的数据域是自己的数据两个指针域第一个指向自己的长子第二个指向自己的右边的兄弟。
三、二叉树
1.背景引出
我们玩猜数字游戏 猜0-100中的某个数可以使用二分法。先猜50大则猜25小则猜75然后再次二分。 这种结构就叫二叉树结构。二叉树是一种特殊的树结构每个节点最多有两个子节点分别称为左子节点和右子节点。
二叉树的特点有: ①每个结点最多有两棵子树所以二叉树中不存在度大于2的结点。注意不是只有两棵子树而是最多有。没有子树或者有一棵子树都是可以的。 ②左子树和右子树是有顺序的次序不能任意颠倒。就像人是双手、双脚但显然左手、左脚和右手、右脚是不一样的右手戴左手套、右脚穿左鞋都会极其别扭和难受。 ③即使树中某结点只有一棵子树也要区分它是左子树还是右子树。图6-5-3中树1和树2是同一棵树但它们却是不同的二叉树。就好像你一不小心摔伤了手伤的是左手还是右手,对你的生活影响度是完全不同的。
2.二叉树的特殊形态
1斜树 斜树是一种特殊的二叉树所有的节点都只有左子节点或右子节点没有同时拥有左子节点和右子节点的节点。斜树可以分为左斜树和右斜树具体取决于所有节点只有左子节点或右子节点。
2满二叉树 满二叉树是一种特殊的二叉树除了叶节点外每个节点都有两个子节点。满二叉树的特点是所有的叶节点都在同一层上并且除了叶节点外每个节点的度数都是2。
3完全二叉树 完全二叉树是一种特殊的二叉树除了最后一层外其他层的节点都是满的且最后一层的节点都靠左排列。也可以说完全二叉树是一颗二叉树中从上到下、从左到右依次填满节点的二叉树。
3.二叉树的性质
二叉树具有以下性质
每个节点最多有两个子节点每个节点最多有两个子节点分别称为左子节点和右子节点。如果一个节点没有子节点称为叶节点。
左子树和右子树的顺序不能颠倒二叉树的左子树和右子树的顺序不能颠倒即左子节点在右子节点之前。
每个节点的子树也是二叉树二叉树的每个节点的子节点也是二叉树即每个节点都可以看作是根节点。
二叉树的高度二叉树的高度是指从根节点到最深叶节点的路径上的节点数。树中的节点数目为n那么二叉树的高度最大为n-1最小为log2(n1)。
二叉树的遍历二叉树的遍历有三种常用的方式分别是前序遍历、中序遍历和后序遍历。前序遍历先访问根节点然后递归访问左子树和右子树。中序遍历先递归访问左子树然后访问根节点最后递归访问右子树。后序遍历先递归访问左子树和右子树最后访问根节点。
二叉搜索树Binary Search Tree简称BST二叉搜索树是一种特殊的二叉树其中每个节点的值都大于其左子树中的任意节点的值且小于其右子树中的任意节点的值。这使得在二叉搜索树中进行搜索、插入和删除操作的时间复杂度为O(logn)其中n为树中节点的数量。
4.二叉树的存储结构
链式结构一个数据域两个指针域分别存放指向左孩子和右孩子的指针。
5.二叉树的遍历算法前序、中序、后序
①前序遍历 关键思路就是先根结点再左后右。根节点不是指A指的是每一次遍历到的当前结点就看作根节点 遍历每个结点的顺序是ABDHKECFIGJ
②中序遍历
关键思路是先左后根节点再右节点。 遍历每个结点的顺序是HKDBEAIFCGJ
③后序遍历
关键思路是先左再右根节点最后访问。 遍历每个结点的顺序是KHDEBIFJGCA
6.已知前序/中序/后序三者中的其二,求另外一个
不过多解释反正用脑子分析就行。理解原理然后就跟推理一样慢慢分析即可。 注意已知前序和后序无法求出中序。
7.建立一颗二叉树
#include stdio.h
#include stdlib.h// 定义二叉树节点结构体
typedef struct TreeNode {int val;struct TreeNode* left;struct TreeNode* right;
} TreeNode;// 创建二叉树节点
TreeNode* createNode(int val) {TreeNode* newNode (TreeNode*)malloc(sizeof(TreeNode));if (newNode NULL) {printf(内存分配失败\n);exit(1);}newNode-val val;newNode-left NULL;newNode-right NULL;return newNode;
}// 构建二叉树
TreeNode* buildTree() {int val;printf(输入节点的值输入-1表示空节点);scanf(%d, val);if (val -1) {return NULL;}TreeNode* root createNode(val);printf(构建左子树\n);root-left buildTree();printf(构建右子树\n);root-right buildTree();return root;
}思路buildTree 函数可以递归地创建左右子节点是因为在构建二叉树的过程中每次调用 buildTree 函数都是在当前节点的基础上构建其左右子树。
具体来说函数首先提示用户输入节点的值如果输入值为 -1则表示该节点为空返回 NULL。否则创建一个新的节点并递归地调用 buildTree 函数来构建当前节点的左子树和右子树。
在递归调用中每次调用都会创建一个新的节点并将其赋值给当前节点的左子树或右子树指针。然后在新的节点上再次调用 buildTree 函数来构建其左子树和右子树。这样通过递归的方式就可以逐层构建整个二叉树的节点。
当用户输入 -1 表示节点为空时会逐层返回 NULL即构建空节点。这样递归调用结束后就完成了整个二叉树的构建过程。
六、线索二叉树
线索二叉树是对二叉树的一种改进它通过添加线索thread来加快对二叉树的遍历操作。线索二叉树中除了存储节点的值和左右子树指针外还添加了线索指针用于指向前驱节点或后继节点。
具体来说线索二叉树中的线索指针可以分为两种类型
前驱线索对于每个节点线索指针可以指向其在中序遍历中的前驱节点。 后继线索对于每个节点线索指针可以指向其在中序遍历中的后继节点。 线索化二叉树的过程主要包括两个步骤
线索化左子树在线索化当前节点的左子树时需要将当前节点的前驱线索指针指向其在中序遍历中的前驱节点并将前驱线索指针的后继线索指针指向当前节点。 线索化右子树在线索化当前节点的右子树时需要将当前节点的后继线索指针指向其在中序遍历中的后继节点并将后继线索指针的前驱线索指针指向当前节点。 线索化完成后可以通过线索指针直接找到任意节点的前驱节点和后继节点从而加速对二叉树的遍历操作。
七、赫夫曼树
赫夫曼树Huffman Tree也称为最优二叉树Optimal Binary Tree是一种特殊的二叉树结构常用于数据压缩算法中的赫夫曼编码。
赫夫曼树的构建过程基于赫夫曼算法其核心思想是将出现频率较高的字符或数据项放在离根节点较近的位置而出现频率较低的字符或数据项放在离根节点较远的位置以实现高效的压缩。
具体构建赫夫曼树的步骤如下
给定一组字符或数据项及其出现频率根据频率从小到大排序作为初始的叶子节点集合。
从初始的叶子节点集合中选择出现频率最小的两个节点作为左右子节点并创建一个新的节点作为它们的父节点父节点的频率为左右子节点频率之和。
将父节点加入到叶子节点集合中并从集合中删除被合并的两个子节点。
重复步骤2和步骤3直到只剩下一个节点该节点即为赫夫曼树的根节点。
赫夫曼树的构建过程可以通过使用优先队列Priority Queue来实现每次从队列中选择频率最小的两个节点进行合并。
赫夫曼树的特点是出现频率较高的字符或数据项在树中的路径较短而出现频率较低的字符或数据项在树中的路径较长。这样在进行赫夫曼编码时可以用较短的编码表示较高频率的字符或数据项从而实现数据的压缩。
赫夫曼树在数据压缩中具有重要的应用能够有效地压缩数据并保证数据的可恢复性。
具体的赫夫曼树的图解、代码实现、性质作用等内容以后有机会再补充这里仅了解一下。
