摘要：泛型簡(jiǎn)易實(shí)現(xiàn)根節(jié)點(diǎn)二叉樹的節(jié)點(diǎn)節(jié)點(diǎn)的值左右孩子節(jié)點(diǎn)先序遍歷方法用于測(cè)試二叉查找樹插入二叉樹的節(jié)點(diǎn)節(jié)點(diǎn)的值左右孩子節(jié)點(diǎn)根節(jié)點(diǎn)插入節(jié)點(diǎn)先序遍歷方法用于測(cè)試先序遍歷迭代器

public class Tree {
    private Node root;   //根節(jié)點(diǎn)

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

    /*二叉樹的節(jié)點(diǎn)*/
    private static class Node {
        T element;  //節(jié)點(diǎn)的值
        Node lchild, rchild; //左右孩子節(jié)點(diǎn)

        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方法用于測(cè)試*/
    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> {
    /*二叉樹的節(jié)點(diǎn)*/
    private static class Node {
        T element;  //節(jié)點(diǎn)的值
        Node lchild, rchild; //左右孩子節(jié)點(diǎn)

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

     Node root = null;   //根節(jié)點(diǎn)

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

    /*插入節(jié)點(diǎn)*/
    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方法用于測(cè)試*/
    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  
        }
    }