/*
时间：2014.1.31
目的：题目1201：二叉排序树 http://ac.jobdu.com/problem.php?pid=1201
*/
#include <stdio.h>
#include <malloc.h>
struct TreeNode{
struct TreeNode *left;
struct TreeNode *right;
int data;
};
void First(TreeNode *p)//前序
{
if(p!=NULL)
{
printf("%d ",p->data);
First(p->left);
First(p->right);
}
}
void Middle(TreeNode *p)//中序
{
if(p!=NULL)
{
Middle(p->left);
printf("%d ",p->data);
Middle(p->right);
}
}
void Last(TreeNode *p)//后序
{
if(p!=NULL)
{
Last(p->left);
Last(p->right);
printf("%d ",p->data);
}
}
void createTree(TreeNode *pt,int n)//建树
{
int i, t;
struct TreeNode *tp = pt;
struct TreeNode *p ;
scanf("%d", &(pt->data));
pt->left = pt->right = NULL;
for(i = 0;i < n - 1;i ++)
{
tp = pt;
p = (TreeNode*)malloc(sizeof(TreeNode));
p->left = p->right = NULL;
scanf("%d", &t);
p->data = t;
while(tp&&tp->data!= t)
{
if(tp->data > t)
{
if(tp->left!=NULL)
tp=tp->left;
else
{
tp->left = p;
break;
}
}
else if(tp->data < t)
{
if(tp->right!=NULL)
tp=tp->right;
else
{
tp->right = p;
break;
}
}
}
}
}
int main()
{
int n, i, t;
while(~scanf("%d", &n))
{
struct TreeNode *pt = (TreeNode*)malloc(sizeof(TreeNode));
struct TreeNode *tp;
createTree(pt,n);
tp = pt;
First(tp);
printf("\n");
Middle(tp);
printf("\n");
Last(tp);
printf("\n");
free(pt);
}
return 0;
}
/*
-------------------
5 思路：1.模拟
1 6 5 9 8
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1
-------------------
*/ 原文：http://blog.csdn.net/z_x_b5/article/details/18889569