二叉排序树

二叉排序树题目题目描述：
输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
输入：
输入第一行包括一个整数n（1<=n<=100）。
接下来的一行包括n个整数。
输出：
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。
每种遍历结果输出一行。每行最后一个数据之后有一个空格。
样例输入：
5
1 6 5 9 8
样例输出：
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1
提示：
输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。AC代码#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 101

struct btree
{
struct btree *lchild, *rchild;
int data;
};

struct stack
{
struct btree* arr[N];
int top;
};

struct btree* create_sortree（struct btree* t, int d）;
void pre_traverse（struct btree *t）;
void order_traverse（struct btree *t）;
void post_traverse（struct btree *t）;
void clean_tree（struct btree *t）;

int main（）
{
int i, n, d;
struct btree *t;
while （scanf（"%d", &n）！= EOF） {
//接收客户端输入，构建二叉排序树
for （i = 0, t = NULL; i < n; i ++） {
scanf（"%d", &d）;
t = create_sortree（t, d）;
}

// 前序遍历
pre_traverse（t）;

// 中序遍历
order_traverse（t）;

// 后序遍历
post_traverse（t）;

// 清理
clean_tree（t）;
}

return 0;
}

struct btree* create_sortree（struct btree *t, int d）
{
if （t == NULL） {
t = （struct btree*）malloc（sizeof（struct btree） * 1）;
t->data = d;
t->lchild = NULL;
t->rchild = NULL;
}else if（t->data > d） { // 插入到左子树
t->lchild = create_sortree（t->lchild, d）;
}else if（t->data < d） { // 插入到右子树
t->rchild = create_sortree（t->rchild, d）;
}else {
// 相同元素不进行任何操作
}

return t;
}

void pre_traverse（struct btree *t）
{
struct btree *p = t;
struct stack *s = （struct stack*）malloc（sizeof（struct stack） * 1）;
s->top = 0;

while （s->top || p） {
if （p） {
printf（"%d ", p->data）;
s->arr[s->top ++] = p;
p = p->lchild;
}else {
p = s->arr[-- s->top];
p = p->rchild;
}
}

printf（" "）;
}

void order_traverse（struct btree *t）
{
struct btree *p = t;
struct stack *s = （struct stack*）malloc（sizeof（struct stack） * 1）;
s->top = 0;

while （s->top || p） {
if （p） {
s->arr[s->top ++] = p;
p = p->lchild;
}else {
p = s->arr[-- s->top];
printf（"%d ", p->data）;
p = p->rchild;
}
}

printf（" "）;
}

void post_traverse（struct btree *t）
{
struct btree *p, *pre;
struct stack *s = （struct stack*）malloc（sizeof（struct stack） * 1）;
s->top = 0;
pre = NULL;
p = t;

while （p || s->top） {
if （p） {
s->arr[s->top ++] = p;
p = p->lchild;
}else {
p = s->arr[-- s->top];
if （p->rchild == NULL || p->rchild == pre） {
printf（"%d ", p->data）;
pre = p;
p = NULL;
}else {
s->arr[s->top ++] = p;
p = p->rchild;
}
}
}

printf（" "）;
}

void clean_tree（struct btree *t）
{
if （t） {
clean_tree（t->lchild）;
clean_tree（t->rchild）;
free（t）;
}
}
/**************************************************************
Problem: 1201
User: wangzhengyi
Language: C
Result: Accepted
Time:70 ms
Memory:3284 kb
****************************************************************/后记

算法导论上二叉排序树应该是最简单最容易理解的，这里记录一下，当数据结构复习吧