二叉搜索树的实现（Java）

二叉搜索树又叫二叉查找树、二叉排序树。

1. 如果左子树不为空，则左子树上的结点的值都小于根结点。
2. 如果右子树不为空，则右子树上的结点的值都大于根结点。
3. 所有的子树都遵循以上两点。

二叉树是一种动态查找表。树的结构不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

所以当相同的值插入时只有一个存在。

二叉搜索树的中序遍历（左根右）是从大到小排序的。

import java.util.ArrayList;
import java.util.List;


public class BinarySearchTree {
    private int data;
    private BinarySearchTree left;
    private BinarySearchTree right;

    public BinarySearchTree(int data) {
        this.data = data;
    }

    
    public void insert(BinarySearchTree root, int data) {
        //右子树
        if (root.data < data) {
            if (root.right == null) {
                root.right = new BinarySearchTree(data);
            }else {
                insert(root.right,data);
            }
        }
        //左子树
        if (root.data > data) {
            if (root.left == null) {
                root.left = new BinarySearchTree(data);
            }else {
                insert(root.left,data);
            }
        }
    }
    
    
    public static BinarySearchTree generateBinarySearchTreeByArray(int[] array) {
        if (array.length != 0) {
            BinarySearchTree tree = new BinarySearchTree(array[0]);
            for (int i = 1; i < array.length; i++) {
                tree.insert(tree,array[i]);
            }
            return tree;
        }
        return null;
    }

    private List beforeList = new ArrayList<>();
    
    private void beforeTraversal(BinarySearchTree tree) {
        if (tree != null) {
            beforeList.add(tree.data);
            beforeTraversal(tree.left);
            beforeTraversal(tree.right);
        }
    }
    
    public List getBeforeList(BinarySearchTree tree) {
        tree.beforeTraversal(tree);
        return beforeList;
    }

    private List inList = new ArrayList<>();
    
    private void inTraversal(BinarySearchTree tree) {
        if (tree != null) {
            inTraversal(tree.left);
            inList.add(tree.data);
            inTraversal(tree.right);
        }
    }
    
    public List getInList(BinarySearchTree tree) {
        tree.inTraversal(tree);
        return inList;
    }

    private List afterList = new ArrayList<>();
    
    private void afterTraversal(BinarySearchTree tree) {
        if (tree != null) {
            afterTraversal(tree.left);
            if (tree.right != null) {
                afterTraversal(tree.right);
            }
            afterList.add(tree.data);
        }
    }
    
    public List getAfterList(BinarySearchTree tree) {
        tree.afterTraversal(tree);
        return afterList;
    }
	//省略getter/setter...
}

测试：将数组{10,8,12,5,9,1,6}转换为二叉搜索树并获取前中后序遍历。

public class Main {
    public static void main(String[] args) {
        int[] nums = {10,8,12,5,9,1,6};
        BinarySearchTree tree = BinarySearchTree.generateBinarySearchTreeByArray(nums);
        assert tree != null;

        System.out.println("前序遍历：" + tree.getBeforeList(tree));
        System.out.println("中序遍历：" + tree.getInList(tree));
        System.out.println("后序遍历：" + tree.getAfterList(tree));
    }
}