随笔-196  评论-90  文章-8  trackbacks-0
本文实现二叉树的递归创建、遍历及深度计算。即输入: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 *= 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 *= 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 一凡 阅读(223) 评论(0)  编辑  收藏 所属分类: 数据结构&算法

只有注册用户登录后才能发表评论。


网站导航: