как сделать двоичное дерево из обходов по предзаказу и по предзаказу

Question

Вот полный вопрос:

Напишите функцию, которая получает два массива длины n. Первый массив - это PreOrder некоторого двоичного дерева, а второй массив - это InOrder двоичного дерева. Функции выводят двоичное дерево.

// the function recovers the tree from its inorder and preorder
BTnode_t* reconstruct_tree( int * preorder, int * inorder, int n)

с учетом структуры и функций:

struct BTnode {
   int value;
   struct BTnode* left;
   struct BTnode* right;
   struct BTnode* parent;
};
typedef struct BTnode BTnode_t;

BTnode_t* create_node(int val) {
    BTnode_t* newNode = (BTnode_t*) malloc(sizeof(BTnode_t));
    newNode->value = val;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->parent = NULL;

    return newNode;
}

Моя реализация того, как решить эту проблему, в настоящее время не работает, и я думаю, что моя ошибкав том, как я отправляю индексы на моем рекурсивном шаге.

#include <stdio.h>
#include <stdlib.h>


#include "assignment4.h"

int search(int arr[], int strt, int end, int value);

int search(int arr[], int strt, int end, int value) 
{ 
    int i; 
    for (i = strt; i <= end; i++) { 
        if (arr[i] == value) 
            return i; 
    } 
} 

// the function recovers the tree from its inorder and preorder
BTnode_t* reconstruct_tree(int* preorder, int* inorder, int n) {
  // implement me
    int preIndex = 0;

  BTnode_t* newnode = create_node(preorder[preIndex]);

  preIndex++;


  if( sizeof(inorder) > n-1)
    return NULL;

  if( sizeof(inorder) == n-1)
    return newnode;

  int inIndex = search( inorder, 0, n - 1, newnode->value);

  newnode->left = reconstruct_tree(preorder, inorder, inIndex -1);
  newnode->right = reconstruct_tree(preorder, inorder + inIndex +1, n-1 );

  return newnode;

}

Код, используемый для проверки этой части задания:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#include "assignment4.h"



bool BT_equal(BTnode_t* t1, BTnode_t* t2) {
  if (t1 == t2)
    return true;
  if ((t1 && !t2) || (!t1 && t2))
    return false;
  return (t1->value == t2->value) && BT_equal(t1->left, t2->left) && BT_equal(t1->right, t2->right);
}

BTnode_t* create_my_tree() {
  BTnode_t* n1 = create_node(1);
  BTnode_t* n2 = create_node(2);
  BTnode_t* n3 = create_node(3);
  BTnode_t* n4 = create_node(4);
  BTnode_t* n5 = create_node(5);
  BTnode_t* n6 = create_node(6);
  BTnode_t* n7 = create_node(7);

  n1->parent = NULL;

  n1->left = n2;
  n2->parent = n1;

  n1->right = n3;
  n3->parent = n1;

  n2->left = n4;
  n4->parent = n2;
  n4->left = NULL;
  n4->right = NULL;

  n2->right = n5;
  n5->parent = n2;
  n5->left = NULL;
  n5->right = NULL;

  n3->left = n6;
  n6->parent = n3;
  n6->left = NULL;
  n6->right = NULL;

  n3->right = n7;
  n7->parent = n3;
  n7->left = NULL;
  n7->right = NULL;

  return n1;
}



bool test_q1() {
  BTnode_t* n1 = create_my_tree();

  int preorder[] = {1,2,4,5,3,6,7};
  int inorder[] = {4,2,5,1,6,3,7};
  BTnode_t* tree = reconstruct_tree(preorder, inorder, 7);

  if (BT_equal(tree, n1))  {
    printf("Q1 - ok\n");
    return true;
  }
  else {
    printf("Q1 - error\n");
    return true;
  }
}

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

Мой вопрос: неправильно ли я выполняю рекурсивный вызов? Я думаю, sizeof () возвращает мне то, что sizeof (int) вернул бы, например, как я должен сделать это правильно? Может ли кто-нибудь, пожалуйста, указать мне в правильном направлении? Или указать на какие-либо вопиющие проблемы?

Заранее спасибо!

важное редактирование

Я все заработал - вот правильный код

BTnode_t* reconstruct_tree(int* preorder, int* inorder, int n) {
  // implement me
    static int preIndex = 0;

  BTnode_t* newnode = create_node(preorder[preIndex]);

  preIndex++;


  if (n<=1){
    return newnode;
  }

  int inIndex = search( inorder, 0, n - 1, newnode->value);

  newnode->left = reconstruct_tree(preorder, inorder, inIndex);
  newnode->right = reconstruct_tree(preorder, inorder + inIndex +1, n - inIndex -1 );

  return newnode;

}

Но я до сих пор не понимаю, почему работает рекурсивный вызов, может кто-нибудь объяснить, как происходит рекурсия