递归遍历二叉树--C语言

拼搏现实的明天。 2022-04-03 14:30 164阅读 0赞

之前写了关于二叉树的非递归遍历算法的代码，今天把二叉树的递归遍历算法的代码补上，内容很简单！但是今天也算是写了一会儿代码了～姑且这么认为吧～

代码：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct BiTNode
    {
        
        char data;//二叉树节点数据
        struct BiTNode *lchild;//二叉树节点左子树指针
        struct BiTNode *rchild;//二叉树节点右子树指针
    }BiTNode,*BiTree;//二叉树节点
    
    //二叉树先序遍历
    void PreBiTree(BiTree T)
    {
        
        if(NULL == T)
        {
        
            return;
        }
        printf("%c ",T->data);
        PreBiTree(T->lchild);
        PreBiTree(T->rchild);
    }
    
    //二叉树中序遍历
    void InBiTree(BiTree T)
    {
        
        if(NULL == T)
        {
        
            return;
        }
        InBiTree(T->lchild);
        printf("%c ",T->data);
        InBiTree(T->rchild);
    }
    
    //二叉树后序遍历
    void PostBiTree(BiTree T)
    {
        
        if(NULL == T)
        {
        
            return;
        }
        PostBiTree(T->lchild);
        PostBiTree(T->rchild);
        printf("%c ",T->data);
    }
    
    //创建二叉树
    void CreateBiTree(BiTree *T)
    {
        
        char ch;
        scanf("%c",&ch);
        if('#' == ch)
        {
        
            *T = NULL;
        }
        else
        {
        
            *T = (BiTree)malloc(sizeof(BiTNode));
            (*T)->data = ch;
            CreateBiTree(&((*T)->lchild));
            CreateBiTree(&((*T)->rchild));
        }
    }
    
    int main()
    {
        
        BiTree T = NULL;
        printf("请按照先序遍历的顺序输入要创建的二叉树\n");
        CreateBiTree(&T);
        printf("二叉树的先序遍历：");
        PreBiTree(T);
        printf("\n");
        printf("二叉树的中序遍历：");
        InBiTree(T);
        printf("\n");
        printf("二叉树的后序遍历：");
        PostBiTree(T);
        printf("\n");
        return 0;
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_5_color_FFFFFF_t_70]  
  这次调用创建二叉树的函数采用了对T取地址的方式，而不是之前的直接传入T参数的方式。CreateBiTree函数的入参的形式也相应的改为BiTree*T，这是因为调用的时候传入的是T指针的地址，相当于是指针的指针，所以这里要定义成BiTree*T。之前的代码里定义的是CreateBiTree(BiTree &T)，这是C++的写法，意思是传的是地址，不是值。两种写法的效果一致，但是一个是C语言写法，一个是C++写法，之前没有特别关注这个，但是其实风格还是差别挺大的。以后要多注意这类问题，不能再把C语言的语法和C++的语法弄混了！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaTIwMTRsZWk_size_5_color_FFFFFF_t_70]: /images/20220403/625072e82c104c2cab0919c9c2680427.png