树的基本概念

深碍√TFBOYSˉ_ 2023-07-10 15:41 29阅读 0赞

## 二叉树的基本概念 ##

**阶数**  
阶数是一个节点的子节点数目的最大值。对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。

**度数**  
树中每个节点子树的个数，就称为该节点的度。

## 二叉树的遍历方式 ##

1.  前序：先遍历根节点，再遍历左子树，再遍历右子树
2.  中序：先遍历左子树，再遍历根节点，再遍历右子树
3.  后续：先遍历左子树，再遍历右子树，再遍历根节点

*ps：顺序是针对根节点而言的*

**根据二叉树遍历顺序，推算二叉树结构**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70]  
前序的顺序：ABCDEF  
中序的顺序：CBDAEF  
后序的顺序：CDBFEA

还原二叉树必须要一个中序遍历顺序，因为需要中序遍历可以将左右子树分开。

## 二叉树的几种类型 ##

## AVL树的定义 ##

1.  本身首先是一棵二叉搜索树。
2.  带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

## 红黑树的定义 ##

1.  节点是红色或黑色。
2.  根节点是黑色。
3.  所有叶子都是黑色。
4.  每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5.  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 1]

## B树的定义 ##

1.  根节点至少有两个孩子
2.  每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
3.  除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4.  所有的叶子节点都在同一层。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201231163910463.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201231164755771.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201231165157331.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70