树、二叉树、二分搜索树的解读

亦凉 2022-05-04 10:58 231阅读 0赞

## 一、导语 ##

## 二、树及二叉树 ##

### 1.树结构图示 ###

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

### 2.树的一些基本概念 ###

> 1、结点：树中的数据元素都称之为结点  
> 2、根：最上面的结点称之为根，一颗树只有一个根且由根发展而来，从另外一个角度来说，每个结点都可以认为是其子树的根  
> 3、父亲：结点的上层结点  
> 4、兄弟：具有相同父亲的结点称为兄弟  
> 5、结点的度：结点所拥有的子树的个数称之为结点的度  
> 6、树叶：度为0的结点，也叫作终端结点  
> 7、分支结点：度不为0的结点，也叫作非终端结点或内部结点  
> 8、结点的层次：从根节点到树中某结点所经路径上的分支树称为该结点的层次，根节点的层次规定为1，其余结点的层次等于其父亲结点的层次+1  
> 9、树的深度：树中结点的最大层次数

### 3.二叉树 ###

![在这里插入图片描述][70 1]  
概念：**其每一个结点都不能多余两个子节点。**  
二叉树的一个性质是一颗**平均二叉树的深度要比及结点个数小**得多，这个性质很重要，尤其对于特殊类型的二叉树即二叉查找树而言，其深度的平均值是O(logN)，这将大大降低查找时的时间复杂度。  
当然，二叉树在运用得不好的情况下的情况下是有严重的问题的，即：  
![在这里插入图片描述][70 2]  
退化成一个类似于链表的结构。这种树被称为**不平衡的二叉树**，当然也有平衡的二叉树：如后面要介绍的AVL、红黑树等。

## 三、二分搜索树 ##

需要以下 条件：

*  **二分搜索树是二叉树**
 *  **二分搜索树每个结点的值：大于其左子树的所有结点的值；小于其右子树的所有结点的值**
 *  **其每一个子树也是也是一个二分搜索树。**  
    如下 ：  
    ![在这里插入图片描述][70 3]  
    得出二分搜索树的性质：
 *  **存储的节点的必须有可比较性。**

### 四、其他（后续补充） ###

*  AVL树（后续补充）
 *  红黑树（后续补充）  
    参考：[http://www.cnblogs.com/xrq730/p/5187032.html][http_www.cnblogs.com_xrq730_p_5187032.html]  
    《算法导论》相关内容

[70]: /images/20220504/82c85eb7a5af447bb804e4dd86700a05.png
[70 1]: /images/20220504/662c5725659843ebb809e37ae256a59c.png
[70 2]: /images/20220504/6472b2c8f20e499d9d1062efeb043c87.png
[70 3]: /images/20220504/324105f4543445368962af49cbfb191e.png
[http_www.cnblogs.com_xrq730_p_5187032.html]: http://www.cnblogs.com/xrq730/p/5187032.html