如何从中序和先序遍历制作二叉树

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;
  }
}

我理解算法 visually.I 已经考虑了很长时间，我认为我发送的索引是正确的。

我的问题：我是否错误地进行了递归调用？我认为 sizeof() return 告诉我 sizeof(int) 会 return 例如，我应该如何正确地做到这一点？谁能指出我正确的方向？或者指出任何明显的问题？

提前致谢！

重要编辑

我成功了 - 这是正确的代码

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 的有序集合）在这种情况下，对于作为某些树根的每个节点子树，该树的 ids 中的最小值应该是子树的根...最小值+1 应该是其左节点的子树，除非左子树为空。让我们用以下符号表示这个事实：

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

和(n+1)将仅在右侧分区，以防左侧分区为空：

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

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

我会给你一个探索中序节点数组的解决方案，在它遇到最小 id 值（应该是子树的根）的点划分它并再次应用算法到表示左子树和右子树的数组。该算法将创建的节点附加到传递的父节点，并且returns匹配树的根：

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;
}

一个完整的解决方案或这个算法，它打印树（重新编号以产生与有效规范预序相匹配的有效有序序列，对于同一棵树---允许产生[=的有效序列48=] 数据集）在 github.

中给出

如何从中序和先序遍历制作二叉树

how to make Binary Tree from inorder and preorder traversals

c

binary-tree

traversal

tree-traversal

build.c