二叉树相关操作

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

/**
 * Created by Leon on 2017/4/4.
 * 二叉树
 */
class Node
{
    public int key;
    public Object value;
    public Node leftChildNode;
    public Node rightChildNode;
    //构造方法
    public Node(int key,Object value)
    {
        super();
        this.key=key;
        this.value=value;
    }
}

public class Tree
{
    //根节点
    private Node root;
    //构造方法
    public Tree(){}
    public Tree(Node root)
    {
        this.root=root;
    }
    /**
     * 插入节点
     */
    public void insert(int key,Object value)
    {
        Node node=new Node(key,value);
        if (this.root==null)
        {
            this.root=node;
        }else
        {
            Node currentNode=this.root;
            while(true)
            {
                if (key>currentNode.key)
                {
                    if (currentNode.rightChildNode == null)
                    {
                        currentNode.rightChildNode = node;
                        return;
                    }else
                    {
                        currentNode = currentNode.rightChildNode;
                    }
                }else
                {
                    if (currentNode.leftChildNode == null)
                    {
                        currentNode.leftChildNode = node;
                        return;
                    }else
                    {
                        currentNode = currentNode.leftChildNode;
                    }
                }
            }
        }
    }
    /**
     * 查找节点
     */
    public Node find(int key)
    {
        if (this.root!=null)
        {
            Node currentNode=this.root;
            while(currentNode.key!=key)
            {
                if (key>currentNode.key)
                {
                    currentNode=currentNode.rightChildNode;
                }else
                {
                    currentNode=currentNode.leftChildNode;
                }
                if (currentNode==null)
                {
                    return null;
                }
            }
        }
        return null;
    }

    /**
     * 展示
     */
    public void show()
    {
        this.show(root);
    }
    /**
     * 中序遍历
     */
    private void show(Node node)
    {
        if (node != null) {
            this.show(node.leftChildNode);
            System.out.println(node.key + ":" + node.value);
            this.show(node.rightChildNode);

        }
    }
    public static void main(String[] args)
    {
        Node root = new Node(50, 24);
        Tree tree = new Tree(root);
        tree.insert(20, 530);
        tree.insert(540, 520);
        tree.insert(4, 540);
        tree.insert(0, 550);
        tree.insert(8, 520);
        tree.show();
    }

}