题目描述

输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。

---

输入描述:

输入第一行包括一个整数n(1<=n<=100)。
接下来的一行包括n个整数。

---

输出描述:

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。
每种遍历结果输出一行。每行最后一个数据之后有一个空格。

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

---

示例1

输入

5
1 6 5 9 8

输出

1 6 5 9 8
1 5 6 8 9
5 8 9 6 1

---

分析

注意点：
1.知道结构体及指针的基本使用方法
2.用while(scanf()!=EOF)作为输入！

---

代码

#include <stdio.h>
#include <stdlib.h>

typedef struct Tree {
	int data;
	struct Tree *left, *right;
} BiTNode,BiTree;

BiTree* Insert(BiTree* t, int tem) {
	if(t==NULL) {
		t = (BiTNode*)malloc(sizeof(BiTNode));
		t->data = tem;
		t->left = t->right = NULL;
	} else if(tem < t->data) {
		t->left = Insert(t->left,tem);
	} else if(tem > t->data) {
		t->right = Insert(t->right,tem);
	}
	return t;
}

/**
* 先序遍历 中左右
*/
void outP(BiTree* t) {
	printf("%d ",t->data);
	if(t->left!=NULL) {
		outP(t->left);
	}
	if(t->right!=NULL) {
		outP(t->right);
	}
}

/**
* 中序遍历 左中右
*/
void outM(BiTree* t) {
	if(t->left) {
		outM(t->left);
	}
	//cout<<t->data<<" ";
	printf("%d ",t->data);
	if(t->right) {
		outM(t->right);
	}
}

/**
* 后序遍历 左右中
*/
void outE(BiTree* t) {
	if(t->left) {
		outE(t->left);
	}
	if(t->right) {
		outE(t->right);
	}
	printf("%d ",t->data);
}

int main() {
	int n,tem,i;
	BiTree *T = NULL;
	while(scanf("%d",&n)!=EOF) {
		T = NULL;
		for( i = 0; i<n; i ++) {
			//cin>>tem;
			scanf("%d",&tem);
			T = Insert(T,tem);
		}
		outP(T);
		printf("\n");
		outM(T);
		printf("\n");
		outE(T);
		printf("\n");
	}
	return 0;
}