深入浅出数据结构（树篇）

ゞ浴缸里的玫瑰 2023-07-11 11:12 123阅读 0赞

### 文章目录 ###

*   *   *   *  前言：
             *  1. 树
             *   *  1.1 名词解释
                 *  1.2 树的存储结构
                 *  1.3 树的种类
                 *  二叉树
                 *  二叉树的性质
                 *  存储方式
                 *  二叉树的遍历
                 *  树、森林与二叉树的转换
                 *  BST二叉排序树（二叉搜索树）
                 *  AVL平衡二叉搜索树
                 *  RBT 红黑树
                 *  线索二叉树
                 *  哈弗曼树（最优二叉树）
                 *  B-,B+,B\*树

#### 前言： ####

此篇为数据结构相关内容连载第二篇，为博主近期总结所得，如有错误，请指出！我及时更正！

#### 1. 树 ####

##### 1.1 名词解释 #####

树这个数据结构用到了递归的概念：树的子树还是树；  
度：节点的子树个数；  
树的度：树中任意节点的度的最大值；  
兄弟：两节点的parent相同；  
层：根在第一层，以此类推；  
高度：叶子节点的高度为1，根节点高度最高；  
有序树：树中各个节点是有次序的；  
森林：多个树组成；

##### 1.2 树的存储结构 #####

*  双亲表示法——在每个结点的结构中，附设一个字段记录其双亲结点在数组中的位置
 *  孩子表示法——每个结点有多个指针域，其中每个指针都指向一颗子树的根结点
 *  孩子兄弟表示法——任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该节点的第一个孩子和此节点的右兄弟。  
    注：第一种方法与第二种方法合并组合成双亲孩子表示法。  
    　　第三种方法最大的好处就是把一颗复杂的树变成一颗二叉树。可以充分利用二叉树的特性与算法来处理这颗树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg_size_16_color_FFFFFF_t_70_pic_center]

##### 1.3 树的种类 #####

*  无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;
 *  有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；
 *  二叉树：每个节点最多含有两个子树的树称为二叉树；
 *  完全二叉树
 *  满二叉树
 *  斜树
 *  平衡二叉树
 *  霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

##### 二叉树 #####

1.特点：每个结点最多只有两个子结点，可以没有或者只有一个。  
　　左子树和右子树是有顺序的，次序不能任意颠倒。  
2.分类：  
斜树：所有节点都只有左子树的二叉树叫做左斜树，所有节点都只有右节点的二叉树叫做右斜树，这两者统称为斜树。  
![aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnLzBfMTMzMDMzOTY3MHVsbkMuZ2lm_pic_center][]  
满二叉树：除了最下面一层的叶子结点外，其他结点都有两个子结点；  
完全二叉树：除了最下面一层的叶子结点外，其他各层结点数达到最大个数，而且最后一层叶子结点按照从左到右的顺序连续存在，只缺最后一层若干结点；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg_size_16_color_FFFFFF_t_70_pic_center 1]

##### 二叉树的性质 #####

1.  第i层至多有2^i -1个节点；
2.  深度为k的树最多有2^k -1个节点；
3.  任意二叉树，度为0的节点数=度为2的节点数+1；
4.  如果i为父亲的编号，则孩子的编号为2i和2i+1;
5.  如果孩子的编号为k,则父亲的编号为floor(k/2);

##### 存储方式 #####

顺序存储：只适用于完全二叉树；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg_size_16_color_FFFFFF_t_70_pic_center 2]  
二叉树的顺序存储结构用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要体现出结点之间的逻辑关系。  
就是从根结点开始一层层地按顺序存储在数组里，但是只适用于完全二叉树，因为非完全二叉树的话，可能会浪费大量的存储空间。  
链式存储：最通用的存储方法；  
![aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnLzBfMTMzMDMzOTc1MFRTbFYuZ2lm_pic_center_pic_center][]  
因为二叉树最多有两个孩子，所以二叉链表拥有一个数据域和两个指针域。  
如果有需要还可以再增加一个指向其双亲的指针域，那就称为三叉链表。

##### 二叉树的遍历 #####

*  先序：先访问**根**结点，后是左子树，到右子树；
 *  中序：先左子树，后**根**结点，最后是右子树；
 *  后序：先左子树，后右子树，最后**根**结点；
 *  层序：从上到下，从左到右依次遍历每一层中的每一个节点。

