本文實現二叉樹的遞歸創建、遍歷及深度計算。即輸入: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
一凡 閱讀(304)
評論(0) 編輯 收藏 所屬分類:
數據結構&算法