c语言-数据结构-二叉树-生成、遍历代码

古城微笑少年丶 2022-09-26 02:27 193阅读 0赞

**1. 目标**

生成一个二叉树，遍历输出二叉树中的内容，并显示所在的层级。

**2. 运行示例**

输入如下图二叉树（前序遍历方式），不存在的子节点用空格代替。显示如下。

![Image 1][]![Center][]

![Center 1][]

**3. 源代码**

需要的注意的是，这里利用递归的方式动态分配内存，需要用指向指针的指针（也可以利用返回指针的方式）才能工作。

#include<stdio.h>
    #define title "------------------------------Life is a fight!------------------------------------"
    
    typedef char Eletype;
    
    typedef struct BitNode{
        struct BitNode *lt;//指向左节点
        Eletype data;//根节点的数据
        struct BitNode *rt;//指向右节点
    } BitNode, *BitPtr;
    
    /*按前序遍历方式生成二叉树
    * 无子节点则用空格代替
    */
    void CrtBit(BitPtr *pptr)//这里由于需要对指针的地址进行操作(用malloc),所以需要用指针的指针作为形参
    {
        char c;
        scanf("%c",&c);
        if(' '==c)
        {
            *pptr=NULL;
        }
        else
        {
            *pptr=(BitPtr)malloc(sizeof(BitNode));
            (*pptr)->data=c;
            CrtBit(&(*pptr)->lt);//注意参数是指针的指针
            CrtBit(&(*pptr)->rt);
        }
    }
    
    /*打印一个节点的数据*/
    void VisitBit(Eletype c, int level)
    {
        printf("%d: %c\n",level, c);
    }
    
    /*遍历节点*/
    void TslBit(BitPtr ptr, int level)
    {
        if(ptr)
        {
            VisitBit(ptr->data, level);
            TslBit(ptr->lt, level+1);
            TslBit(ptr->rt, level+1);
        }
    }
    
    int main(void)
    {
        BitPtr ptr;
        int level=1;
    
        printf("%s\n\n",title);
        printf("Please enter the data:\n");
        CrtBit(&ptr);
        TslBit(ptr, level);
        return 0;
    }

[Image 1]: 
[Center]: /images/20220717/9dc50461993f4a9b9224fed064f30bcd.png
[Center 1]: /images/20220717/a5ad936a09214da0bb41884bb5d21cf5.png