package 数据结构;

//二分搜索树——简化版

public class BST2<E extends Comparable<E>> {

private class Node {// 定义结点类

public E e;

public Node left, right;

public Node(E e) {

this.e = e;

left = null;

right = null;

}

}

private Node root;// 定义根结点

private int size;// 定义数的元素数量

public BST2() {// 定义构造方法

root = null;

size = 0;

}

public int size() {// 返回树大小的方法

return size;

}

public boolean isEmpty() {// 判断树是否为空的方法

return size == 0;

}

public void add(E e) {// 用户传入 一个元素，加入树中

root = add(root, e);// 先看根结点是不是空的，如果是空的直接赋值给根结点

// 如果根结点不是空的，那么将根结点下面的元素加好，再返回新树的根结点

}

public Node add(Node node, E e) {// 当根结点不为空的时候开始判断

if (node == null) {

size++;// 如果当前结点是空的，那直接返回一个新结点连上去就行了

return new Node(e);// 如果不是空的，那么就交给下面递归判断看大于还是小于

}

if (e.compareTo(node.e) < 0)// 要是小于，那就放左边，同样先看看左边是不是空的

node.left = add(node.left, e);// 左边是空的就将需要加入的赋值给左边

else if (e.compareTo(node.e) > 0)

node.right = add(node.right, e);

return node;// 最后返回已经添加好元素的这颗树

}

// 查看树是否含有该元素

public boolean contains(E e) {

return contains(root, e);

}

private boolean contains(Node node, E e) {

if (node == null) {

return false;

}

if (e.compareTo(node.e) == 0)

return true;

else if (e.compareTo(node.e) < 0)

return contains(node.left, e);

else

return contains(node.right, e);

}

// 前序遍历

public void preOrder() {

preOrder(root);

}

// 前序遍历以root为根的二分搜索树，递归算法

private void preOrder(Node node) {

if (node == null)

return;

System.out.println(node.e);

preOrder(node.left);

preOrder(node.right);

}

// 中序遍历

public void inOrder() {

inOrder(root);

}

// 中序遍历以root为根的二分搜索树，递归算法

private void inOrder(Node node) {

if (node == null)

return;

preOrder(node.left);

System.out.println(node.e);

preOrder(node.right);

}

// 后序遍历

public void postOrder() {

postOrder(root);

}

// 后序遍历以root为根的二分搜索树，递归算法

private void postOrder(Node node) {

if (node == null)

return;

preOrder(node.left);

preOrder(node.right);

System.out.println(node.e);

}

public static void main(String[] args) {

// TODO 自动生成的方法存根

BST2<Integer> bst = new BST2<Integer>();// 做一个二叉树的对象

int nums[] = { 5, 3, 6, 8, 4, 2 };// 定义数组

for (int num : nums) // 将数组元素输入二叉树

bst.add(num);

bst.preOrder();

System.out.println();

bst.inOrder();

System.out.println();

bst.postOrder();

}

}

问题描述：

问题描述：

老师为什么我的中序得到的结果和你的不一样，我的从根的左边找，你的会从最底部