간단한 두 갈래 찾기 트리 구현

/** * <p> *     * </p> * * @author Vicky * @date 2015-8-10 */
public class BinarySearchTree {
    private Node root;
    private int num;//     
    private int index;//     

    public BinarySearchTree() {
        super();
    }

    public BinarySearchTree(Node root) {
        super();
        this.root = root;
        this.num++;
    }

    public Node getRoot() {
        return root;
    }

    /** *           * * @param node * @return */
    public BinarySearchTree addNode(Node node) {
        this.num++;
        if (null == root) {
            root = node;
            return this;
        }
        addNode(node, root);
        return this;
    }

    /** *        * * @param node * @param parent */
    private void addNode(Node node, Node parent) {
        if (node.getVal() > parent.getVal()) {
            if (null == parent.getRight()) {
                parent.setRight(node);
            } else {
                addNode(node, parent.getRight());
            }
        } else if (node.getVal() < parent.getVal()) {
            if (null == parent.getLeft()) {
                parent.setLeft(node);
            } else {
                addNode(node, parent.getLeft());
            }
        } else {
            return;
        }
    }

    /** *      */
    public int[] inorderTraversal() {
        if (this.num == 0) {
            return null;
        }
        this.index = 0;
        int[] vals = new int[this.num];
        inorderTraversal(getRoot(), vals);
        return vals;
    }

    /** *      * * @param node * @param vals */
    private void inorderTraversal(Node node, int[] vals) {
        if (null == node) {
            return;
        }
        inorderTraversal(node.getLeft(), vals);
        vals[index++] = node.getVal();
        inorderTraversal(node.getRight(), vals);
    }

    @Override
    public String toString() {
        return "BSTree [root=" + root + "]";
    }
}

/** * <p> *    * </p> * * @author Vicky * @date 2015-8-10 */
class Node {
    private final int val;
    private Node left;
    private Node right;

    public Node(int val) {
        this(val, null, null);
    }

    public Node(int val, Node left, Node right) {
        super();
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getVal() {
        return val;
    }

    @Override
    public String toString() {
        return "Node [left=" + left + ", right=" + right + ", val=" + val + "]";
    }
}

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;

/** * <p> *          * </p> * * @author Vicky * @date 2015-8-10 */
public class BinarySearchTreeTest {
    public static void main(String[] args) {
        BinarySearchTree tree = buildTree();
        int[] vals = tree.inorderTraversal();
        System.out.println(Arrays.toString(vals));

        for (int i = 0; i < 10; i++) {
            addNode(tree);
            vals = tree.inorderTraversal();
            System.out.println(Arrays.toString(vals));
        }
    }

    /** *         * * @return */
    public static BinarySearchTree buildTree() {
        Random ran = new Random();
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < 20; i++) {
            set.add(ran.nextInt(500));
        }
        BinarySearchTree tree = new BinarySearchTree();
        Iterator<Integer> ite = set.iterator();
        while (ite.hasNext()) {
            tree.addNode(new Node(ite.next()));
        }
        return tree;
    }

    public static BinarySearchTree addNode(BinarySearchTree tree) {
        Random ran = new Random();
        tree.addNode(new Node(ran.nextInt(1000)));
        return tree;
    }
}