关于#数据结构#的问题，请各位专家解答！（相关搜索：二叉树|二叉树遍历）

Question

二叉树遍历在键入树的数据时程序出不去了，求解答。

#define  _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#define false 0
#define true 1
using namespace std;

typedef struct BTnode {
    char data;  //节点的数据域
    struct BTnode* lchild, * rchild; //左右子指针
}*BTree, BTnode;

//先序创建二叉树
void CreateBTree(BTree& T) {// 可执行输入操作！
    char str;
    cin >> str;
    if (str == '#') T = NULL;//出现 # ，递归终止条件
    else {
        
        T = new BTnode; //申请一个根结点
        T->data = str; //将根结点赋值为str
        CreateBTree(T->lchild);  //递归创建左子树
        CreateBTree(T->rchild); //递归创建右子树 
    }
}

inline bool visit(int e) {   //使用内敛函数，提高运行效率 
    printf("%d", e);
    return true;
}
//先序遍历
void Order(BTree T) {
    if (T) {
        visit(T->data);  //先遍历数据
        Order(T->lchild);//再遍历左子树
        Order(T->rchild);//最后遍历右子树
    }
}
//中序遍历
void InOrder(BTree T) {
    if (T) {
        InOrder(T->lchild);//先遍历左子树
        visit(T->data);    //再遍历数据
        InOrder(T->rchild);//最后遍历右子树
    }
}
//后续遍历
void PostOrder(BTree T) {
    if (T) {
        PostOrder(T->lchild);//先遍历左子树
        PostOrder(T->rchild);//再遍历右子树
        visit(T->data);      //最后遍历数据
    }
}
 
 //树的深度
 int Depth(BTree T) {
     int H, L, R;
     if (T == NULL) {
         return 0;
     }
     else {
         L = Depth(T->lchild) + 1;
         R = Depth(T->rchild) + 1;
         H = (L > R ? L : R);
         return H;

     }
 }
 //统计二叉树中结点的个数
 int NodeCount(BTree T) {
     if (T) {
         return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
     }
     else return 0;
 }
 //统计二叉树叶子节点的个数
 int NodesCount(BTree T) {
     int L, R;
     if (T == NULL) { return 0; }
     if ((T->lchild == NULL) && (T->rchild == NULL)) {
         return 1;
     }
     L = NodesCount(T->lchild);
     R = NodesCount(T->rchild);
     return (L + R);
 }
 //树状打印    
 int show(BTree T, int h) {
     if (T == NULL)  return 0;
     show(T->rchild, h + 2);
     for (int i = 1; i <= h; i++) {
         printf("0");
     }
     printf("%d\n", T->data);
     show(T->lchild, h + 2);
 }

 void interface() {
     printf("    [先序遍历输出]请输入1\n    [中序遍历输出]请输入2\n    [后序遍历输出]请输入3\n    [查询树的深度]请输入4\n    [查询树的结点个数]请输入5\n    [查询树的叶子结点个数]请输入6\n    [横向打印树]请输入7\n    [退出]请输入8\n");
 }

 int main() {
     BTree T; //构建一个树
     string c;  //操作选择：1-2-3-4-5-6-7-8
     int Count, Counts, Counts_1;

     //界面优化
     int n = 0;
     printf("——Welcome to our linear list——\n");
     printf("【正在创建中】-请输入创建结点总个数：");
     scanf("%d", &n);

     printf("请输入树的各元素：\n");
     CreateBTree(T);//调用一个创建好的树
    
     printf("--请选择:");
     interface();  //界面优化函数
     cin >> c;

     do {
         //错误输入提示，可重新输入
         if (c != "1" && c != "2" && c != "3" && c != "4" && c != "5" && c != "6" && c != "7" && c != "8") {
             printf("[warning]WRONG input,please enter again:");
             cin >> c;
         }

         // 按序号操作
         else if (c == "1") {
             printf("\n先序遍历输出:");
             Order(T);
         }
         else if (c == "2") {
             printf("\n中序遍历输出:");
             InOrder(T);
         }
         else if (c == "3") {
             printf("\n后序遍历输出:");
             PostOrder(T);
         }
         else if (c == "4") {
             int d = Depth(T);
             printf("\n树的深度为：%d", d);
         }
         else if (c == "5") {
             Count = NodesCount(T);
             printf("\n树的结点个数为：%d", Count);
         }
         else if (c == "6") {
             Counts = NodesCount(T);
             printf("\n树的叶子结点个数为：%d", Counts);
         }
         else if (c == "7") {
             printf("\n树的横向打印:\n");
             show(T, 1);
         }
         else if (c == "8") break;
         printf("\n———--please enter your choice again:");
         cin >> c;
     } while (c == "1" || c == "2" || c == "3" || c == "4" || c == "5" || c == "6" || c == "7" || c == "8");
     return 0;
 }

Answer 1

引自免费微信小程序：皆我百晓生

问题：在键入树的数据时程序出不去了。

解决方案： 根据你提供的代码，问题出现在CreateBTree函数中。我看到你在CreateBTree函数中使用了递归来创建二叉树，但是你在每次递归调用CreateBTree函数时没有传入参数的引用。这导致程序无法正确地递归地创建二叉树。

以下是修复后的代码：

void CreateBTree(BTree& T) {// 可执行输入操作！
    char str;
    cin >> str;
    if (str == '#') T = NULL;
    else {

        T = new BTnode;
        T->data = str;
        CreateBTree(T->lchild);
        CreateBTree(T->rchild);
    }
}

你可以将上述修复后的代码替换到原来的代码中进行尝试，应该可以解决程序无法退出的问题。

另外，在你的代码中，InOrder和PostOrder函数中的顺序是有问题的。在中序遍历中，应先遍历左子树再遍历右子树，而不是相反。在后序遍历中，也是先遍历左子树再遍历右子树。你需要将这两个函数中的顺序进行修正。

关于二叉树的遍历，在你的代码中已经实现了三种遍历方式，即先序遍历、中序遍历和后序遍历。你可以根据需要调用相应的函数来实现遍历操作。

希望能帮助到你！如果你还有其他问题，请随时提问。