本文实现二叉树的递归创建、遍历及深度计算。即输入:abd##e##cf###（按二叉树结构输入）
二叉树：
返回结果如下：
完整代码如下：
#include <stdio.h>
//树结构
typedef struct tree {
char data;
struct tree *lchild, *rchild;
} tree;
//创建树
struct tree* create_tree() {
char node_data;
scanf("%c", &node_data);
if(node_data == '#') {
return NULL;
} else {
struct tree *T = NULL;
T = (struct tree*)malloc(sizeof(struct tree));
T->data = node_data;
T->lchild = create_tree();
T->rchild = create_tree();
return T;
}
}
//先序遍历
void pre_traverse(struct tree *T) {
if(T == NULL) {
return;
} else {
printf("%c\t", T->data);
pre_traverse(T->lchild);
pre_traverse(T->rchild);
}
}
//中序遍历
void mid_traverse(struct tree *T) {
if(T == NULL) {
return;
} else {
mid_traverse(T->lchild);
printf("%c\t", T->data);
mid_traverse(T->rchild);
}
}
//后序遍历
void aft_traverse(struct tree *T) {
if(T == NULL) {
return;
} else {
aft_traverse(T->lchild);
aft_traverse(T->rchild);
printf("%c\t", T->data);
}
}
//深度
int tree_deepth(struct tree *T) {
int i,j;
if(!T) {
return 0;
} else {
if(T->lchild)
i = tree_deepth(T->lchild);
else
i = 0;
if(T->rchild)
j = tree_deepth(T->rchild);
else
j = 0;
return i > j ? (i + 1) : (j + 1);
}
}
int main(int argc, char **argv) {
struct tree *T = create_tree();
if(T) {
printf("%s\n", "先序:");
pre_traverse(T);
printf("\n%s\n", "中序:");
mid_traverse(T);
printf("\n%s\n", "后序:");
aft_traverse(T);
printf("\n%s\n", "深度:");
int deepth = tree_deepth(T);
printf("%d\n", deepth);
printf("\n");
}
return 0;
}
posted on 2012-04-09 17:19
一凡 阅读(299)
评论(0) 编辑 收藏 所属分类:
数据结构&算法