import java.util.Scanner;
/**
* 二叉排序树的创建和使用
* 7 10 8 15 7 11 58 9 小的放左边大的放右边,中序遍历则为排序,称为树的排序
* @author lenovo
*
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//用例
for(int i=0;i<n;i++){
Tree t = new Tree();
int m=sc.nextInt();
int e;
for(int j=0;j<m;j++){
e = sc.nextInt();
TreeNode node = new TreeNode(e);
t.setRoot(t.insert(t.getRoot(), node));
}
System.out.println("中序遍历");
t.coreorder(t.getRoot());
}
}
}
class Tree{
TreeNode root;
public Tree(){
this.root = null;
}
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
//构造数,令p为根,q为插入的点,返回值类型为TreeNode点
public TreeNode insert(TreeNode p,TreeNode q){
if(p==null){
p=q;
}else{
if(p.getData()>q.getData()){
p.setLeft(insert(p.getLeft(),q));//巧用递归
}else{
p.setRight(insert(p.getRight(),q));
}
}
return p;
}
//前序遍历
public void preorder(TreeNode p){
if(p==null)
return;
System.out.print(p.getData()+" ");
preorder(p.getLeft());
preorder(p.getRight());
}
//中序遍历
public void coreorder(TreeNode p){
if(p==null)
return;
coreorder(p.getLeft());
System.out.print(p.getData()+" ");
coreorder(p.getRight());
}
//后续遍历
public void postorder(TreeNode p){
if(p==null)
return;
postorder(p.getLeft());
postorder(p.getRight());
System.out.print(p.getData()+" ");
}
}
class TreeNode{
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(){
this.left = null;
this.right = null;
}
public TreeNode(int data){
this.data = data;
this.left = left;
this.right = right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
1
9
1 4 7 8 9 6 3 2 5
中序遍历
1 2 3 4 5 6 7 8 9
View Code