数据结构
2022-03-24 18:55:49 0 举报AI智能生成
数据结构之树结构
作者其他创作
大纲/内容
初识数据结构
算法的复杂度
栈与队列
排序与递归
哈希与矩阵
树结构
初识树
树的定义与特点
定义
由一个或多个（n >= 0）节点组成的有限集合T，且仅有一个节点称为根（Root），当n > 1时，其余节点分为m（m >= 0）个互不相交的有限集合（T1、T2、T3。。。Tm）每个集合本身又是一棵树，常被称为根（Root）的子树。
特点
树的定义具有递归性质，即树中有树，最终成树。
相关术语及名词解释
根
即根节点（没有前驱）
叶子
即终端节点（没有后继）
*森林
是指m棵互不相交的树的集合（例如没有根节点的子树其集合就被称为森林）
*有序树
节点各子树（T1、T2、T3。。。Tm）从左至右有序，不能互换（左为第一）
*无序树
节点各子树可互换位置
双亲
即上层的那个节点（直接前驱，parent）
孩子
即下层结点的子树（直接后继，child）
兄弟
同一双亲下的同层节点（孩子之间互称兄弟，sibling）
堂兄弟
双亲位于同一层次的节点（非同一双亲，cousin）
祖先
从根到该结点所经分支的所有节点
子孙
该节点下层子树中的任一节点
*结点
是指树的数据元素（个人理解：节点是常名，结点是变名，原因无他，数据元素是可变的，犹如const 和 let的声明，但都是同一个指引）
*节点的度
节点挂接的子树数（有几个直接后继就是几度，又可以看作有多少个孩子就有多少个度）
*节点的层次
从跟到该节点的层数（根节点算第一层）
*终端节点
度为0的节点（个人称其为断子绝孙的节点），如：叶子节点、没有度的根节点
*分支节点
除树根以外的节点（内部节点）
*树的度
所有节点度中的最大值（Max{各节点的度}，拓展：数学表达式Max{}意为取括号里数列中最大的那个值）
*树的深度
所有节点中最大的层数（Max{各节点的层次}）
树的存储结构
双亲表示法
用指针表示出每个结点的双亲结点
优点：寻找一个结点的双亲结点操作实现很方便
缺点：寻找一个结点的孩子结点很不方便
孩子表示法
用指针指出每个结点的孩子结点
优点：寻找一个结点的孩子结点比较方便
缺点：寻找一个结点的双亲结点很不方便
双亲孩子表示法
用指针既表示出每个结点的双亲结点，也表示出每个结点的孩子结点
孩子兄弟表示法
表示出第一个结点的第一个孩子结点，也表示出每个结点的下一个兄弟结点
树之二叉树
概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成
特点
每个结点最多有两棵子树
二叉树的子树有左右之分，其次序不能颠倒
满二叉树
所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上
完全二叉树
如果一棵具有N个结点的二叉树的结构与满二叉树的前N个节点 的结构相同，称为完全二叉树（特别说明：满二叉树是特殊的完全二叉树，而完全二叉树不一定是满二叉树）
二叉树的性质
若规定根节点的层次为1，则一棵非空二叉树第n层上最多有2^（n-1）（n>=1）个结点，（^代表次方）
若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^ (n-1) (n>=0)，特别说明：这里的深度与上面的层次概念只不过是换一种的说法
对任何一棵二叉树，如果其叶结点个数为n0，度为2的非叶结点个数为n2,则有n0 = n2+1
具有n个结点的完全二叉树，如果按照从上至下从左到右的顺序对所有结点从1开始编号，则对于序号为i的结点有：
如果i>1，则序号为i的结点的双亲结点的序号为i/2取整 如果i=1，则序号为i的结点为根节点，无双亲结点
如果2i<n，则序号为i的双亲结点的左孩子序号是2i右孩子序号是2i+1 如果2i>=n，则序号为i结点无右孩子结点
如果2i+1<=n，则序号为i结点的右孩子结点的序号为2i+1
如果2i+1>n，则序号为i结点无右孩子结点
二叉树的存储结构
顺序存储（就是用一组连续的存储单元存放二叉树中的结点）
优点：存储完全二叉树，简单省空间，如上图
缺点：对一般二叉树尤其单支树，存储空间利用不理想，如上图
链式存储（就是用链表来表示一棵二叉树，即用链来指示元素的逻辑关系）
包含数据域和左右指针域的链表
增加一个双亲字段parent,用来指向其双亲结点的链表
二叉树的基本操作
二叉树的创建
依照顺序存储结构来创建（如上的存储结构所述）
依照链式存储结构来创建（如上的存储结构所述）
二叉树的遍历
前序遍历（遵循先遍历双亲结点后再遍历左结点最后才遍历右结点的顺序，简称：中左右）打印的顺序为：12485367
中序遍历（遵循先遍历左结点后遍历双亲结点再最后才遍历右结点的顺序，简称：左中右）打印的顺序为：84251637
后序遍历（遵循先遍历左结点后遍历右结点再最后才后遍历双亲结点的顺序，简称：左右中）打印的顺序为：84526731
层序遍历（前面的都是深度优先而层级遍历则是广度优先）打印顺序为：12345678
线索化二叉树
线索化概念
按照二叉树的遍历将二叉树导成一个线性序列
普通二叉树可能存在的问题
递归遍历有可能导致栈溢出
非递归版本可能会降低程序的效率
想要找到某种遍历形式下某个节点的前驱还是后继比较难
树中有大量的空指针域造成浪费
线索二叉树
定义：二叉树的结点加上线索后的的二叉树
线索
结点中指向前驱或者后继结点的指针
线索标识位
作用区分是孩子结点还是前驱或者后继
线索化过程
当某结点的左指针为空时，令该指针指向按照某种方式遍历二叉树时得到该结点的前驱节点
当某结点的右指针为空时，令该指针指向按照某种方式遍历二叉树时得到该结点的后继结点
二叉搜索树
性质
如果左子树不为空，则左子树上所有节点的值都小于根结点的值
它的右子树不为空，则右子树上所有节点的值都大于根结点的值
它的左右子树也分别为二叉搜索树（或称：二叉查找树）
操作
搜索
若根结点不为空
根结点key==要查找的key，返回查找key对应的结点
根结点key>查找key，在其左子树查找
根结点key<查找key，在其右子树查找
否则返回null
插入
首先检测这个节点是不是已经存在，要是存在不插入（如果树的根节点为空则创建其为树的根节点），否则将元素插入到找到的位置
删除
首先判断是否在树中，没有直接返回
有的情况
要删除的节点没有孩子节点
直接删除该结点（如图需要删除的是key值为27的叶结点过程）
要删除的节点只有左孩子
删除该结点并使被删除结点的双亲结点指向被删除结点的左孩子结点
要删除的节点只有右孩子
删除该结点并使被删除结点的双亲结点指向被删除结点的右孩子结点
*要删除的节点有左、右孩子结点
需要找到这个节点的右子树上的最小结点【记为H】（因为它没有左子节点），把【H】替换到我们计划删除的节点上；然后，再删除这个最小的节点【H】（因为它没有左子节点，所以可以转化成之前的两种情况之一）。特别说明：找到某个节点的右子树上的最小结点就意味着这个最小结点是没有左子树的了，因为如果它还有左子树那就说明它还未是最小值故而还需要往左子树继续查找最小结点。
【H】结点是一个叶子结点的情况（如图需要删除的是key值为20的结点的过程）
【H】结点是一个非叶子结点的情况（如图依旧是需要删除的是key值为20的结点的过程）
加深理解图
二叉搜索树性能分析
对于二叉查找树来说，不管是插入、删除还是查找操作，时间复杂度都和树的高度成正比，也就是O(H)，因为每次操作都对应了一条从根节点向下的一条路径。而对于树的高度，却很可能因树的形状的不同而不同。
理想情况下，二叉查找树是一颗完全二叉树，每层的节点依次为 1、2、4、8、16…………，不难发现，树的高度为log(N),所以时间复杂度为 O(logN),这是一个相当高效的算法了
最坏情况依旧是O(N)。二叉查找树在一定条件下可能会退化成链表，如图所示，这就是一个弯曲的链表。
AVL树
AVL树的概念与性质
AVL树概念
上面说到二叉搜索树虽然可以提高我们查找数据的效率，但如果插入二叉搜索树的数据是有序或接近有序的，此时二叉搜索树会退化为单支树，在单支树当中查找数据相当于在单链表当中查找数据，效率是很低下的，因此两位俄罗斯的数学家（名字简称：G.M.Adelson-Velskii和E.M.Landis）在1962年发明了解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。故而AVL树又被称为平衡二叉树（Balanced Binary Tree）。
AVL树性质
它的左右子树都是AVL树
左子树和右子树高度之差（简称平衡因子）的绝对值不超过1（即整数值只有-1、0、1这三位兄弟）
如果一棵树是高度平衡的，它就是AVL树。如果它有n个节点，其高度可保持在0(lgn)，平均搜索复杂度O(lgn)，特别说明：这里所说的二叉搜索树的高度是平衡的是指：树中每个结点左右子树高度之差的绝对值不超过1，因为只有满二叉树才能做到每个结点左右子树高度之差均为0（而lgn是以10为底n的对数）
AVL树的插入
按照二叉搜索树的插入方法，找到待插入位置（如果是空树，插入后即为根结点）
回顾一下二叉搜索树的插入规则
待插入结点的key值比当前结点小就插入到该结点的左子树
待插入结点的key值比当前结点大就插入到该结点的右子树
待插入结点的key值与当前结点的key值相等就插入失败
找到待插入位置后，将待插入结点插入到树中
更新平衡因子，如果出现不平衡，则需要进行旋转
与二叉搜索树插入结点不同的是：AVL树插入结点后需要更新树中结点的平衡因子，因为插入新结点后可能会影响树中某些结点的平衡因子
由于一个结点的平衡因子是否需要更新，是取决于该结点的左右子树的高度是否发生了变化，因此插入一个结点后，该结点的祖先结点的平衡因子可能需要更新
所以我们插入结点后需要倒着往上更新平衡因子，更新规则如右
新增结点在parent的右边，parent的平衡因子+ +（即自增1）
新增结点在parent的左边，parent的平衡因子− −（即递减1）
而每更新完一个结点的平衡因子后，都需要进行如右所描述的判断
如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子（说明新结点的插入使得parent的左子树或右子树增高了，即改变了以parent为根结点的子树的高度，从而会影响parent的父结点的平衡因子，因此需要继续往上更新平衡因子）
如果parent的平衡因子等于0，表明无需继续往上更新平衡因子了（说明新结点插入到了parent左右子树当中高度较矮的一棵子树，插入后使得parent左右子树的高度相等了，此操作并没有改变以parent为根结点的子树的高度，从而不会影响parent的父结点的平衡因子，因此无需继续往上更新平衡因子）
如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理（说明此时parent结点的左右子树高度之差的绝对值已经超过1了，不满足AVL树的要求，因此需要进行旋转处理）
由于我们插入结点后需要倒着往上进行平衡因子的更新，所以我们将AVL树结点的结构设置为了三叉链结构，这样我们就可以通过父指针找到其父结点，进而对其平衡因子进行更新（三叉链结构如图所示）
在更新平衡因子的过程当中出现了平衡因子为-2或2的结点时，我们则需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种，在进行分类之前我们首先需要进行分析
将插入结点称为current（即也是代码中的指针），将其父结点称为parent（即也是代码中的指针），那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新则必定要执行current变为parent而parent变为parent的parent的逻辑。（高度总结就是指引在跑），特别说明：当parent的平衡因子为-2或2时，current的平衡因子必定是-1或1而不会是0。理由是：若current的平衡因子是0，那么current一定是新增结点，而不是上一次更新平衡因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新，而current是新增结点的话，其父结点的平衡因子更新后一定是-1、0、1这三兄弟之一，而不可能是-2或2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：①其父结点是一个左右子树均为空的叶子结点，其平衡因子是0，新增结点插入后其平衡因子更新为-1或1。②其父结点是一个左子树或右子树为空的结点，其平衡因子是-1或1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中较矮的一棵子树增高了，新增结点后其平衡因子更新为0。所以得出的结论就是当parent的平衡因子为-2或2时，cur的平衡因子必定是-1或1而不会是0
根据上述分析后我们可以将旋转处理分为四类，继下所述
平衡化旋转（依据上述分析进行演示）
左单旋（即当parent的平衡因子为2，current的平衡因子为1时）
演示图（parent的因子为2即值为10对应的结点的因子为2，而当前节点current就是值13对应的结点而它的平衡因子为1，故需要进行左单旋转）
右单旋（即当parent的平衡因子为-2，current的平衡因子为-1时）
演示图（parent的因子为-2即值为7对应的结点的因子为-2，而当前节点current就是值5对应的结点而它的平衡因子为-1，故需要进行右单旋转）
左右双旋（即当parent的平衡因子为-2，current的平衡因子为1时）
演示图（parent的因子为-2即值为7对应的结点的因子为-2，而当前节点current就是值5对应的结点而它的平衡因子为1，故需要进行左右旋转）
右左双旋（即当parent的平衡因子为2，current的平衡因子为-1时）
演示图（parent的因子为2即值为10对应的结点的因子为2，而当前节点current就是值13对应的结点而它的平衡因子为-1，故需要进行右左旋转）
AVL树的删除
删除结点的方法和二叉搜索树相同
先找到待删除的结点
若找到的待删除结点的左右子树均不为空，则需要使用替换法进行删除
Huffman树
概念
哈夫曼树是给定n个权值作为n个叶子结点（即也是n个度为0的根结点）进行构造的一棵二叉树，若该树的带权路径长度达到最小时则称这样的二叉树为最优二叉树则也称为哈夫曼树(Huffman Tree)
构造Huffman树
构造n棵只有根结点的二叉树森林，每棵二叉树都只有一个带有权值的根结点
重复步骤，直到F中只剩下一棵树
在二叉树森林中选最小的两个，作为左右子树构建一棵新的二叉树，新二叉树的根结点的权值为左右子树根结点的权值之和
在原来二叉树森林里删除这两棵二叉树
把新的二叉树加入二叉树森林
Huffman编码
什么是编码
在数据通信中经常把传输的文字转换成二进制字符0和1组成的二进制串，这叫做编码
编码的问题
在信息传输过程中，一个字母出现地越多，那么我们希望它越瘦小（编码短）这样占用的编码就越少，其实编码长的字母也是让频率比它多的字母把编码短的位子都占用后，它才去占用当前最短的编码。至此让总的编码长度最短，且要保证长编码的不与短编码的字母冲突（比如不能出现读码读到01还有长编码的字母为011，如果短编码为一个长编码的左起子串，这就是冲突，意思就是说读到当前位置已经能确定是什么字母时不能因为再读取一位或几位让这个编码能表示另外的字母）。
哈夫曼编码
那么哈夫曼树怎么避免左起子串问题呢？
因为哈夫曼是从叶子节点开始构造，构造到根节点的，而且构造时，都是计算两个权值的节点的和再与其他叶子节点再生成一个父节点来组成一个新的树。并且不允许任何带有权值的节点作为他们的父节点。这也保证了所有带有权值的节点都被构造为了叶子节点。然后最后编码的时候是从根节点开始走到叶子节点而得出的编码。(高度总结：因为哈夫曼树的它的字母都在叶子节点上，因此不会出现一个字母的编码为另一个字母编码左起子串的情况)
在上述的构造哈夫曼树中生成对应的字符编码如图（每个字符的二进制编码为[从根节点 数到对应的叶子节点，路径上的值拼接起来就是叶子节点字母的应该的编码]）
B树
红黑树
堆
图结构
收藏
收藏
0 条评论
下一页
