数据结构篇_知识点板块_第五章树与二叉树

2022年05月11日 阅读数:3
这篇文章主要向大家介绍数据结构篇_知识点板块_第五章树与二叉树,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
  • 数据结构篇为本人考研时所写笔记,包括知识点和编程思想两大板块,笔记内容依据王道数据结构考研书所写,但比书本上知识更加生动形象,愿本篇章能对您有所帮助

5、树与二叉树

(一)树基本概念

  1. 树的定义是递归的,故数是一种递归的数据结构,同时也做为一种逻辑结构,同时也是一种分层结构html

  2. 树的表示方法:算法

① 树形表示法编程

② 嵌套集合表示法数组

③ 凹入表表示法数据结构

④ 广义表表示法oop

  1. 基本术语:

① 祖先(与子孙对应):从根到结点的惟一路径上的任意结点性能

② 双亲(与孩子对应):路径上最接近该结点的连线的上层结点优化

③ 兄弟(sibling):有相同双亲的结点编码

④ 结点的出度:结点拥有的非空子树数目.net

⑤ 结点的入度:指向结点的分支数目

⑥ 结点的度:树中一个结点的孩子个数,即该结点的出度

⑦ 树的度:树中结点的最大度数

⑧ 分支结点(非终端结点、非叶子节点):度大于0的结点

⑨ 叶子节点(终端节点):度为0的结点

⑩ 内部结点:根结点以外的分支结点

⑪ 堂兄弟:在同一层的结点

⑫ 结点的层次:从树根开始定义,树根为第1层依次往下

⑬ 结点的深度:从根节点开始自顶向下逐层累加(注意题目中的深度是从0仍是1开始计算的,默认从1开始)

⑭ 结点的高度:从叶节点开始自底向上逐层累加(同上,默认最底下的高度为1)

⑮ 树的高度/深度是树中结点的最大层数

⑯ 有序树:各子树从左到右是有次序的,不能互换,反之无序树

⑰ 结点间路径:这两个结点之间所通过的结点序列构成,树中分支是有向的(从双亲指向孩子),故树中路径是从上往下的

⑱ 路径长度:路径上所通过的边的个数

⑲ 树的路径长度:树根到每一个结点的路径长的总和

度为m的树 m叉树
任意结点的度≤m(最多m个孩子) 任意结点的度≤m(最多m个孩子)
至少有一个结点度=m(有m个孩子) 容许全部结点的度都<m
必定是非空树,至少有m+1个结点 能够是空树

(二)二叉树

  1. 二叉树≠度为2的树≠度为2的有序树

  2. 若二叉树用二叉链表作存储结构,则在N个结点的二叉树链表中只有N-1个非空指针域(由于N个节点的二叉树,若用二叉链表表示 则每一个节点都有两个链域也就是2N个,而后除了根节点外每一个节点都能但只能被指一次,因此有N-1个链域不为空,于是有N+1个链域为空)

  3. 不容许两个结点值相等

  4. 五种特殊二叉树(二叉树不是树的特殊形式,这是两种不一样的数据结构):

 满二叉树:树中每层都含最多的结点

(1) 高度为h,则结点数为2h-1,叶节点数为2(h-1)

(2) 若按程序编号(自上而下,自左而右),根节点为1号,对于编号为i的结点,双亲为:向下取整(i/2);左孩子:2i;右孩子:2i+1

 彻底二叉树(若同满二叉树编号):

(1) 若i<=向下取整(n/2)则结点i为分支节点

(2) 若n为奇数,则每一个分支结点都有左孩子和右孩子(除去根节点能够对半分)

若n为偶数,编号最大的分支结点(编号为n/2)只有左孩子

 二叉排序树BST):

(1) 左结点值<根值<右结点值

(2) 插入新结点不会引发树的分裂组合

(3) 插入顺序不一样,获得的二叉排序树不一样

(4) 查找效率取决于树的高度,最好(为平衡二叉树时,与折半查找相同)为O(log_2n),最坏为O(n)

(5) 插入、创建的算法平均时间是O(nlogn),但其执行时间是堆排序的2-3倍

(6) 当各关键字相等时,最佳二叉排序树应是高度最小的二叉排序树,构造方法:

