关于二叉树遍历规则:
http://blog.chinaunix.net/u1/53217/showart_1331012.html采用递归的方式创建和遍历链式二叉树
NOTE:
1、build_tree函数中必须加入fflush(stdin);因为前面一次输入有一个回车符
2、build_tree函数的参数需要传递t的地址而不是t, 即&t
3、有3个版本的,选个最简单的发,前两个是数据结构书上的
4、scanf_s是VC里面的,用scanf当然是可以的,VC警告说不安全
输入:
每输入一个字符回车,按先序遍历顺序输入,无节点的则输入空格(如果你不知道输入的树是什么样的那就在最后不断的输入空格回车吧,总会结束的!)
代码:
#include <stdio.h>
#include <stdlib.h>
#define OK 1
struct node{
char key;
struct node *lchild;
struct node *rchild;
};
typedef struct node Node;
char key;
/* 必须传递指针的指针 ,因为有malloc操作,形参改变不会影响实参 */
int build_tree(Node **t)
{
scanf_s("%c",&key);
fflush(stdin); /* 清除回车符 */
if(key==' '){
*t=NULL;
}
else{
*t=(Node *)malloc(sizeof(Node));
if(*t == NULL){
printf("Malloc error!\n");
exit(1);
}
(*t)->key=key;
//(*t)->lchild=NULL;
//(*t)->rchild=NULL;
build_tree(&(*t)->lchild);
build_tree(&(*t)->rchild);
}
return OK;
}
int PreOrderTraverse(Node *t)
{
if(t){
printf("%c",t->key);
PreOrderTraverse(t->lchild);
PreOrderTraverse(t->rchild);
}
return OK;
}
int InOrderTraverse(Node *t)
{
if(t){
InOrderTraverse(t->lchild);
printf("%c",t->key);
InOrderTraverse(t->rchild);
}
return OK;
}
int PostOrderTraverse(Node *t)
{
if(t){
PostOrderTraverse(t->lchild);
PostOrderTraverse(t->rchild);
printf("%c",t->key);
}
return OK;
}
int main(int argc,char **argv)
{
Node *tree=NULL;
printf("Input nodes:\n");
build_tree(&tree);
printf("The previous order:");
PreOrderTraverse(tree);
printf("\n");
printf("The in order:");
InOrderTraverse(tree);
printf("\n");
printf("The post order:");
PostOrderTraverse(tree);
printf("\n");
return 0;
}
|
阅读(823) | 评论(0) | 转发(0) |