摘要： 日常生活中，很多事物都能够用树来形容，例如书的目录、工作单位的组织架构等等。树是计算机中十分重要的一种数据结构，树存储形式能够进步数据的存储、读取效率。
本文分享自华为云社区《【云驻共创】想理解二叉树，看这篇文章就够了》，作者：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 为例，其中结点类定义如下：
二叉查找树类定义如下：
相干类定义好后，咱们来看具体的办法实现，上面别离介绍。
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
李四
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。
论断
二叉树的不仅在根底的数据结构方面有十分重要的钻研意义，在理论利用中也有十分重要的利用场景，兼顾了惯例数据结构数组和链表的长处，同时又防止了二者天生的有余。许多理论的问题形象进去的数据结构往往是二叉树的模式，从而利用二叉树的存储构造和算法个性，因而学习二叉树就十分的必要。心愿通过明天本文的介绍可能帮忙大家深刻了解和把握二叉树。
点击关注，第一工夫理解华为云陈腐技术~