Построение двоичного дерева из заданных ошибок порядка и предварительных порядков

Question

Я делаю двоичное дерево из заданного массива inorder и preorder, и я не знаю, почему он дает неверный результат, хотя он отлично работает для некоторых точек в заданном массиве

#include<iostream> 

using namespace std; 

class Node 
{ 
    public: 
     int i; 
     Node* left; 
     Node* right; 
     bool isThreaded; 
     Node(int j); 
}; 

Node::Node(int j):i(j) 
{ 
    left=NULL; 
    right=NULL; 
} 

void inorder(Node* root) 
{ 
    if(root) 
    { 
     inorder(root->left); 
     cout<<root->i<<" "; 
     inorder(root->right); 
    } 
} 

int findkey(int* a, int l, int r, int key) 
{ 
    for(int i=l; i<r; i++) 
    { 
     if(a[i]==key) 
      return i; 
    } 

    return -1; 
} 

Node* ConstructfromPreorderInorder(int* pre, int n, int* in, int l, int r, int& k) 
{ 
    Node* root=NULL; 

    if(k<n && l<r) 
    { 
     int key=findkey(in, l, r, pre[k]); //Finds the index of current preorder element in inorder array 


     root=new Node(pre[k++]); //Forms the node 

     root->left=ConstructfromPreorderInorder(pre, n, in, 0, key, k); //To find the left subtree we traverse to left of the index of element in inroder array 

     root->right=ConstructfromPreorderInorder(pre, n, in, key+1, r, k); 
     //Similarly we traverse right to form right subtree 
    } 
    return root; 
} 

int main() 
{ 
    int pre[]={1,2,4,5,3,6,7}; 
    int in[]={4,2,5,1,6,3,7}; 

    int n=sizeof(pre)/sizeof(*pre); //Function used to find the no. of elements in an array. In this case elements in preorder array. Both are same so can use any 

    int i=0; 
    Node* root2=ConstructfromPreorderInorder(pre, n, in, 0, n, i); 
    inorder(root2); 
} 

Хотя он работает для половины элементов массива, но после этого дает необычные результаты. Я добавил заявления печати для лучшего просмотра.

Пожалуйста, обратитесь к нему, если это поможет.

Answer 1

Для построения левого поддерева диапазона следует начинать с л вместо 0.

root->left=ConstructfromPreorderInorder(pre, n, in, l, key, k);

вместо

root->left=ConstructfromPreorderInorder(pre, n, in, 0, key, k); 

Answer 2

Ответ на ваш основной вопрос, «Как я могу отладить этот код? ":

• Найти самый простой возможный случай отказа.
• Проверьте части кода отдельно, например findkey.
• Шаг через это в вашем уме.
• Пройдите через него в отладчике.
• Добавить подробные заявления о печати.

Пример последние:

Node* ConstructfromPreorderInorder(int* pre, int n, int* in, int l, int r, 
int& k) 
{ 
cout << "constructing from " << l << " to " << r << " at " << k << endl;