特点：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树，这点很重要，
代码：
package Tree; public class SortTree { public static void main(String[] args) { //添加 int array[] = {1,4,6,2,8,3,12,90,45,32,89}; BinarySortTree binarySortTree = new BinarySortTree(); //循环添加结点 for (int i = 0 ; i < array.length ; i++){ binarySortTree.addNode(new Node(array[i])); } //中序遍历 binarySortTree.preOrder(); } } class BinarySortTree{ //根结点 private Node root; public void setRoot(Node root) { this.root = root; } //添加结点 public void addNode(Node node){ if (this.root == null){ root = node; }else { this.root.addNode(node); } } //先序遍历 public void preOrder(){ if (this.root != null){ this.root.preOrder(); }else { System.out.println("空树"); } } } class Node{ int value;//结点的值 Node left;//左子树 Node right;//右子树 public Node(int value) { this.value = value; } @Override public String toString() { return "Node{" + "value=" + value + '}'; } //添加结点 public void addNode(Node node){ if (node == null){ return; } if (node.value < this.value){ if (this.left == null){ this.left = node; }else { this.left.addNode(node); } } else { if (node.value > this.value){ if (this.right == null){ this.right = node; }else { this.right.addNode(node); } } } } //前序遍历 public void preOrder() { //输出root结点 System.out.println(this); if (this.left != null) { this.left.preOrder();//递归左子结点 } if (this.right != null) { this.right.preOrder(); } } }
