申谭 发表于 2023-11-20 19:23:36

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

#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 == data)
            return i;
    }
    return -1;
}

node* buildtree(char* postorder, char* inorder, int n) {
    if (n <= 0)
      return NULL;
    char tdata = postorder;
    int k = find_(inorder, n, tdata);
    if(k==-1)
    {
      return NULL;
    }
    node* root = new node;
    root->data = tdata;
    root->left = buildtree(&postorder, &inorder, k);
    root->right = buildtree(&postorder, &inorder, 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;
    char inorder;
    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 发表于 2023-11-20 19:23:50

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

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


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

Mike_python小 发表于 2023-11-20 19:25:18

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

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


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


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

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

申谭 发表于 2023-11-20 19:44:19

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

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

LazyBreeze 发表于 2023-12-14 20:29:25

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


我也在思考这个问题，楼主有想法了吗，抛掷异常更容易出现问题
页: [1]
查看完整版本: 给定非空二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根...