NOJ数据结构015——建立二叉树的二叉链表的存储结构

亦凉 2023-01-16 03:21 132阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]  
本题中无论建立还是遍历二叉树，都用到了递归思想，个人感觉跟广义表的建立有些像。

创建二叉树的时候，若create函数返回类型为void型，则可以写成两种形式，一种用二级指针，另一种不用。

先上用二级指针的：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
        
        char data;
        struct Node *LChild;
        struct Node *RChild;
    }BiTNode, *BiTree; //定义二叉树
    
    void CreateBinTree(BiTree *T); //创建二叉树
    void PreTree(BiTree T);        //遍历并输出二叉树
    
    int main()
    {
        
        BiTree T;
        T = NULL;
        CreateBinTree(&T);
        PreTree(T);
        return 0;
    }
    
    void CreateBinTree(BiTree *T) //此处需用二级指针来传递
    {
          //创建二叉树
        char c;
        c = getchar();
        if (c == ')') {
        
            return;
        }
        if (c != '(' && c != ',' ) {
        
            *T = (BiTree) malloc (sizeof(BiTNode));
            //个人认为使用二级指针的原因
            (*T)->data = c;
            (*T)->LChild = NULL;
            (*T)->RChild = NULL;
            c = getchar();
        }
        if (c == '(') {
        
            (*T)->LChild = (BiTree) malloc (sizeof(BiTNode));
            CreateBinTree(&(*T)->LChild);
            c = getchar();
        }
        if (c == ',') {
        
            (*T)->RChild = (BiTree) malloc (sizeof(BiTNode));
            CreateBinTree(&(*T)->RChild);
        }
    }
    
    void PreTree(BiTree T)
    {
          //遍历并输出二叉树
        if(T == NULL) {
        
            return;
        }
        printf("%c",T->data);
        PreTree(T->LChild);  //递归遍历
        PreTree(T->RChild);
    }

再是不用二级指针的：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
        
        char data;
        struct Node *LChild;
        struct Node *RChild;
    }BiTNode, *BiTree;
    
    void CreateBinTree(BiTree T); //创建二叉树
    void PreTree(BiTree T);        //遍历并输出二叉树
    
    int main()
    {
        
        BiTree T;
        T = (BiTree) malloc (sizeof(BiTNode));
        CreateBinTree(T);
        PreTree(T);
        return 0;
    }
    
    void CreateBinTree(BiTree T)
    {
          //创建二叉树
        T->LChild = NULL;
        T->RChild = NULL;
        char c;
        c = getchar();
        if (c == ')') {
        
            return;
        }
        if (c != '(' && c != ',' ) {
        
            T->data = c;
            c = getchar();
        }
        if (c == '(') {
        
            T->LChild = (BiTree) malloc (sizeof(BiTNode));
            CreateBinTree(T->LChild);
            c = getchar();
        }
        if (c == ',') {
        
            T->RChild = (BiTree) malloc (sizeof(BiTNode));
            CreateBinTree(T->RChild);
        }
    }
    
    void PreTree(BiTree T)
    {
          //遍历并输出二叉树
        if(T == NULL) {
        
            return;
        }
        printf("%c",T->data);
        PreTree(T->LChild);
        PreTree(T->RChild);
    }

个人认为之所以要用二级指针，是因为在create函数开头用了malloc重新分配了内存空间，若是去掉此语句，就不必再使用二级指针。  
当然，还有另一种方法可以不用二级指针，就是将create函数返回值写为bitree，即二叉树类型或其指针类型。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/3b974df83534425fb9121348d1ea1c50.png