给定非空二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根...

申谭

#include <iostream>
#include <cstring>
#include<math.h>
using namespace std;

struct node {
    char data;
    node* left;
    node* right;
};

typedef node* tree;

int find_(char* inorder, int size, char data) {
    for (int i = 0; i < size; i++) {
        if (inorder[i] == data)
            return i;
    }
    return -1;
}

node* buildtree(char* postorder, char* inorder, int n) {
    if (n <= 0)
        return NULL;
    char tdata = postorder[n - 1];
    int k = find_(inorder, n, tdata);
    if(k==-1)
    {
        return NULL;
    }
    node* root = new node;
    root->data = tdata;
    root->left = buildtree(&postorder[0], &inorder[0], k);
    root->right = buildtree(&postorder[k], &inorder[k+1], n - k - 1);
    return root;
}

int get_height(tree t) {
    if (t == NULL)
        return -1;
   
    int d1 = get_height(t->left);
    int d2 = get_height(t->right);
    return max(d1, d2) + 1;
}

void Preorder(tree t) {
    if (t == NULL)
        return;
   
    cout << t->data;
    Preorder(t->left);
    Preorder(t->right);
}

int main() {
    char postorder[10000];
    char inorder[10000];
    while (scanf("%s", postorder) != EOF && scanf("%s", inorder) != EOF) {
        int n = strlen(inorder);
        tree root = buildtree(postorder, inorder, n);
        int height = get_height(root);
        if(root==NULL) cout<<"INVALID"<<endl;
        else
        {
        cout << height << endl;
        Preorder(root);
        cout << endl;
        }
    }
    return 0;
}感觉在递归的时候如果k==-1就要返回上一级而不是直接结束函数，导致一些不合法的输入，还会输出一些字符，该如何修改

isdkz

你需要在递归的时候，当  k==-1  时返回上一级，而不是直接结束函数。这样可以避免输出一些不合法的字符。你可以修改  buildtree  函数中的条件判断，如下所示：

node* buildtree(char* postorder, char* inorder, int n) {
    if (n <= 0) 
        return NULL;
    char tdata = postorder[n - 1];
    int k = find_(inorder, n, tdata); 
    if(k==-1)
    {
        return NULL;
    }
    node* root = new node;
    root->data = tdata;
    root->left = buildtree(&postorder[0], &inorder[0], k);
    if(root->left == NULL) // 如果左子树为空，返回上一级
    {
        delete root;
        return NULL;
    }
    root->right = buildtree(&postorder[k], &inorder[k+1], n - k - 1);
    if(root->right == NULL) // 如果右子树为空，返回上一级
    {
        delete root;
        return NULL;
    }
    return root;
}

通过在递归的过程中加入对左右子树是否为空的判断，可以避免输出不合法的字符。

Mike_python小

在当前的代码中，当 k == -1 时，会直接返回 NULL，导致递归函数结束。为了在遇到不合法的输入时返回上一级，你可以在递归函数中添加一个判断条件，如果 k == -1 则返回上一级。

以下是修改后的代码片段：

node* buildtree(char* postorder, char* inorder, int n) {    if (n <= 0)         return NULL;        char tdata = postorder[n - 1];    int k = find_(inorder, n, tdata);     if(k == -1) {        return NULL;    }        node* root = new node;    root->data = tdata;    root->left = buildtree(&postorder[0], &inorder[0], k);    if (root->left == NULL) {        // 非法输入，返回上一级        delete root;        return NULL;    }    root->right = buildtree(&postorder[k], &inorder[k+1], n - k - 1);    if (root->right == NULL) {        // 非法输入，返回上一级        delete root->left;        delete root;        return NULL;    }        return root;}

请注意，当发现左子树或右子树为空时，我们将删除已创建的节点并返回 NULL，以确保整个树的结构正确。

希望这可以解决你的问题。如果还有其他疑问，请随时提问。

申谭

Mike_python小 发表于 2023-11-20 19:25
在当前的代码中，当 k == -1 时，会直接返回 NULL，导致递归函数结束。为了在遇到不合法的输入时返回上一级 ...

但是走到左分支左后不是一定要指向NULL
CBEDFAGH
CEFDBHGA
我说的错误是类似于这种然后输出INVALID
现在代码输出2
HFDGA

LazyBreeze

申谭 发表于 2023-11-20 19:44
但是走到左分支左后不是一定要指向NULL
CBEDFAGH
CEFDBHGA

我也在思考这个问题，楼主有想法了吗，抛掷异常更容易出现问题