如何通过有序遍历和预排序遍历制作二叉树

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;

}

但是我仍然不明白为什么递归调用有效，有人可以解释一下递归如何发生的。

Answer 1

嗯，首先要说的是，在给定的序列上有一个简单的重映射，它允许您仅基于重映射只会使事情复杂化而无需添加任何有助于解决问题的事实，从而从有序序列构造树。 。因此，我将对问题描述进行以下简化：

• 前置列表是数字0 ... N-1的升序排列。
• 由于预订序列仅一次访问每个节点，因此预订序列号与序列0 ... N-1之间存在双向映射。
• 由于映射是双向的，因此存在一个反向映射，通过将反向映射应用于有序序列的编号，可以获取新的有序序列。这将导致一个新的有序序列映射到同一棵树，因为这两个序列现在是等效的。
• 这可以忘记预购序列，而不是搜索数字，而是搜索集合的最小值。
• 这解决了一个更普遍的问题，但是当有序节点序列的集合与预排序序列的有效预排序兼容时，这是等效的。

预序列的集合并不总是与给定的序列兼容。

证明：在这种情况下，假设从一个有序序列（假设预序列是数字0..N-1的有序集合）构建树，对于作为某个子树根的每个节点，该树的id的最小值应该是子树的根...而minimum + 1应该是其左节点的子树，除非是空的左子树。让我们用以下符号表示这个事实：

                  (n)
                 /   \
[lllllll(n+1)llll]   [rrrrrrrr]

[(n+1)仅在右边的分区，如果左边的分区为空：

  (n)
 /   \
*    [rrrrrrrr(n+1)rrrrrrrrrrr]

因此，如果有序序列具有非空的左子树，并且预排序中的(n+1)元素在序列中的(n)之后，则不可能构建其中预排序序列有效的树。这在您的代码中体现为搜索的项目不存在于左子树中，因为它是非空的。我的解决方案（找到的最小值）总是提供一个带有无效前序树的解决方案，但其中的所有节点都以升序插入，并将它们附加到已经存在的节点中。当该顺序为有效的预购订单时，则两种算法都给出相同的结果。

我将为您提供一种解决方案，该解决方案将探索有序节点的数组，在遇到最小id值（应为子树的根）的点处对其进行分割，然后将算法再次应用于表示该数组的数组左子树和右子树。该算法将创建的节点附加到传递的父节点上，并返回匹配树的根：

build.c

#include <assert.h>
#include <stdlib.h>

#include "node.h"

struct node *build(const unsigned *l, int sz, struct node *parent)
{
    if (sz == 0) return NULL;

    struct node *res = malloc(sizeof *res);
    assert(res != NULL);

    int i, im = -1;
    unsigned m = ~0;
    for (i = 0; i < sz; i++) {
        const unsigned c = l[i];
        if (c < m) {
            m = c;
            im = i;
        }
    }
    assert (im >= 0 && im < sz);

    res->id     = m;
    res->parent = parent;
    res->left   = build(l, im, res);
    res->right  = build(l + im + 1, sz - im - 1, res);

    return res;
}

一种完整的解决方案或此算法，它打印树（重新编号以产生与有效规范顺序相同的有效有序序列，对于同一棵树---允许产生有序/预定数据集的有效序列）在github中给出。