数据结构之二叉树

╰+攻爆jí腚メ 2022-12-26 09:18 341阅读 0赞

### 二叉树 ###

*  二叉树概念
 *   *  基本形态
     *  相关术语
     *  特殊类型
     *  性质
 *  二叉树的应用
 *   *  霍夫曼编码
     *  用户界面
     *  数据库系统
     *  表达式处理
     *  人工智能
     *  优先级队列
 *  二叉树的数据结构
 *  树的周游算法
 *   *  先序遍历
     *  中序遍历
     *  后序遍历
     *  层级遍历
 *  树的平衡
 *  问与答
 *   *  1，同双向链表类似，一些书除了维护从父节点指向子节点的正常指针之外，也维护了从子节点指回它们父节点的指针，还有一些树在兄弟节点之间也维护相互关联的指针，为什么？
     *  2，在二叉搜索树中，如何找到最小的节点？在最坏情况下，非平衡和平衡二叉树中的操作时间复杂度是多少？如何在二叉搜索树中找到最大的节点？时间复杂度是多少？
     *  3，何时应该选择分支因子相对较大的树而不是二叉树（二叉树的分支因子为2）？
     *  4，如何在二叉搜索树中找到某个节点的后继节点？该操作的时间复杂度是多少？
 *  其他树
 *   *  K叉树
     *  红黑树
     *  Trie树
     *  B树，B+树和B\*树

# 二叉树概念 #

树的一个节点拥有多少个子节点取决于树的类型，这个量值称为树的分支因子，它决定了当插入节点是，树的分支扩展速度。二叉树的分支因子为2。二叉树是一种将节点按照层次结构组织起来的数据结构，每个节点最多只有两个与它直接相关联的子节点。

## 基本形态 ##

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：  
1、空二叉树——如图（a）；  
2、只有一个根结点的二叉树——如图（b）；  
3、只有左子树——如图（c）；  
4、只有右子树——如图（d）；  
5、完全二叉树——如图（e）。  
![在这里插入图片描述][20201204105803200.gif_pic_center]

## 相关术语 ##

①结点：包含一个数据元素及若干指向子树分支的信息 。  
②**结点的度**：一个结点拥有子树的数目称为结点的度 。  
③叶子结点：也称为终端结点，没有子树的结点或者度为零的结点 。  
④分支结点：也称为非终端结点，度不为零的结点称为非终端结点。  
⑤**树的度**：**树中所有结点的度的最大值**。  
⑥结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。  
⑦**树的深度**：也称为树的高度，树中所有结点的层次最大值称为树的深度 。  
⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树 。  
⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。  
⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成 。

## 特殊类型 ##

1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。  
2、完全二叉树：**深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。**  
完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center]

## 性质 ##

(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；

(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，  
则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为int（log2n）+1

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：  
若I为结点编号则 如果I<>1，则其父结点的编号为I/2；  
如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；  
如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。

(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(n,2\*n)/(n+1)。

# 二叉树的应用 #

## 霍夫曼编码 ##

这是一种数据压缩方法，该方法用一棵霍夫曼树来压缩一组数据。霍夫曼树是一颗二叉树，它能够保证按照最优的方式将编码赋给数据中的符号。出现频率高的符号将被赋予较短的编码，而出现频率低的符号将被赋予较长的编码。

## 用户界面 ##

在用户图形界面中，窗口按照层次结构组织成一棵树，除了顶部窗口外，每个窗口都拥有一个父窗口，而每个窗口可能拥有多个子窗口。在文件系统中，目录和目录之间也有相同的组织方式。

## 数据库系统 ##

特别是针对那些同事需要满足高效率的顺序和随机访问，而且还要经常执行插入和删除操作的系统。B树拥有很大的分支因子，大致可归类为平衡搜索树。

## 表达式处理 ##

这个任务是编译器和手持式计算器经常做的，一种处理算数表达式的自然方法是通过表达式树，这是一种按照表达式的操作数和操作符按照层次结构组织起来的一棵二叉树。

## 人工智能 ##

AI方面的许多问题都是采用决策树来解决。决策树的节点代表问题的状态，每个节点都是一个决策点，必须在当前决策点做出选择以使得问题继续求解下去。

## 优先级队列 ##

优先级队列是一种数据结构，它采用一棵二叉树来记录集合中的哪个元素将拥有下一个最高的优先级。与将一组数据全部排序相比，优先级队列提供了更好的解决方案。

# 二叉树的数据结构 #

二叉树中的每个节点都包含三个部分：一个数据成员和两个左右指针。如果某个节点没有相对应左子节点或右子节点，就将相应的指针设置为NULL。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 1]

# 树的周游算法 #

周游一棵二叉树意味着按照某种顺序依次访问树的每一个节点。一般有四种周游算法：先序遍历、中序遍历、后序遍历以及层级遍历。

## 先序遍历 ##

[先序遍历][Link 1]  
遍历顺序：根->左->右，先序遍历是按照**深度优先**的方式遍历节点的。

## 中序遍历 ##

[中序遍历][Link 2]  
遍历顺序：左->根->右，**对于二叉搜索树，中序遍历得到的节点数组是升序的**。

## 后序遍历 ##

[后序遍历][Link 1]  
遍历顺序：左->右->根。

## 层级遍历 ##

层级遍历首先访问树的根，然后依次向下层处理，按照从左到右的顺序访问每层的节点。层级遍历采用了**广度优先**的策略。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 2]

# 树的平衡 #

树的平衡是指对于给定数量的节点，保证树的高度尽可能短的过程。这意味着在节点加入下一层之前必须保证本层的节点满额。正式的说法是：如果满足树的所有叶子节点都在同一层上，或者所有叶子节点都在最后两层上，且倒数第二层是满的，则这棵树是平衡的。  
如果一个平衡树最后一层的所有叶子节点都在最靠左边的位置，则称这棵树是左平衡的。左平衡树可以帮助实现堆和优先级队列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 3]

