二叉树的创建与遍历（递归版本）-阿里云开发者社区

二叉树的创建与遍历（递归版本）

2016-05-19 3841

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

非递归方式实现二叉树的创建与搜索，对于二叉树通常约定以前序遍历方式输入，若输入不正确是不会有什么显示的，这点要注意；

给出了C语言创建链表的俩种方式（不同于C++中引用传递）

一创建二叉树方式：

方式一：输入指针

[cpp]view plain copy 
 
void creatBT(BiTree *T)//建立一个二叉树  
{  
    char ch;  
    scanf("%c",&ch);//读入字符  
    if(ch=='.')//.代表空子树  
        *T = NULL;  
    else  
    {  
        *T = (node *)malloc(sizeof(node));  
        if(!T)  
        {  
            printf("开辟内存失败\n");  
            exit(1);  
        }  
        (*T)->data = ch;//给T赋值  
        creatBT(&(*T)->lchild);//给左子树赋值  
        creatBT(&(*T)->rchild);//给右子树赋值  
    }  
}  

方式二：无参数传入，返回局部函数的指针地址

[cpp]view plain copy 
 
BiTree creatBT()//建立一个二叉树  
{  
    BiTree T;  
    char ch;  
    scanf("%c",&ch);//读入字符  
    if(ch=='.')//.代表空子树  
        T = NULL;  
    else  
    {  
        T = (node *)malloc(sizeof(node));  
        if(!T)  
        {  
            printf("开辟内存失败\n");  
            exit(1);  
        }  
        T->data = ch;//给T赋值  
        T->lchild = creatBT();//给左子树赋值  
        T->rchild = creatBT();//给右子树赋值  
    }  
    return T;  
}  

二遍历代码（采取方式一的创建方式）

[cpp]view plain copy 
 
#include <stdio.h>  
#include <stdlib.h>  
//定义二叉树的数据结构(递归方式)  
typedef struct node  
{  
    char data;  
    struct node *lchild;  
    struct node *rchild;  
}node ,*BiTree;  
void creatBT(BiTree *T)//建立一个二叉树  
{  
    char ch;  
    scanf("%c",&ch);//读入字符  
    if(ch=='.')//.代表空子树  
        *T = NULL;  
    else  
    {  
        *T = (node *)malloc(sizeof(node));  
        if(!T)  
        {  
            printf("开辟内存失败\n");  
            exit(1);  
        }  
        (*T)->data = ch;//给T赋值  
        creatBT(&(*T)->lchild);//给左子树赋值  
        creatBT(&(*T)->rchild);//给右子树赋值  
    }  
}  
void pre_order(node *T)//前序遍历二叉树  
{  
    if(T)  
    {  
        printf("%c ",T->data);  
        pre_order(T->lchild);  
        pre_order(T->rchild);  
    }  
  
}  
void mid_order(node *T)//中序遍历  
{  
    if(T)  
    {  
        mid_order(T->lchild);  
        printf("%c ",T->data);  
        mid_order(T->rchild);  
    }  
  
}  
void back_order(node *T)  
{  
    if(T)  
    {  
        back_order(T->lchild);  
        back_order(T->rchild);  
        printf("%c ",T->data);  
    }  
  
}  
int main()  
{  
    BiTree T = NULL;  
    printf("请使用前序遍历的方式输入字符串，用.代替空值\n");  
    creatBT(&T);//建立二叉树  
    printf("建树成功\n");  
    printf("\n前序遍历的结果是：\n");  
  
    pre_order(T);  
    printf("\n中序遍历的结果是：\n");  
    mid_order(T);  
    printf("\n后序遍历的结果是：\n");  
    back_order(T);  
    printf("\n");  
    system("pause");  
    return 0;  
}  

若要采取方式二的创建方式main函数对应修改为

[cpp]view plain copy 
 
int main()  
{  
    BiTree T = NULL;  
    printf("请使用前序遍历的方式输入字符串，用.代替空值\n");  
    T = creatBT();//建立二叉树  
    printf("建树成功\n");  
    printf("\n前序遍历的结果是：\n");  
  
    pre_order(T);  
    printf("\n中序遍历的结果是：\n");  
    mid_order(T);  
    printf("\n后序遍历的结果是：\n");  
    back_order(T);  
    printf("\n");  
    system("pause");  
    return 0;  
}  

结果一样的

小结：采用有参传入的时候由于在局部函数执行完后变量都会被释放，因此需要传入BiTree的指针，因而比较复杂，建议使用无参书传入，返回头节点，代码比较简洁容易理解

转载：http://blog.csdn.net/xsf50717/article/details/40019023

二叉树的创建与遍历（递归版本）

热门文章

最新文章

相关电子书