数据结构之二叉树

为什么要定义树这种数据结构？

线性表 和 链表 常见的两种数据结构。但是各有所长。
线性表顺序存储，通过下标随机访问元素十分方便.但是在删除和插入的时候比较困难。
链表一般不连续存储，查找元素必须遍历整个表，但是在插入删除的时候十分快捷。
折衷之下，树应运而生。

二叉树

---

二叉树的特点

每个节点最多只有两个子节点。二叉树的一个节点的值大于其左孩子的值，小于其右孩子的值（如果有的话）。
一棵二叉树最多拥有 2^n - 1个节点，最多有2^(n - 1)个叶子节点。n为树的高度。

二叉树节点的定义

class TreeNode{
    public int value;
    public TreeNode leftChild = null;
    public TreeNode rightChild = null;
    TreeNode( int value){//初始化方法
        this.value = value; 
    } 
        TreeNode(){}
}

二叉树插入操作

private TreeNode root;
public void insert(int value){
        TreeNode newNode = new TreeNode(value);
        if(root == null){
            root = newNode;
        }else{
            TreeNode current = root;
            TreeNode parent;
            while (true) {
                parent = current;
                if(value < parent.value){
                    current = current.leftChild;
                    if(current == null){
                        parent.leftChild = newNode;
                        return;
                    }
                }else{
                    current = current.rightChild;
                    if(current == null){
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }