任务：动态创建一个如图所示的树，并且用三种方式（前、中、后序）输出结果；
一、节点
typedef struct Tree{
int data;
struct Tree * plchild;//左指针域
struct Tree * prchild;//右指针域
}TREE,*PTREE;
二、动态创建树函数
思路：
创建树函数，本质上是递归,返回根节点的地址。
根节的点左树和右树也可以有左树和右树，意味着可以递归使用创建树函数；
如果不需要创建子树，输入一个-1表示不用创建即可；
PTREE creat_tree(void){
int data;
scanf("%d",&data);
PTREE p = (PTREE)malloc(sizeof(TREE));
PTREE prot = p;//第一个根节点的地址另外保存
p->data = data;
if(data == -1){
return NULL;
}else{
printf("请输入%d左子树(输入-1代表不用创建): ",data);
p->plchild = creat_tree();//新创建树，将地址赋值给根节点的左指针域
printf("请输入%d右子树(输入-1代表不用创建): ",data);
p->prchild = creat_tree();//新创建树，将地址赋值给根节点的右指针域
return prot;
}
}
三、前序遍历（中、后序一样的）
前：
思路：递归 1.访问根节点 2.前序遍历根结点左子树 3.前序遍历根节点右子树
void pre_traverse(PTREE p){
if(p==NULL){
return;
}else{
printf("%d",p->data);
if(p->plchild != NULL){
pre_traverse(p->plchild);
}
if(p->prchild != NULL){
pre_traverse(p->prchild);
}
}
}
中：
思路：递归 1.中序遍历根结点左子树 2.访问根节点 3.中序遍历根节点右子树
void in_traverse(PTREE p){
if(p==NULL){
return;
}else{
if(p->plchild != NULL){
in_traverse(p->plchild);
}
printf("%d",p->data);
if(p->prchild != NULL){
in_traverse(p->prchild);
}
}
}
后;
思路：递归 1.后序遍历根结点左子树 2.后序遍历根节点右子树 3.访问根节点
void end_traverse(PTREE p){
if(p==NULL){
return;
}else{
if(p->plchild != NULL){
end_traverse(p->plchild);
}
if(p->prchild != NULL){
end_traverse(p->prchild);
}
printf("%d",p->data);
}
}
四、主函数代码：
#include#include typedef struct Tree{ int data; struct Tree * plchild;//左指针域 struct Tree * prchild;//右指针域 }TREE,*PTREE; PTREE creat_tree(void); void pre_traverse(PTREE p); void in_traverse(PTREE p); void end_traverse(PTREE p); int main(void){ printf("请输入第一个节点的数据：n"); PTREE p = creat_tree(); printf("前序输出的结果是：n"); pre_traverse(p); printf("n中序输出的结果是：n"); in_traverse(p); printf("n后序输出的结果是：n"); end_traverse(p); return 0; }
运行结果：
