彻底搞懂二叉搜索树

学习的大多是线性表相关的内容，把指针搞懂后其实也没有什么难度，规则相对是简单的，后面会讲解一些比较常见的数据结构，用多图的方式让大家更容易吸收。

在数据结构与算法中，树是一个比较大的家族，家族中有很多厉害的成员，这些成员有二叉树和多叉树(例如B+树等)，而二叉树的大家族中，二叉搜索树(又称二叉排序树)是最最基础的，在这基础上才能继续拓展学习AVL(二叉平衡树)、红黑树等知识。

对于二叉排序树而言，本章重点关注其实现方式以及插入、删除步骤流程，我们会手写一个二叉排序树，二叉树遍历部分的内容比较多会单独详细讲解。

什么是树

树是一种数据结构，它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝递归的，将树的任何一个节点以及节点下的节点都能组合成一个新的树，所以树的很多问题都是使用递归去完成。

根节点： 最上面的那个节点(root)，根节点没有父节点，只有子节点(0个或多个都可以)

层数： 一般认为根节点是第1层(有的也说第0层)，而树的高度就是层数最高(上图层数开始为1)节点的层数

节点关系:

• 父节点：连接该节点的上一层节点,
• 孩子节点: 和父节点对应，上下关系。而祖先节点是父节点的父节点(或者祖先)节点。
• 兄弟节点：拥有同一个父节点的节点们!

节点的度: 就是节点拥有孩子节点的个数(是直接连接的孩子不是子孙).

树的度: 就是所有节点中最大 (节点的度)。同时，如果度大于0的节点是分支节点,度等于0的节点是叶子节点(没有子孙)。

（编辑：牡丹江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!