【Java】二叉树的实现

摘要：泛型简易实现根节点二叉树的节点节点的值左右孩子节点先序遍历方法用于测试二叉查找树插入二叉树的节点节点的值左右孩子节点根节点插入节点先序遍历方法用于测试先序遍历迭代器

public class Tree {
    private Node root;   //根节点

    public Tree(Node root) {
        this.root = root;
    }

    /*二叉树的节点*/
    private static class Node {
        T element;  //节点的值
        Node lchild, rchild; //左右孩子节点

        public Node(T element, Node lchild, Node rchild) {
            this.element = element;
            this.lchild = lchild;
            this.rchild = rchild;
        }   
    }

    /*先序遍历*/
    public void preorder(Node root   ) {
        if(root != null) {
            System.out.println(root.element);
            preorder(root.lchild);
            preorder(root.rchild);
        }
    }

    /*main方法用于测试*/
    public static void main(String[] args) {
        Node lchild = new Node("B", null, null);
        Node rchild = new Node("C", null, null);
        Node root = new Node("A", lchild, rchild);

        Tree tree = new Tree(root);
        tree.preorder(tree.root);

    }
}

public class Tree> {
    /*二叉树的节点*/
    private static class Node {
        T element;  //节点的值
        Node lchild, rchild; //左右孩子节点

        public Node(T element, Node lchild, Node rchild) {
            this.element = element;
            this.lchild = lchild;
            this.rchild = rchild;
        }   
    }

     Node root = null;   //根节点

    public Tree(Node root) {
        this.root = root;
    }   

    /*插入节点*/
    protected Node insert(Noderoot, NodenewNode) {
        if(root == null) {
            root = newNode;
        } else if (root.element.compareTo(root.element) < 0) {
            root.lchild = insert(root.lchild, newNode);
        } else {
            root.rchild = insert(root.rchild, newNode);
        }
        return root;
    }

    public void insert(T data) {
        Node newNode = new Node(data, null, null);
        root = insert(root, newNode);
    }

    /*先序遍历*/
    public void preorder(Node root   ) {
        if(root != null) {
            System.out.println(root.element);
            preorder(root.lchild);
            preorder(root.rchild);
        }
    }

    /*main方法用于测试*/
    public static void main(String[] args) {
        Tree tree = new Tree(null);
        tree.insert("C");
        tree.insert("B");
        tree.insert("A");
        tree.preorder(tree.root);
    }
}

    /** Returns a preorder iterator for this tree. */ 
     public Iterator preorderIterator() { 
     return new PreorderIterator(); 
     } 

    /*** inner class for a preorder iterator ***/
    private class PreorderIterator implements Iterator {
        private Node nextNode;

        private PreorderIterator() {
            // The traversal starts with the root node.
            nextNode = root;
        }

        public boolean hasNext() {
            return (nextNode != null);
        }

        public T next() {
            if (nextNode == null)
                throw new NoSuchElementException();

            // Store a copy of the key to be returned.
            T element = nextNode.element;

            // Advance nextNode.
            if (nextNode.lchild != null)
                nextNode = nextNode.lchild;
            else if (nextNode.rchild != null)
                nextNode = nextNode.rchild;
            else {
                // We"ve just visited a leaf node.
                // Go back up the tree until we find a node
                // with a right child that we haven"t seen yet.
                Node parent = nextNode.parent;
                Node child = nextNode;
                while (parent != null
                        && (parent.rchild == child || parent.rchild == null)) {
                    child = parent;
                    parent = parent.parent;
                }

                if (parent == null)
                    nextNode = null; // the traversal is complete
                else
                    nextNode = parent.rchild;
            }

            return element;
        }

        @Override
        public void remove() {
            // TODO Auto-generated method stub  
        }
    }