二叉树的应用-链式存储结构基本操作

Question

有无佬看看是哪里写错了，为什么我尝试输出二叉树输出不了呢

#ifndef COM_H
#define COM_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MaxSize 50

typedef char elemtype;

typedef struct node
{
    elemtype data;
    struct node  *left;
    struct node  *right;
}BTNode;

void CreateBTree(BTNode * b,char * str)
{
    BTNode * St[MaxSize],*p;
    int top = -1,k,j=0;
    char ch;
    b = NULL;
    ch = str[j];
    while(ch!='\0')
    {
        switch (ch)
        {
        case '(':
            top++;
            St[top] = p;
            k=1;
            break;
        case ')':
            top--;
            break;
        case ',':
            k=2;
            break;
        default:
            p=(BTNode *)malloc(sizeof(BTNode));
            p->data=ch;
            p->left=p->right=NULL;
            if(b==NULL)
                b=p;
            else
            {
                switch (k) {
                case 1:
                    St[top]->left=p;
                    break;
                case 2:
                    St[top]->right=p;
                    break;
                }
            }
        }
        j++;
        ch=str[j];
    }
}


void DestroyBTree(BTNode*b)
{
    if(b!=NULL)
    {
        DestroyBTree(b->left);
        DestroyBTree(b->right);
        free(b);
    }
}

BTNode *FindNode(BTNode*b,elemtype x)
{
    BTNode * p;
    if(b==NULL)
        return NULL;
    else if(b->data==x)
        return b;
    else
    {
        p=FindNode(b->left,x);
        if(p!=NULL)
            return p;
        else
            return FindNode(b->right,x);
    }
}

BTNode *LchildNode(BTNode * p)
{
    return p->left;
}

BTNode *RchildNode(BTNode * p)
{
    return p->right;
}

int BTHeight(BTNode *b)
{
    int left,right;
    if(b==NULL)
        return(0);
    else
    {
        left = BTHeight(b->left);
        right = BTHeight(b->right);
        return (left>right)?(left+1):(right+1);
    }
}

void DispBTree(BTNode *b)
{
    if(b!=NULL)
    {
        printf("%c",b->data);
        if(b->left!=NULL||b->right!=NULL)
        {
            printf("(");
            DispBTree(b->left);
            if(b->right!=NULL)
                printf(",");
            DispBTree(b->right);
            printf(")");
        }
    }
}

void PreOrder(BTNode *b)
{
    if(b!=NULL)
    {
        printf("%c",b->data);
        PreOrder(b->left);
        PreOrder(b->right);
    }
}

void InOreder(BTNode *b)
{
    if(b!=NULL)
    {
        InOreder(b->left);
        printf("%c",b->data);
        InOreder(b->right);
    }
}

void PostOrder(BTNode *b)
{
    if(b!=NULL)
    {
        PostOrder(b->left);
        PostOrder(b->right);
        printf("%c",b->data);
    }
}

#endif

Answer 1

根据提供的代码和问题描述，可以看出问题可能在于 CreateBTree() 函数，函数的参数为指向根节点的指针，但是在函数中将指针重新赋值为NULL，导致函数结束后根节点指针并没有被正确修改。因此，需要将函数参数改为指向指针的指针，以确保函数中对指针的修改能够正确传出。

修改后的代码如下：

#ifndef COM_H
#define COM_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MaxSize 50

typedef char elemtype;

typedef struct node
{
    elemtype data;
    struct node  *left;
    struct node  *right;
}BTNode;

void CreateBTree(BTNode ** b,char * str)
{
    BTNode * St[MaxSize],*p;
    int top = -1,k,j=0;
    char ch;
    (*b) = NULL; // 修改根节点指针的值，需要使用指针的指针
    ch = str[j];
    while(ch!='\0')
    {
        switch (ch)
        {
        case '(':
            top++;
            St[top] = p;
            k=1;
            break;
        case ')':
            top--;
            break;
        case ',':
            k=2;
            break;
        default:
            p=(BTNode *)malloc(sizeof(BTNode));
            p->data=ch;
            p->left=p->right=NULL;
            if((*b)==NULL)
                (*b)=p; // 修改根节点指针的值，需要使用指针的指针
            else
            {
                switch (k) {
                case 1:
                    St[top]->left=p;
                    break;
                case 2:
                    St[top]->right=p;
                    break;
                }
            }
        }
        j++;
        ch=str[j];
    }
}


void DestroyBTree(BTNode*b)
{
    if(b!=NULL)
    {
        DestroyBTree(b->left);
        DestroyBTree(b->right);
        free(b);
    }
}

BTNode *FindNode(BTNode*b,elemtype x)
{
    BTNode * p;
    if(b==NULL)
        return NULL;
    else if(b->data==x)
        return b;
    else
    {
        p=FindNode(b->left,x);
        if(p!=NULL)
            return p;
        else
            return FindNode(b->right,x);
    }
}

BTNode *LchildNode(BTNode * p)
{
    return p->left;
}

BTNode *RchildNode(BTNode * p)
{
    return p->right;
}

int BTHeight(BTNode *b)
{
    int left,right;
    if(b==NULL)
        return(0);
    else
    {
        left = BTHeight(b->left);
        right = BTHeight(b->right);
        return (left>right)?(left+1):(right+1);
    }
}

void DispBTree(BTNode *b)
{
    if(b!=NULL)
    {
        printf("%c",b->data);
        if(b->left!=NULL||b->right!=NULL)
        {
            printf("(");
            DispBTree(b->left);
            if(b->right!=NULL)
                printf(",");
            DispBTree(b->right);
            printf(")");
        }
    }
}

void PreOrder(BTNode *b)
{
    if(b!=NULL)
    {
        printf("%c",b->data);
        PreOrder(b->left);
        PreOrder(b->right);
    }
}

void InOreder(BTNode *b)
{
    if(b!=NULL)
    {
        InOreder(b->left);
        printf("%c",b->data);
        InOreder(b->right);
    }
}

void PostOrder(BTNode *b)
{
    if(b!=NULL)
    {
        PostOrder(b->left);
        PostOrder(b->right);
        printf("%c",b->data);
    }
}

#endif