# 问与答 #

## 1，同双向链表类似，一些书除了维护从父节点指向子节点的正常指针之外，也维护了从子节点指回它们父节点的指针，还有一些树在兄弟节点之间也维护相互关联的指针，为什么？ ##

一般来说，维护附加的指针为遍历树时提供了更加灵活的方式。比如维护父节点与子节点之间的指针，能使我们自上而下或者自下而上遍历这棵树。维护兄弟之间的指针可以使得不必先访问父节点就能方便地遍历子节点。连接兄弟节点带来的好处在B+树中可以找到，这是一种使用指针将叶子节点连接在一起的平衡搜索树。通过链接叶子节点，能够有效地在书的最底端形成一个链表。这提供了一种按照顺序查找特定的节点，并检索要么在其之前或在其之后节点的高效方法。数据库系统采用这种方法来同时支持高效的随机和顺序访问。当然缺点就是多了一些保存指针的开销，而且在插入和移除子节点时，管理兄弟节点的指针比较复杂。

## 2，在二叉搜索树中，如何找到最小的节点？在最坏情况下，非平衡和平衡二叉树中的操作时间复杂度是多少？如何在二叉搜索树中找到最大的节点？时间复杂度是多少？ ##

二叉搜索树中的最小节点是最左边的叶子节点。要定位到该节点，需要从根节点开始通过左指针逐层下降，直到到达该分支的边缘。在非平衡二叉搜索树中，最坏的情况需要O(n)的时间，n为节点个数。平衡二叉树下，复杂度为O(lg n)。查找最大的节点与查找最小的节点类似，复杂度也相同，只不过最大的节点为最右端的叶子节点。

## 3，何时应该选择分支因子相对较大的树而不是二叉树（二叉树的分支因子为2）？ ##

对于给定的节点个数，分支因子大能够保持这个数的高度较低，也就使树能够保持相对的平衡性。因此，在对于书的高度尤其敏感的应用中，采用分支因子较大的树是更好的选择。

## 4，如何在二叉搜索树中找到某个节点的后继节点？该操作的时间复杂度是多少？ ##

在一个二叉搜索树中，某节点x的后继节点是指x之后的下一个最大节点。例如一棵二叉树中包含键值3，6，9，11，22，66，于是11的后继为22.要在二叉搜索树中确定x的后继节点，首先要定位到x，然后移动到x的右子节点，从这个节点开始，逐层访问左节点，其最左端的叶子节点就是x的后继节点。定位到x以及x的后继节点的时间复杂度都是O(lg n)。

# 其他树 #

## K叉树 ##

K叉树的分支因子为k，节点的分支因子大于2对某些特定的场景的建模很有帮助。比如在图形窗口系统中父窗口与其子窗口之间的1对n的关系，或者文件系统中的目录结构。

## 红黑树 ##

红黑树是每个节点都带有颜色属性的自平衡二叉树，节点颜色要么为红色要么为黑色。通过在分支中规定节点着色的规则，红黑树能够确保每个分支都不会长于其它分支的2倍。红黑树的最长运行时间为T(n)=2klgn，这里n是树中节点的个数，k为某个常量。而完全平衡二叉树的搜索时间为T(n)=klgn。

## Trie树 ##

Trie搜索树主要用来查找变长字符串的组合。

## B树，B+树和B\*树 ##

数据库系统通常使用B树来提高访问辅助存储设备上的数据的性能。一般来说，通过优化手段使得节点大小和辅助存储设备的块大小保持一致。所有类型的B树都是平衡的，且一般都有较大的分支因子。这使得书的高度较小，于是为了得到某条记录必须遍历的层级减少了，从而减少了IO操作带来的开销。

[20201204105803200.gif_pic_center]: /images/20221120/0db078e6dd1c4723bf7cb96d78fa0740.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/205738bf04bb4938a8f9a8f0f66a7e5f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/be79ecaab41f4fa3ace12f07f59662c1.png
[Link 1]: https://blog.csdn.net/luolaihua2018/article/details/109311612
[Link 2]: https://blog.csdn.net/luolaihua2018/article/details/109023182
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/3bfe8107746743a383f45b2705535146.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/ccc9407dce024e5183d2b80b0ef062eb.png