二叉链，左右子树交换，New tree函数不返回结果

Question

问题：采用二叉链存储结构存储。设计一个算法把二叉树b的左、右子树进行交换得到新的二叉树t。一到display函数就不出结果，我个人认为是Newtree函数出来问题。

#include "BTree.cpp" 
int NewTree(BTNode *bt,BTNode*&t )
{
    if(bt!=NULL)
    {     t=(BTNode *)malloc(sizeof(BTNode));
          bt->data=t->data;
          if(bt->lchild!=NULL)
          NewTree(bt->lchild,t->rchild);
          else if(bt->rchild!=NULL)
          NewTree(bt->rchild,t->lchild);
      }
    else t=NULL;
}
void display(BTNode*bt,BTNode *&t)
{    NewTree(bt,t);
    if(t=NULL)
      printf("bt树为空树");
    else 
      {printf("新二叉树为：");
      DispBTree(t);}
}
int main()
{  BTNode *bt,*t,*bt1;
    CreateBTree(bt,"A(B(D,E(G,H)),C(,F(I)))");
    printf("bt:");
    DispBTree(bt);
    printf("good");
    printf("\n");
    display(bt,t);
    printf("good2");
    DestroyBTree(bt);
    CreateBTree(bt1," ");
    display(bt1,t);
    printf("good3");
    DestroyBTree(bt1);
    DestroyBTree(t);
}

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

问题概括

您提问的目的是解决在C语言中使用二叉树数据结构时，通过NewTree函数交换二叉树的左右子树后，display函数无法正确显示结果的问题。

问题出现原因

1. NewTree函数的设计问题：在NewTree函数中，您试图通过递归调用自身来交换左右子树，但是没有正确地处理空节点和子树的连接。
2. display函数中的条件判断错误：您使用了if(t=NULL)，这是不正确的，应该是if(t == NULL)。
3. 内存分配问题：在NewTree函数中，如果bt为NULL，则t被设置为NULL，这将导致无法正确构建新的二叉树。

问题解决方案

为了解决这个问题，需要对NewTree函数进行重构，确保左右子树能够正确交换，并且新树能够正确构建。同时，修正display函数中的条件判断。

提供代码

以下是修改后的代码示例：

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

typedef struct BTNode {
    char data;
    struct BTNode *lchild, *rchild;
} BTNode;

void CreateBTree(BTNode **bt, char *str);
void DispBTree(BTNode *bt);
void DestroyBTree(BTNode *bt);

BTNode* NewTree(BTNode *bt) {
    BTNode *t = NULL;
    if (bt != NULL) {
        t = (BTNode *)malloc(sizeof(BTNode));
        t->data = bt->data;
        NewTree(bt->rchild); // 先递归右子树
        t->lchild = NewTree(bt->lchild); // 然后递归左子树
    } else {
        return NULL;
    }
    return t;
}

void display(BTNode *bt) {
    BTNode *t = NewTree(bt);
    if (t == NULL) {
        printf("bt树为空树\n");
    } else {
        printf("新二叉树为：\n");
        DispBTree(t);
    }
    DestroyBTree(t); // 释放新树的内存
}

int main() {
    BTNode *bt, *t;
    CreateBTree(&bt, "A(B(D,E(G,H)),C(,F(I)))");
    printf("原始二叉树为：\n");
    DispBTree(bt);
    printf("\n");
    display(bt);
    printf("\n");
    DestroyBTree(bt);
    return 0;
}

代码运行方式

您需要一个C语言的编译器，如GCC，来编译和运行上述代码。在命令行中，您可以使用以下命令：

gcc -o program program.c
./program

代码预期运行结果

如果代码正确编译并运行，您将看到原始二叉树的显示，然后是交换左右子树后的新二叉树的显示。

推荐相关链接

• C语言二叉树数据结构
• C语言内存分配
• C语言递归函数

请注意，上述代码仅为示例，您可能需要根据您的实际代码结构和函数实现进行调整。