该账户是华为云开发者社区的官方运营账户，提供全面深入的云计算前景分析、丰富的技术干货、流程样本，共享华为云前端信息动态
本文来自华为云社区《【云驻共创】想了解二叉树，看这篇文章就够了》、作者： liuzhen007。
前言
日常生活中，书的目录、职场的组织结构等很多东西都可以用树来记述。 树是计算机中非常重要的数据结构，树的存储方式可以提高数据的存储、读取效率。
一、树的基本定义
日常生活中，很多东西都可以用树来描述。 树是计算机中非常重要的数据结构。 树的保存方式可以提高数据的保存、读取效率，例如利用二叉排序树，可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。
其实，树的种类有很多种。 例如普通二叉树、完全二叉树、满二叉树、线索二叉树、哈夫曼树、二叉排序树、平衡二叉树、AVL平衡二叉树、红黑树、b树、b树、堆等。 今天介绍的主要内容是二叉树的基本知识和一些基础类型的二叉树。
二、二叉树的相关术语
正式开始讲课之前，首先介绍二叉树的相关专业名词和术语。 例如，节点、节点程度、叶节点、分支节点、节点层次、树的程度、树的深度等。 理解这些基础专业名词和术语对理解二叉树的特性有非常重要的帮助。1 )节点)包含一个数据要素和几个子树分支的信息。
2 )节点的度)一个节点拥有子树的数据成为节点的度。
3 )叶节点)也称为终端节点，是无子节点或度为零的节点。
4 )分支节点)也称为非终端节点，度非零的节点成为非终端节点。
5 )节点的层次)如从根节点到根节点的层次为1，根的直接后继层次为2那样。
6 )树的度)树中所有节点的度的最大值。
7 )树的深度)树中节点的最大级别。
1. 树的特点
树作为特殊的数据结构，有非常多的特性。 例如：1 )每个节点有多个或零个子节点
2 )没有父节点成为根节点，没有子节点成为叶节点
3 )根以外的各节点只有一个父节点
4 )各节点及其子孙节点从整体上可以看作一棵树，以当前节点为根的子树
2. 二叉树的基本定义
1(二叉树是度为2以下的树，每个节点最多有两个子节点2 )二叉树的节点被分为左节点和右节点
3. 满二叉树
1(二叉树各层的节点度达到最大值时，这个二叉树就会充满二叉树2 )一棵深度为n的二叉树有2^n-1个节点
4. 完全二叉树
叶节点只出现在最下层和次下层，最下层的叶节点在左侧连续，倒数第二个叶节点在右侧连续，被称为完全二叉树。
三、二叉树的创建
接下来，用代码编写二叉树。 语言以Java为例。 其中，节点类定义如下：
二叉搜索树类定义如下。
ttps://p26.toutiaoimg.com/origin/pgc-image/e93a25bc169043ab84a9194802a6d19d?from=pc">相关类定义好后，我们来看具体的方法实现，下面分别介绍。
1. size（）方法
size（）方法相对简单，每次添加元素加一，删除元素减一，维护一个公共的变量 num 即可，代码实现如下：
2. put（Key key，Value value）方法
put（Key key，Value value）方法可以利用重载方法 put（Node x，Key key，Value value），因此实现也相对简单，其中第一个参数只需要传根结点即可，代码实现如下：
3. put（Node x，Key key，Value value）方法
put（Node x，Key key，Value value）方法应该是整个类中实现相对较为复杂的，下面进行简单的分析。
第一种情况，当前树中没有任何一个结点，直接将新插入的结点作为根结点。
第二种情况，当前树不为空，则从根结点开始。这种情况有可以细分为三种情况：
1）如果新结点的key小于当前结点的key，则继续查找当前结点的左子结点。
2）如果新结点的key大于当前结点的key，则继续查找当前结点的右子结点。
3）如果新结点的key等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值即可。
具体的代码实现如下：
4. get（Key key）方法
get（Key key）方法和 put（Key key，Value value）方法类似，也可以利用重载方法 get（Node x，Key key）来实现，代码实现如下：
5. get（Node x，Key key）方法
get（Node x，Key key）方法实现查询方法从根结点开始，如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；如果要查找的key大于当前结点的key，则继续找当前结点的右子结点；如果要查找的key等于当前结点的key，则返回当前结点的value。
具体的代码实现如下：
通过上面的代码，我们可以看出 get（）方法和 put（）方法类似，都是通过递归调用实现的。
6. delete（Key key）方法
delete（Key key）方法也是一样的思路，调用后面的重载方法就行了，代码实现如下：
7. delete（Node x，Key key）方法
删除方法的实现思路，以最复杂的情况为例，首先找到被删除的结点，找到被删除结点右子树中的最小结点 minNode，删除右子树中的最小结点，让被删除结点的鲜艳的蜻蜓成为最小结点 minNode 的鲜艳的蜻蜓，让被删除结点右子树成为最小结点minNode的右子树，让被删除结点的父结点指向最小结点 minNode。
具体的代码实现如下：
既然代码已经写完了，接下来通过代码来验证一下，看看我们写得是否正确：
答案输出：
3
hxsddr/p>
2
Nice，太好了，通过上述输出结果已经证明了程序是正确的。
四、查找二叉树中最小和最大的键
比如二叉树中用来记录某个公司员工薪资和员工姓名数据，或者某班级学生们的排名和姓名数据。如何快速找出排名最高和最低的同学数据？
这样的话，该怎么做呢？其实，一般还可以整理出如下四个方法，定义如下：
1. min（）方法
min（）方法和上面提到的 get（）和 put（）方法类似，也可以使用下面的重载方法实现，具体代码如下：
// 找出树中最小的键 public key min() { return min(root).key; }2. min（Node x）方法
min（Node x）方法需要根据传入的结点位置，查找鲜艳的蜻蜓中的最小的结点，如果为空，则直接返回空，具体代码实现如下：
// 找出树中最小键所在的结点 public Node min(Node x) { if (x == null) { return x; } Node minNode = x; while (minNode.left != null) { minNode = minNode.left; } return minNode; }3. max（）方法
max（）方法和上面提到的 min（）方法类似，也可以使用下面的重载方法实现，具体代码如下：
// 找出树中最小的键 public key max() { return max(root).key; }4. max（Node x）方法
max（Node x）方法需要根据传入的结点位置，查找右子树中的最大的结点，如果为空，则直接返回空，具体代码实现如下：
// 找出树中最大键所在的结点 public Node min(Node x) { if (x == null) { return x; } Node maxNode = x; while (maxNode.right != null) { maxNode = maxNode.right; } return maxNode; }五、二叉树的遍历
二叉树的遍历有三种方式，分别是前序遍历、中序遍历、后序遍历。
1. 前序遍历
先访问根结点，再访问鲜艳的蜻蜓，最后访问右子树，比如下图中的二叉树，前序遍历结果如下：
EBADCGFH。
2. 中序遍历
先访问鲜艳的蜻蜓，再访问根结点，最后访问右子树，比如下图中的二叉树，中序遍历结果如下：
ABCDEFGH。
3. 后序遍历
先访问鲜艳的蜻蜓，再访问右子树，最后访问根结点，比如下图中的二叉树，后序遍历结果如下：
ACDBFHGE。
结论
二叉树的不仅在基础的数据结构方面有非常重要的研究意义，在实际应用中也有非常重要的应用场景，兼顾了常规数据结构数组和链表的优点，同时又避免了二者天生的不足。许多实际的问题抽象出来的数据结构往往是二叉树的形式，从而利用二叉树的存储结构和算法特性，因此学习二叉树就非常的必要。希望通过今天本文的介绍能够帮助大家深入理解和掌握二叉树。
点击关注，第一时间了解华为云新鲜技术~华为云博客_大数据博客_AI博客_云计算博客_开发者中心-华为云