二叉排序树_求二叉树的高度

如果定义一颗二叉树的高度就是从根到叶子的最长距离。试编码求二叉树的高度。


其实，二叉树的高度就是它的左子树和右子树中高度最大值 + 1


另外考虑: 当待排序的数据本来就是有序的情况，会发生什么？

请参考《数据结构》教材解决这个问题。

class BiTree {
private int data;
private BiTree left;
private BiTree right;

public BiTree(int x) {
data = x;
}

//小的数放左边，大的数放右边
public void add(BiTree t) {
if (t.data if (left == null) {
left = t;
} else {
left.add(t);
}
} else {
if (right == null) {
right = t;
} else {
right.add(t);
}
}
}
//中序遍历，先左子树，再自身，再右子树
//递归思想
public void travel() {
if (left != null) {
left.travel();
}
System.out.print(data+" ");
if (right != null) {
right.travel();
}
}

//求高度
//递归思想
public int height(){
int treeHeight = 0;
int leftHeight,rightHeight;
if(this == null){
return 0;
}else{
leftHeight = (left == null? 0:left.height());
rightHeight = (right == null? 0:right.height());
treeHeight = Math.max(leftHeight, rightHeight);
return 1+treeHeight;
}
}
}

public class My1 {
public static void main(String[] args) {
BiTree t = new BiTree(12);
t.add(new BiTree(9));
t.add(new BiTree(5));
t.add(new BiTree(8));
t.add(new BiTree(15));
t.add(new BiTree(20));
t.add(new BiTree(11));

t.travel();//遍历

System.out.println();
System.out.println("树的高度是："+t.height());
}
}

Conclusion
5 8 9 11 12 15 20 
树的高度是：4

当排序数据自身就是有序的时，这个队列元素的个数即二叉树的高度