9147 分段错误：11 从中序和前序遍历构造二叉树

Question

给定二叉树的中序和先序遍历，构造二叉树。

在从中序遍历和先序遍历构建树时，我认为我已经正确地编写了它，但为什么它给出了分段错误。请帮忙。下面是我的代码：

#include<bits/stdc++.h>
using namespace std;

class Node {
 public :
 int data;
 Node* left;
 Node* right;

 Node(int data)
 {
    this->data = data;
    left = right = NULL;
 }
};

void Inorder(Node* root)
{
  if (root == NULL)
  {
    return;
  }

  Inorder(root->left);
  cout << root->data << " ";
  Inorder(root->right);
}

 Node* buildTreeHelper( int inorder[], int preorder[], int InS, int InE, int PreS, int PreE)
 {

  if (InS > InE)
  {
     return NULL;
  }

 int rootData = preorder[PreS];

 int lIns = InS;
 int rootIndex = -1;
 for (int i = InS ; i < InE ; i++)
  {
     if (inorder[i] == rootData)
       {
         rootIndex = i;
         break;
       }
  }
    int lIne = rootIndex - 1;
    int lPres = PreS + 1;
    int lPree = lIne - lIns + lPres;
    int rIns = rootIndex + 1;
    int rIne = InE;
    int rPres = lPree  + 1;
    int rPree = PreE;


   Node* root = new Node(rootData);
   root->left = buildTreeHelper(inorder, preorder, lIns, lIne, lPres, lPree);
   root->right = buildTreeHelper(inorder, preorder, rIns, rIne, rPres, rPree);

    return root;
}

Node* buildTree(int inorder[], int preorder[], int size)
{
    return buildTreeHelper(inorder, preorder, 0, size - 1, 0, size - 1);
}
int main()
{

    int inorder[] = {4, 2, 5, 1, 8, 6, 9, 3, 7};
    int preorder[] = {1, 2, 4, 5, 3, 6, 8, 9, 7};

   Node* root = buildTree(inorder, preorder, 9);
    Inorder(root);
    delete root;
    return 0;
}

我无法确定是什么错误，请帮我解决这个问题。

Answer 1

在我看来，至少你的一个问题是在循环中找到 in-order 数据列表中的根索引，你实际上并没有检查最后一个元素（即它应该是 i <= InE.)

此外，我不能说你的 lPree 计算是正确的，因为你选择的名字太无用了，我什至不想读那一行。

并且，请不要使用 #include <bits/stdc++.h>。我不知道是哪个 compiler/IDE 鼓励使用这个特定的 header，但我在其他（初学者）人的代码中看到过它，在我看来，这不好。请只使用标准 headers。在这种情况下，那将是 iostream（可能会加上 using std::cout;。）

顺便说一句，在程序结束时，您只释放了单个根节点。这显然是不充分和不正确的。您必须遍历并释放整棵树（您可以从 Node 析构函数中执行此操作，但我不建议在析构函数中进行递归调用。在这个简单的程序中您可能没问题。）

9147 分段错误：11 从中序和前序遍历构造二叉树

9147 Segmentation Fault : 11 Construct Binary tree from inorder and preorder traversals

c++

binary-tree

segmentation-fault