二叉树和二叉搜索树

---

ps：整个文章所涉及的源代码我都发布在我的Github主页上，大家可以自行下载，如果对您有一丢丢的帮助的话，记得在我的github项目上点上【star】哟，当然不要忘了在本篇文章下方【点赞】啦，你们的支持将是我最大的动力！

（利他之心是每个优秀开发者的传统美德！——@惜墨的少年）

---

树的相关术语

一个树结构包含一系列存在父子关系的节点。除了顶部的第一个节点，每个节点都有一个父节点以及零个或多个子节点。树顶部的节点叫做根节点，它没有父节点。树中每个元素叫做节点，节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点。没有子元素的节点称为外部节点即叶子节点。

有关树的另外一个术语是子树。子树由节点和它的后代构成。节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。树的高度取决于所有节点深度的最大值。一棵树也可以分解成层级。根节点在第0层，它的子节点在第1层，以此类推。

二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。二叉搜索树（BST）是二叉树的一种，但是只允许在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的值。下面以二叉搜索树为例。

创建 Node 类

Node 类

创建 BinarySearchTree 类

BinarySearchTree 类
insert() insertNode()

中序遍历

中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从小到大的顺序访问所有节点。中序遍历的一种应用是对树进行排序操作。

中序遍历逻辑

先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

先序遍历逻辑

后序遍历

后序遍历是先访问节点的后代节点，再访问节点本身。后续遍历的一种应用是计算一个目录和它的子目录中所有文件所占空间大小。

后序遍历逻辑 打印节点 测试 测试结果

搜索树中的值

（1）最小值

搜索树中最小值

（2）最大值

搜索树中最大值

（3）搜索特定的值

搜索树中特定的值 测试搜索树中值 测试结果

移除一个节点

（1）移除一个叶子结点

（2）移除有一个左或右子节点的节点

（3）移除有两个子节点的节点

remove() removeNode() 查找节点
移除节点测试结果