二叉树数据结构原理

一、二叉树的概念

二叉树是树类中应用最广泛的一种数据结构，也是非线性数据结构。二叉树的每个节点最多只能包含两个子节点，通常我们称之为左右子树。

二、二叉树的分类以及其特点

比较常见的一些树的名称及其种类如下

完全二叉树

每层节点添加必须是从左到右，不能跳着添加。每个节点的孩子节点数量可以是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的堆内存结构是完全二叉树。