数据结构——树

每个宝宝的头上都只有一根天线?

树的高度：4(默认从1开始算)

D节点的度：3

这棵树的度：3?

3棵树组成一个森林

相互转换是重点

树的度：最大的那个节点的度为3

m叉树：每个节点最多有m个孩子 0 1 2 3 ...m

比如二叉树：

完全二叉树：只有叶子节点的右边能缺少，其余和满二叉树一模一样?

最多只有一个度为1的节点

4也重要

你想插入68其实很简单，只要从根开始对比关键字，大了就往右走，小了就往左走

希望你长胖而不是长高，这样对比关键词的次数就会减少，别走那么深吗，受不了啊

任何一个节点的左右子树的高度之差不超过1

顺序存储只适合存储完全二叉树?

左孩子2i 右孩子2i+1

i的父节点：i/2向下取整?

i所在层次：[log2n] +1也是向下取整

普通二叉树

判断左孩子只能通过isempty字段

也都要按照满二叉树的标准来分配存储空间

因此引出了二叉树的链式存储：

一共有n+1个空链域，可用于构造线索二叉树?

这里重点解释一下为什么是n+1个空炼狱：在一棵二叉树当中，除了根节点之外，每个天线宝宝头上都只有一根天线(每个天线消耗一个指针)，一共使用了n-1个指针，所以还剩2n-(n-1)=n+1个空炼狱

二叉树的链式存储

大多情况其实是使用的链式存储，插入根节点的时候只要初始化根即可，后面加入新的节点就再malloc即可

子节点好找，但是父节点镇TM难找啊！！！?

方便找父节点：三叉链表

?

多练几遍呗?

代码实现二叉树的先序中序后序遍历

visit访问的代码放在前面就是先序遍历，放到中间就是中序遍历，放到后面就是后序遍历

空间复杂度：O(h)? ? ? ? 与高度有关

先序第一次碰到的就是喽，其余的使用前面的方法吧

求树的高度

分别递归遍历左右子树的高度取其最大值为树高

每访问一个节点就把它的左右孩子依次入队，同时根节点出队

使用链队列? ? ? ? 代码实现：

最终结果：注意验证！

?

首先由先序/后续/层次遍历确定根节点的位置，然后根据中序遍历序列确定左右

结果和上面的一样的嘿嘿

普通二叉树的缺陷：只能从根开始遍历，我从第二个元素开始都不刑😂😂?

找到中序遍历序列的前驱和后继节点讲实话蛮麻烦的

以下是访问前驱后继的步骤：在visit当中添加操作，一般要从根节点来从头进行中序遍历等等

中序线索二叉树：

术语：二叉链表?

?

建立线索二叉树的目的就是为了方便地找它的前驱和后继：

最左下角的这个节点就是p的后继节点

只有中序线索二叉树才能同时找到前驱和后继?

普通的树应该设计什么样的数据结构来存储它呢？?

?使用二叉链表来存储树可以方便地进行二叉树和树之间的转换

只不过它的指针是*firstchild和*nextsibling，即左孩子是第一个孩子，右孩子是兄弟

?

树和二叉树的相互转换：

?

森林和二叉树的相互转换?

?

哈夫曼树

方法二：

?思考：有没有更好的编码方案呢？

哈夫曼编码可以用于数据的压缩

我一路向北，判断是不是同一个爹地

并查集就两个操作一个是查一个是并

使用双亲表示法来实现并查集那是相当滴容易啊，只要修改指向就🆗辽

使用一个数组就可以表示他们之间的集合关系?

集合初始化代码：

并和查的代码实现：

注意：这里的x指的是下标

合并的时候把小树合并到大树上面，就不会增加树的高度h了

使用根节点的绝对值来表示树的高度(-2 -3 -5 -7 -8这样子)

最终结果：