用java构建二叉排序树，实现先序，中序和后序遍历

1.基础知识：

先上图，举个例子：

先选遍历的规则：根节点----左子树----右子树      结果为12-9-76-35-22-16-48-46-40-90

中序遍历的规则：左子树----根节点----右子树      结果为9-12-16-22-35-40-46-48-76-90

后序遍历的规则：左子树----右子树----根节点      结果为9-16-22-40-46-48-35-90-76-12

二叉排序树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态。

2.java代码实现

package cn.edu.ahui;

import org.omg.CORBA.PUBLIC_MEMBER;

//二叉树的数据结果
class BinaryTree{
int val;//根节点数据
BinaryTree left;//左子树
BinaryTree right;//右子树
public BinaryTree(int val){
this.val = val;
this.left = null;
this.right = null;
}
}

public class BinaryTreeBuilder {
//向二叉树中插入子树
public void insert(BinaryTree root, int data){
//二叉排序树的右节点都比根节点大
if(data > root.val){
if(root.right == null)
root.right = new BinaryTree(data);
else
this.insert(root.right,data);//递归插入子节点
}
//二叉排序树的左节点都比根节点小
else{
if(root.left == null)
root.left = new BinaryTree(data);
else
this.insert(root.left, data);//递归插入子节点
}
}


//先序遍历
public static void preOrder(BinaryTree root){
if(root != null){
System.out.print(root.val+"-");
preOrder(root.left);
preOrder(root.right);
}
}

//中序遍历
public static void inOrder(BinaryTree root){
if(root != null){
inOrder(root.left);
System.out.print(root.val+"-");
inOrder(root.right);
}
}

//后序遍历
public static void postOrder(BinaryTree root){
if(root != null){
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+"-");
}
}

public static void main(String[] args){
int[] a = {12,76,35,22,16,48,90,46,9,40};
BinaryTreeBuilder btb = new BinaryTreeBuilder();
BinaryTree root = new BinaryTree(a[0]);
for(int i = 1; i<a.length; i++){
btb.insert(root, a[i]);
}
System.out.print("先序遍历：");
preOrder(root);
System.out.println("");
System.out.print("中序遍历：");
inOrder(root);
System.out.println("");
System.out.print("后序遍历：");
postOrder(root);
}



}

3.代码运行结果

先序遍历：12-9-76-35-22-16-48-46-40-90-

中序遍历：9-12-16-22-35-40-46-48-76-90-

后序遍历：9-16-22-40-46-48-35-90-76-12-