面试问题浓缩总结
小游
2021-03-21

数和二叉树

# 二叉树的遍历

1.先序遍历：根结点 ---> 左子树 ---> 右子树

2.中序遍历：左子树---> 根结点 ---> 右子树

3.后序遍历：左子树 ---> 右子树 ---> 根结点

4.层次遍历：只需按层次遍历即可

img

比如上面这张图，遍历的结果如下所示

先序遍历：1 2 4 5 7 8 3 6

中序遍历：4 2 7 5 8 1 3 6

后序遍历：4 7 8 5 2 6 3 1

层次遍历：1 2 3 4 5 6 7 8

这里我简单解释一下先序遍历。

我们可以看到1是根节点，所以先是1，然后左子树是2，这里我们到2可以看到2是下一课树的根节点，所以左子树是4，这个时候已经不能往下了，所以我们遍历右子树5往下就是左子树7，然后右子树8，到这个时候，我们的1的那个左子树已经遍历完了然后我们向右。后面就不说了

# 二叉树的性质

1.在二叉树的第i层上至多有2^(i-1)个节点

2.深度为k的二叉树至多有2^(k) - 1

3.对于任何一棵二叉树T如果其终端结点数为n0度为2的节点为n2，则n0=n2+1

# 满二叉树

深度为k且含有2^k-1个节点的二叉树，其实就是最后一层可以不满，但是上一层必须摆满。

# B+树，B树，红黑树

# 红黑树

一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是red或black. 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍.它是一种弱平衡二叉树(由于是若平衡,可以推出,相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索,插入,删除操作多的情况下,我们就用红黑树.

性质

  • 每个节点非红即黑.
  • 根节点是黑的。
  • 每个叶节点(叶节点即树尾端NUL指针或NULL节点)都是黑的.
  • 如果一个节点是红的,那么它的两儿子都是黑的.
  • 对于任意节点而言,其到叶子点树NIL指针的每条路径都包含相同数目的黑节点.

应用

  • 广泛用于C++的STL中,map和set都是用红黑树实现的.
  • 著名的linux进程调度Completely Fair Scheduler (opens new window),用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.
  • IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查.
  • ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
  • java中TreeMap的实现.

# 红黑树的左旋和右旋

左旋：以某个节点作为支点(旋转节点)，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，旋转节点的左子节点保持不变。右子节点的左子节点相当于从右子节点上“断开”，重新连接到旋转节点上。

img

右旋：以某个节点作为支点(旋转节点)，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，旋转节点的右子节点保持不变。左子节点的右子节点相当于从左子节点上“断开”，重新连接到旋转节点上。

img

# B+树和B树

更具体的查看算法笔记里面的查找算法

B+树更适合用于文件索引，比如MySQL的innodb就是使用的B+数来进行索引

后面参考这个：https://segmentfault.com/a/1190000020416577

# 线索二叉树

理解线索二叉树 - 简书 (jianshu.com) (opens new window)

遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。这些线性序列中的每一个元素都有且仅有一个前驱结点和后继结点。

但是当我们希望得到二叉树中某一个结点的前驱或者后继结点时，普通的二叉树是无法直接得到的，只能通过遍历一次二叉树得到。每当涉及到求解前驱或者后继就需要将二叉树遍历一次，非常不方便。然后我们的二叉树正常情况会有很多空节点，所以我们可以利用这个节点

但是我们需要判断当前节点是存放的结果还是节点，所以我们在每一个结点都增设两个标志域LTag和RTag，它们只存放0或1的布尔型变量，占用的空间很小。于是结点的结构如图所示。

image-20210228204116857

LTag为0是指向该结点的左孩子，为1时指向该结点的前驱

RTag为0是指向该结点的右孩子，为1时指向该结点的后继

因此，实际的二叉链表图如下所示：

image-20210228204200692

# 树和森林

注意：这个树不是二叉树，二叉树是一种特殊的树，不要理解错误

# 树的三种表示方法

  • 双亲表示法

    image-20210325085109928

  • 孩子表示法

    其实就是先用数组表示所有节点， 然后数组指向的链表就指向所有的孩子（这个树和上图是一样的）

    image-20210325085459488

  • 孩子兄弟表示法

    其实就是一个链表，第一个指向孩子，第二个指向兄弟

    image-20210325085728475

表示效果如下图

image-20210325085742371

# 哈夫曼树

哈夫曼树也被称为最优树，就是指带权路径长度最短的树。

几个概念

  • 路径 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
  • 路径长度 路径上的分支数目称作路径长度
  • 树的路径长度 从树根到每一结点的路径长度之和
  • 权 赋予某个实体的一个量，是对实体的某个或某些属性的数值化描述
  • 结点的带权路径长度 从该结点到树根之间的路径长度与结点上权的乘积
  • 树的带权路径长度 树中所有叶子结点的带权路径长度之和

c 的带权路径长度最小，可以验证c恰好为哈夫曼树。

image-20210228212140623

编辑 (opens new window)
上次更新: 2021/04/23, 21:43:16
串、数组、广义表
图

← 图→

Theme by Vdoing | Copyright © 2021-2021 小游