摘要：泛型簡易實現根節點二叉樹的節點節點的值左右孩子節點先序遍歷方法用于測試二叉查找樹插入二叉樹的節點節點的值左右孩子節點根節點插入節點先序遍歷方法用于測試先序遍歷迭代器

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  
        }
    }