例如：求下面树的三种遍历  
![在这里插入图片描述][20200305104400784.png_pic_center]  
前序遍历：abdefgc  
中序遍历：debgfac  
后序遍历：edgfbca

\[范例1：二叉树遍历\]  
![format_png_pic_center][]  
参见范例代码BinaryTree1 \{也可以用栈来记录并输出\}

\[范例2：完全二叉树\]  
![format_png_pic_center 1][]  
参见范例代码BinTreeTraverse2 \{也可以用栈来记录并输出\}

\[对于1中的普通二叉树，可以变成完全二叉树处理，比如缺少的位置补充0，打印的时候不输出0\]

##### 树、森林与二叉树的转换 #####

注：面对复杂的树与森林都可以转换成简单二叉树来进行处理，由于二叉树至多只有两个节点，变化较少，很多性质与算法被研究出来，使用方便。

##### BST二叉排序树（二叉搜索树） #####

特点：

1.  所有非叶子结点至多拥有两个儿子（Left和Right）；
2.  所有结点存储一个关键字；
3.  非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
4.  其他的左右子树也分别为二叉查找树
5.  二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。  
    ![format_png_pic_center 2][]

如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树  
的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变BST树结构  
（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg_size_16_color_FFFFFF_t_70_pic_center 3]  
但BST树在经过多次插入与删除后，有可能导致不同的结构：  
右边也是一个BST树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用BST树还要考虑尽可能让BST树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；  
![format_png_pic_center 3][]

##### AVL平衡二叉搜索树 #####

![format_png_pic_center 4][]  
含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树（图b），具有以下性质：

1.  要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1；
2.  其左右子树也都是平衡二叉树；
3.  二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。  
    【平衡因子BF=左子树深度－右子树深度】

##### RBT 红黑树 #####

AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；  
红黑是弱平衡的，用非严格的平衡来换取增删节点时候旋转次数的降低；  
所以简单说，搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应该选择RB树。  
![在这里插入图片描述][20200305104607269.png_pic_center]  
　红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：

1.  根节点只能是黑色；
2.  红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色；
3.  其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间；
4.  在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。

##### 线索二叉树 #####

二叉链表有很多浪费的空指针可以利用，线索二叉树给二叉树的查找与遍历带来了高效率。  
　　指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。  
　　对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。  
　　二叉链表充分利用了空指针域的空间，又保证了创建过程时的一次遍历就可以终生享用的前驱后继的信息。因此，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱后继，那么采用线索二叉树的存储结构是非常不错的选择

##### 哈弗曼树（最优二叉树） #####

从树中的一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。  
树的路径长度就是从树的根结点到每一结点长度之和。  
带权路径长度最小的二叉树称为哈夫曼树。【每个节点带权值】

##### B-,B+,B\*树 #####

请移步我之前的博客，深入浅出数据库索引，有相应介绍

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200305104236492.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg==,size_16,color_FFFFFF,t_70#pic_center
[aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnLzBfMTMzMDMzOTY3MHVsbkMuZ2lm_pic_center]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnLzBfMTMzMDMzOTY3MHVsbkMuZ2lm#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200305104302233.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200305104324348.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg==,size_16,color_FFFFFF,t_70#pic_center
[aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnLzBfMTMzMDMzOTc1MFRTbFYuZ2lm_pic_center_pic_center]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnLzBfMTMzMDMzOTc1MFRTbFYuZ2lm#pic_center#pic_center
[20200305104400784.png_pic_center]: https://img-blog.csdnimg.cn/20200305104400784.png#pic_center
[format_png_pic_center]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnL3N0cnVjdHVyZTEuanBn?x-oss-process=image/format,png#pic_center
[format_png_pic_center 1]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnL3N0cnVjdHVyZTIuanBn?x-oss-process=image/format,png#pic_center
[format_png_pic_center 2]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnLzIwMTExMTIyMTUwOTI3NTQuanBn?x-oss-process=image/format,png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200305104529644.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FBQWh4eg==,size_16,color_FFFFFF,t_70#pic_center
[format_png_pic_center 3]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnLzMxLmpwZw?x-oss-process=image/format,png#pic_center
[format_png_pic_center 4]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZzEuYmltb3d1LmNvbS9pbWFnZXMvamF2YXdlYi9zampnLzIwMTExMTIyMTUxMTAxNTcuanBn?x-oss-process=image/format,png#pic_center
[20200305104607269.png_pic_center]: https://img-blog.csdnimg.cn/20200305104607269.png#pic_center