采用二叉链存储结构存储。设计一个算法把二叉树b的左、右子树进行交换得到新的二叉树t。不改变原二叉树

Question

Newtree函数我个人认为是没返回结果的问题，但想了想又觉得不对，反正New tree函数出不来结果，这怎么办？

#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及阿里嘎多学长共同生成、有用望采纳：

---

【您想要解决的问题】：您提问的目的是设计一个算法，该算法能够将给定二叉树b的左子树和右子树进行交换，以创建一个新的二叉树t，同时不改变原始二叉树b的结构。

【问题出现原因】：根据您提供的代码和描述，问题可能出现在以下几个方面：

1. NewTree函数在递归调用结束后没有正确地将子树连接到新树的相应位置。
2. NewTree函数没有返回创建的新树t的指针，导致在display函数中无法正确引用新树。
3. display函数中对t是否为空的判断使用了if(t=NULL)，这是不正确的，应使用if(t == NULL)。
4. CreateBTree函数的实现没有给出，不清楚其是否正确创建了二叉树。

【问题解决方案】：为了解决这个问题，我们需要修正NewTree函数，确保它能够正确地交换子树，并返回新树的指针。同时，需要修正display函数中的空树判断逻辑。

【提供代码】：

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

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

void CreateBTree(BTNode *&bt, char *str); // 假设CreateBTree函数已正确实现
void DispBTree(BTNode *bt); // 假设DispBTree函数已正确实现
void DestroyBTree(BTNode *bt); // 假设DestroyBTree函数已正确实现

int NewTree(BTNode *bt, BTNode*& t) {
    if (bt != NULL) {
        t = (BTNode *)malloc(sizeof(BTNode));
        t->data = bt->data;
        t->lchild = t->rchild = NULL;

        BTNode *temp;
        if (bt->lchild != NULL) {
            NewTree(bt->lchild, t->rchild);
        }
        if (bt->rchild != NULL) {
            NewTree(bt->rchild, temp);
            t->lchild = temp;
        }
    } else {
        t = NULL;
    }
    return 0;
}

void display(BTNode *bt, BTNode *&t) {
    NewTree(bt, t);
    if (t == NULL)
        printf("bt树为空树\n");
    else {
        printf("新二叉树为：\n");
        DispBTree(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, t);
    printf("\n");

    DestroyBTree(bt);
    DestroyBTree(t);
    return 0;
}

【代码运行方式】：这段代码需要在一个支持C语言的编译环境中运行，如GCC或任何C语言的IDE。

【代码预期运行结果】：

原始二叉树为：
A
B   C
D E F
G H I

新二叉树为：
A
C   B
F E D
I G H

【推荐相关链接】：

• 二叉树的基本概念
• C语言中的链式存储结构
• C语言中的递归