​ (1 首先对各关键字按值从小到大排序

​ (2 而后仿照折半查找的断定树构造法构造二叉排序树

(7) 与二分查找的比较:

​ (1 维护表的有序性时,二叉排序树只需修改指针便可,时间复杂度为O(log_2n),而二分查找因是有序顺序表故为O(n)

​ (2 当有序表是静态查找表时,宜用顺序表做为存储结构,采用二分查找

​ (3 当有序表是动态查找表时,宜用二叉排序树

(8) 对于非空二叉排序树T1删除结点v造成的T2又插入结点造成的T3而言:

(1 若v是T1的叶结点,则T1与T3相同

(2 若v不是T1的叶结点,则T1与T3不一样

 平衡二叉树(AVL):

(1) 左子树深度-右子数深度(此高度差又称平衡因子(BF))只能是1/0/-1(平衡因子的含义和计算方法)

(2) 含有n个结点的平衡二叉树的最大深度为O(log_2n)(也为平均查找长度)

(3) 最后插入的结点不必定为叶子结点,由于可能会致使平衡调整

(4) 对于非空二叉平衡树T1删除结点v造成的T2又插入结点造成的T3而言:

​ (1 若v是T1的叶结点,则T1与T3可能不相同

(5) 插入操做(写完题记得检查是否符合左<根<右):

​ (1 每次调整的对象都是最小不平衡子树

​ (2 只有左孩子才能右上旋(L)(把A(最小不平衡对象)的左子树根节点代替它,并把其右子树链接为本身的左子树),只有右孩子才能左上旋(R)(把A(最小不平衡对象)的右子树根节点代替它,并把其左子树链接为本身的右子树)

​ (3 插入在左子树的左孩子进行LL

​ 插入在右子树的右孩子进行RR

​ 插入在左子树的右孩子进行LR

​ 插入在右子树的左孩子进行RL

 线索二叉树(TBT)(加上线索的二叉树,为一种存储结构,是一种物理结构):

(1) 优势:加快了查找结点的前驱和后继的速度

(2) 线索化的实质是遍历一次二叉树,由于前驱和后继信息只有在遍历时才能获得

(3) 至少包含五个域:数据域(data)、左指针域(lchild)、右指针域(rchild)、左标志域(ltag,为1时指向结点的后继)、右标志域(rtag,为1时指向结点的前驱)

(4) 线索链表:以这种结点结构构成的二叉链表

​ 线索:指向结点前驱和后继的指针

  1. 彻底二叉树和满二叉树采用顺序存储比较合适

  2. 二叉树存储结构:

① 顺序存储结构(从数组下标为1开始存储):

(1) 为了让数组下标能反映结点之间关系,只能用0来代替添加一些并不存在的空结点

(2) 最坏状况下,高度为h且只有h个结点的单支树须要占据近2^h-1个存储单元

② 链式存储结构:至少包含三个域:数据域(data)、左指针域(lchild)、右指针域(rchild)

  1. 若题目中结点数值很大通常采用特殊值法

  2. 二叉树的遍历:

① 先序(序指的是根节点什么时候被访问)(NLR),中序(LNR),后序(LRN)-填空可能考英文名称

② 平均查找长度(ASL)和查找失败平均长度(ASL)(即计算树中全部空结点(层数算为空结点的双亲的层数)的查找长度)-除不清可写分数,也要用大O表示法表示

③ 时间复杂度都是O(n);

递归遍历中,递归工做栈的栈深刚好为树的深度,最坏状况下,二叉树为n个结点且深度为n的单支树,此时空间复杂度为O(n)(精确值应为树的深度+1,由于叶子的空域也递归了一次)

(三)树、森林、并查集

  1. 树的顺序存储结构和二叉树的顺序存储结构的区别:

① 树:数组下标表明结点的编号,下标中所存的内容指示告终点之间的关系

② 二叉树:数组下标既表明告终点的编号,又指示了二叉树中各结点之间的关系,固然二叉树属于树因此也可用树的存储结构

  1. 树的存储结构:

① 数组表示法:

② 双亲链表表示法:采用一组连续的空间来存储每一个结点,同时在每一个结点中增设一个伪指针,指示其双亲结点在数组中的位置,设域data和parent

③ 孩子链表表示法:将每一个结点的孩子结点都用单链表连接起来造成一个线性结构,设域data和firstchild

④ 孩子兄弟链表表示法(又称二叉树表示法):每一个结点包括三部分:节点值、指向结点第一个孩子结点的指针、指向结点下一个兄弟结点的指针,设域leftchild、data、rightchild

(1) 优势:能够方便的实现树转换为二叉树的操做

(2) 缺点:从当前结点查找其双亲结点比较麻烦

  1. 树转换为二叉树(完成后无右子树)的规则(二叉树转树则反操做):

① 每一个结点左指针指向它的第一个孩子

② 右指针指向它在树中相邻的右兄弟

③ 二叉树形态惟一

④ 根结点的右子树必定为空

  1. 林转换为二叉树(二叉树转树则反操做):写题时要分清是树仍是森林转二叉树

① 先将森林中每棵树转换为二叉树

② 将第二棵看成第一棵二叉树的右子树,以此类推

③ 二叉树形态惟一

  1. 树和森林的遍历(名字不要记混了):

① 树的先根遍历:先访问根结点,再依次按照二叉树的先序遍历遍历每棵树,其遍历序列与这棵树相应的二叉树的先序序列相同

② 树的后根遍历:先访问根结点的每棵子树,再访问根结点,其遍历序列与这棵树相应的二叉树的中序序列相同

③ 先序遍历森林:先序遍历第一棵树,以此类推

④ 中序遍历森林(部分教材称为后根遍历/中根遍历):中序遍历第一棵树,以此类推

  1. 并查集(合并查询的集合):

① 

② 一般用树的双亲表示法做为并查集的存储结构

③ 变成树的过程即属于同一个集合的连成一棵树

④ 合并两个子集合:只需将其中一个子集合根结点的双亲结点指向另外一个集合的根结点

⑤ 并查集的优化(路径压缩):把每一个元素直接链接到所在集合(树)的根上

(四)哈夫曼树(最优二叉树)和哈夫曼编码

  1. 带权路径长度最小到二叉树称为最优二叉树/哈弗曼树

  2. 结点带权路径长度(WPL):通过的边数*该结点上的权值

树的带权路径长度:全部叶结点的带权路径长度之和

  1. 哈夫曼树的特色:

① 每一个初始结点最终都成叶子结点,且权值越小的结点到根节点的路径长度越大

② 构造过程当中工新建了n-1个结点,所以总结点数为2n-1

③ 哈夫曼中不存在度为1的结点

④ 符合②③的树称为严格的、正则的二叉树

  1. 哈夫曼编码:

① 固定长编码:对每一个字符用相等的长度的二进制表示(即000,001,010...)

② 可变长度编码:容许对不一样字符用不等长的二进制位表示

③ 前缀编码:没有一个编码是另外一个编码的前缀

④ 编码构造树的过程当中:

(1) 0,1到底表示左子树仍是右子树没有明确规定,通常为左为0,右为1

(2) 左右孩子结点的顺序是任意的,故构造出的哈夫曼树并不惟一

(3) 所构造出的不一样哈夫曼树WPL一定是相同且最优的

(五)树堆

1. 堆的概念:

① 堆就是用数组实现的二叉树,因此它没有使用父指针或者子指针

② 最大堆:父节点的值比每个子节点的值都要大

③ 最小堆:父节点的值比每个子节点的值都要小

④ 堆和二叉搜索树的主要差异:

(1) 节点的顺序。在二叉搜索树中,左子节点必须比父节点小,右子节点必须必比父节点大可是在堆中并不是如此。在最大堆中两个子节点都必须比父节点小,而在最小堆中,它们都必须比父节点大

(2) 内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数据来存储数组,且不使用指针

(3) 平衡。二叉搜索树必须是“平衡”的状况下,其大部分操做的复杂度才能达到O(log n)。你能够按任意顺序位置插入/删除数据,或者使用 AVL 树或者红黑树,可是在堆中实际上不须要整棵树都是有序的。咱们只须要知足堆属性便可,因此在堆中平衡不是问题。由于堆中数据的组织方式能够保证O(log n) 的性能

(4) 搜索。在二叉树中搜索会很快,可是在堆中搜索会很慢。在堆中搜索不是第一优先级,由于使用堆的目的是将最大(或者最小)的节点放在最前面,从而快速的进行相关插入、删除操做。

⑤ insert() 插入一个新的元素,和经过 remove()移除最大或者最小值。二者的时间复杂度都是O(log n)

  1. 树堆的概念:

① 树堆是一种随机的二叉搜索树(知足二叉搜索树的所有性质),可是和二叉搜索树有相同的性质

② 树堆的结构不禁元素的添加顺序决定,而是随机的

③ 添加新节点时,给这个节点附加优先级(priority)。这种优先结构与元素大小关系和输入顺序无关,值经过随机数肯定。

  1. 树堆的条件:

① 二叉搜索树的条件:对全部节点而言,左侧子树的节点元素值小于根节点元素值,右侧子树的节点元素值大于根节点

② 堆的条件:全部节点的优先级都大于等于自身子节点的优先级

  1. 树堆(也称随机二叉搜索树)的思想:对每个关键字加上一个随机生成的优先级(例如快排∶快排最坏状况下是O(n^2),但若是在快排以前打乱下可以使快排的思想接近0 ( nlog2_n)),当二叉搜索树是有序的状况下进行构造会使二叉搜索树退化成一个链,但若是给一个随机优先级(权值)以树堆的方式进行插入则会是一颗随机插入的二叉搜索树,在以前若插入一个结点假设数高为h则插入最坏状况下=插入+旋转=20 (h),但以树堆形式随机插入的话=0 (h)+O(log2_h),故以树堆形式的构造会有效下降在有序状况下进行插入时的时间复杂度

  2. 若是插入顺序随机,则一棵BST的深度是接近O(log_2n)(若真的很是随机可能就是一颗平衡二叉树了)

  3. 树堆的构造:

  4. 树堆的旋转操做和平衡二叉树类似也是为了保护小根堆/大根堆性质,如如下右旋保护小根堆性质:

  1. 树堆的操做代码:https://www.cnblogs.com/maomao9173/p/10275153.html

https://blog.csdn.net/sdzbyzh/article/details/121446109

计算公式(一些公式记清是向上取整仍是向下取整
二叉树
n个结点有n-1条边 n_0=n_2+1(记清楚,总记反!)
高度为h的树根到每一个结点的路径长度的最大值应是h-1 第k层上至多有2^(k-1)个结点(k>=1)
树中结点数等于全部结点的度数(分支数)之和加1 高度为h的二叉树至多有2^h-1个结点(h>1)
度为m的树中第i层上至多有m^i-1个结点(i>=1) 彻底二叉树:① 叶子结点个数=n/2② 结点i的双亲编号:向下取整(i/2)③ 左孩子:2i;右孩子:2i+1④ 结点i所在层次(深度):向下取整(log_2i)+1⑤ 具备n个结点的彻底二叉树的高度为:向上取整(log_2(n+1))或向下取整(log_2n)+1⑥ 高度为h最少有2^(h-1)个结点⑦ n_0+n_2必定为奇数
高度为h的m叉树至多有(m^h-1)/(m-1)个结点至少有h个结点 含有n个结点的二叉链表中有2n个指针域,含有n+1个空链域
高度为h度为m的树至少有h+m-1个结点 对于先序序列为a1...an的不一样二叉树个数是=不一样元素出栈序列个数=1/(n+1) *Σn,2n
具备n个结点的m叉树的最小高度为:向上取整(log_m(n(m-1)+1))(当m=n-1时,最大深度为n,最小深度为2(若题没规定m是几就这么填))具备n个结点的,度为m的树最小高度为:h=向上取整(log_m(n+1)) 哈夫曼树:① n_0=n_2+1② 深度为h的平衡树最少结点数为n_h=n_(h-1)+n_(h-2)+1③ n个结点的哈夫曼树,最大高度为n,最小高度为log_2n+1④ 文件总长=∑字符出现频度**码长⑤ 平均码长=Σ字符出现几率**码长
常考树节点与度之间的关系:① 总结点树=n_0+n_1+...+n_m② 总分支数=1n_1+2n_2+...+m*n_m③ 总结点数=总分支数+1 树堆:① 若是一个堆有 n 个节点,那么它的高度是 h = 向下取整(log2(n))② 整个堆中的节点数目为: 2^(h+1) - 1③ 叶节点老是位于数组的 floor(n/2) 和 n-1 之间
指针域计算:m叉树的多重链表中每一个结点有m个指针域,n个结点共有nm个指针域,非空指针域的个数(即分支的个数)共n-1个,因此空指针域有nm-(n-1)=n(m-1)+1