二叉搜索树

二叉搜索树：对于二叉树中的每个节点，它的值小于它的左子树中所有结点的值，并且大于它的右子树中的所有结点的值。下图即为一颗二叉树：

在二叉搜索树中插入结点：

递归法与非递归法

public class BinarySearchTree {
    private TreeNode root;
    
    public void insert(int val) {
    	// 递归法插入结点
        root = recursiveInsert(root, val);
        // 非递归法插入结点
        // nonRecursiveInsert(val);
    }

    /**
     * 递归法插入结点
     * @param node
     * @param val
     * @return
     */
    public TreeNode recursiveInsert(TreeNode node, int val) {
        if(node == null) {
            node = new TreeNode(val);
        }else{
            if(val < node.val) {
                node.left = recursiveInsert(node.left, val);
            }else{
                node.right = recursiveInsert(node.right, val);
            }
        }
        return node;
    }
	
	/**
     * 非递归法插入结点
     * @param val
     */
	public void nonRecursiveInsert(int val) {
        if(root == null) {
            root = new TreeNode(val);
        }else{
            TreeNode curNode = root;
            while(true) {
                if(val < curNode.val) {
                    if(curNode.left == null) {
                        curNode.left = new TreeNode(val);
                        break;
                    }else{
                        curNode = curNode.left;
                    }
                }else{
                    if(curNode.right == null) {
                        curNode.right = new TreeNode(val);
                        break;
                    }else{
                        curNode = curNode.right;
                    }
                }
            }
        }
    }
    
    public TreeNode getRoot() {
        return root;
    }
	
	// 前序遍历
	public static void preOrderTraverse(TreeNode node) {
        if(node == null) {
            return;
        }else{
            System.out.print(node.val + " ");
            if(node.left != null) {
                preOrderTraverse(node.left);
            }
            if(node.right != null) {
                preOrderTraverse(node.right);
            }
        }
    }

    public static void main(String[] args) {
        int[] values = {8, 5, 10, 1, 7, 12};

        BinarySearchTree binarySearchTree = new BinarySearchTree();

        for(int val: values) {
            binarySearchTree.insert(val);
        }

        binarySearchTree.preOrderTraverse(binarySearchTree.getRoot());
    }
}