// 增加二叉树的3种遍历函数,用于测试创建的排序二叉树是否正确.
//
// 输入序列:
// 50 20 10 30 60 0
// 前序遍历序列: 50 20 10 30 60
// 中序遍历序列: 10 20 30 50 60
// 后序遍历序列: 10 30 20 60 50
//
// 二叉树示意图:
//
// 50
// / \
// 20 60
// / \
// 10 30
//
#include
#include
struct node //二叉树的结构体
{
int value;
struct node *lCh,*rCh;
};
struct node *st=NULL;
void preOrder(struct node *ptr) //前序遍历(递归法)
{
if(ptr!=NULL)
{
printf("%d ",ptr->value);
preOrder(ptr->lCh);
preOrder(ptr->rCh);
}
}
void inOrder(struct node *ptr) //中序遍历(递归法)
{
if(ptr!=NULL)
{
inOrder(ptr->lCh);
printf("%d ",ptr->value);
inOrder(ptr->rCh);
}
}
void postOrder(struct node *ptr) //后序遍历(递归法)
{
if(ptr!=NULL)
{
postOrder(ptr->lCh);
postOrder(ptr->rCh);
printf("%d ",ptr->value);
}
}
//原函数insert()的输入参数tree是指针,而只是用指针,返回不了tree,
//所以改用"指针的指针",才能返回创建后的tree
//原代码void insert(struct node *tree,int v)
void insert(struct node **tree,int v) //这里tree是"指针的指针"
{
if(*tree == NULL) //所有的tree前面都要加上"*"(星号)
{
//原代码tree=(struct node*)malloc(sizeof(struct node *tree));
*tree=(struct node*)malloc(sizeof(struct node));
(*tree)->value=v;
(*tree)->lCh = (*tree)->rCh = NULL;
return;
}
if(v < (*tree)->value)
{
insert(&((*tree)->lCh),v);
}
else
{
insert(&((*tree)->rCh),v);
}
}
void input()
{
while(1)
{
int v;
scanf("%d",&v);
if(v <= 0)
{
break;
}
//原代码insert(st,v);
insert(&st,v); //注意:st前面是"&"(取地址符号)
}
}
int main() //原代码main()
{
input();
printf("\n前序遍历序列: ");
preOrder(st);
printf("\n中序遍历序列: ");
inOrder(st);
printf("\n后序遍历序列: ");
postOrder(st);
return 0; //函数int main()要有返回值
}