一、二叉树的概念
二叉树是树类中应用最广泛的一种数据结构，也是非线性数据结构。二叉树的每个节点最多只能包含两个子节点，通常我们称之为左右子树。
二、二叉树的分类以及其特点
比较常见的一些树的名称及其种类如下
完全二叉树
每层节点添加必须是从左到右，不能跳着添加。每个节点的孩子节点数量可以是0，1，2个。
Xnip2019-10-28_16-44-39.jpg
满二叉树
每个节点的孩子节点要么没有，要么有2个。不允许出现当个孩子的情况。
Xnip2019-10-28_16-47-26.jpg
二叉搜索树
也称二叉排序数。要求该节点的左子树小于节点本身，该节点的又右子树大于节点本身。所以对二叉搜索树进行中序遍历可以得到一个有序的序列。
Xnip2019-10-28_16-50-37.jpg
均衡二叉树
指每个节点的左右子树高度插不能大于一。在二叉搜索树的基础上自动添加的维持平衡的性质。插入、搜索、删除的综合效率比较高。
Xnip2019-10-28_16-53-51.jpg
完美二叉树
每个节点都有两个孩子节点，每一个都被完全填充。
Xnip2019-10-28_16-55-31.jpg
三、二叉搜索树存储原理
二叉搜索树算法的排序规则
- 选择第一个元素作为根节点。
- 之后如果元素大于根节点，放在右子树，小于根节点，放在左子树。
-
最后按照中序遍历的方式进行输出，可以得到排序的结果。
Xnip2019-10-28_17-00-01.jpg
四、具体代码的实现
// 添加节点
public void addNode(int data){
if (data < this.data){
if (this.left == null){
this.left = new Node(data);
}else {
this.left.addNode(data);
}
}else {
if (this.right == null){
this.right = new Node(data);
}else {
this.right.addNode(data);
}
}
}
// 遍历节点
public void printNode(){
if (this.left != null){
this.left.printNode();
}
System.out.print(this.data + "=>");
if (this.right != null){
this.right.printNode();
}
}
详细代码可参考
https://github.com/JacksonMike/Java_ultimate/blob/master/BinaryTree.java
五、 二叉树的应用场景
- 与多叉树相比，二叉树的高度比较低，拥有较高的查找性能，所以常常用于数据库索引和文件系统。
- 是项目中应用较多的数据结构，例如Map, Set, JVM的堆内存结构是完全二叉树。
