Java温故而知新-二叉树

二叉树

主要用于提升查询的效率的。

根节点

取第一个数据作为根节点的保存数据

左子树

比根节点小的数据放在左子树（也可以保存相等的数据，或者就干脆不保存相等）

右子树

比根节点大的数据放在右子树

倒过来看就是：

前序遍历

根-左-右

中序遍历

左-根-右

后序遍历

左-右-根

面试题

Github JS 图形化示例

https://github.com/archelangelo/tree-builder 等我有空了，我要结束这个js图形界面展示，实现一个二叉树展示界面。

实现二叉树的增加操作

interface IBinaryTree {      //定义二叉树标准操作接口
    public void add(E data);    //实现数据的增加
}

class BinaryTreeImpl implements IBinaryTree{

    private class Node{         //该内部类只为当前的外部类提供服务
        private Comparable data;     //要存储的数据，全部进行强制性转型
        private Node left;          //左子树
        private Node right;         //右子树
        private Node parent;        //父节点
        public Node(Comparable data){        //节点创建的同时保存数据
            this.data = data;
        }


    }


    // ----------------以下的操作为二叉树实现结构----------------
    private Node root;      //数据结构都需要提供有根节点
    @Override
    public void add(E data) {
        if(data ==null ){
            throw new NullPointerException("存储在二叉树结构中的数据不允许为null.");
        }
        if(!(data instanceof  Comparable)){
            throw new ClassCastException("要保存数据对象所在的类没有实现java.lang.Comparable接口。");
        }
        Node newNode = new Node((Comparable) data);         //将数据保存在节点之中
        if(this.root ==null){           //当前没有根节点存在
            this.root = newNode;        //保存根节点
        } else {            //需要确定节点的存储位置
            Node currentNode = this.root;   //设置当前节点
            while (currentNode!=newNode){      //当前节点不是新节点，表示新的节点未保存
                if(currentNode.data.compareTo(data)