使用递归策略将数组转换为二叉树

Question

我需要从包含一些零的向量开始创建二叉树，其中零表示不存在的节点。例如，如果我得到：

int a[] = {10,4,7,2,3,-1,8,9,-1,2,4,5};

我希望我的输出是这样的：

         10
        /   \
       4     7
      / \     \
     2   3     8
    /   / \   /
   9   2   4 5

我的结构：

  typedef struct node {
   int n;
   struct node * dx;
   struct node * sx;
  } *Bit_node;

搭建一个节点的方法：

  Bit_node bit_new(int n) {
    Bit_node new_node = malloc(sizeof(struct node));
    new_node -> n = n;
    return new_node;
  }

构建整棵树的方法：

  Bit_node bit_arr2tree(int a[], int size, int i) {
  if (i>= size) {
      return NULL;
  }
  if(a[i] != -1) {
   Bit_node new_node = bit_new(a[i]);
   new_node -> sx = bit_arr2tree(a, size, i*2 +1);
   new_node -> dx = bit_arr2tree(a, size, i*2 +2);
  }
  
  return new_node;
}

但是在我的实现中，我的树是在没有考虑“漏洞”的情况下构建的。有没有办法考虑它们，保持递归策略？

Answer 1

首先，int a[] = {10,4,7,2,3,-1,8,9,-1,2,4,5}; 不应该产生你期望的树，5 是 8 的左边 child。因为 8 在索引 6，它的左边 child将位于索引 6 * 2 + 1 == 13。所以你的输入可能应该是 int a[] = {10,4,7,2,3,-1,8,9,-1,2,4,-1,-1,5};，在数组的末尾有两个额外的 -1 以将 5 推到正确的索引。

您的实现无法工作，因为在模式中：

{
    Bit_node new_node = malloc(...)
}
return new_node;

new_node 在不在范围内时被访问。如果你遇到 -1，你想 return NULL 就像你在数组上越界时所做的那样。返回 NULL 表示“这里没有 child”，这正是您想要与 parent 框架通信的内容，以便它将缺少的 child 设置为 NULL。

修复应该非常简单：

Bit_node bit_arr2tree(int a[], int size, int i) {
    if (i>= size || a[i] < 0) {
    //           ^^^^^^^^^^^
        return NULL;
    }

    Bit_node new_node = bit_new(a[i]);
    new_node->sx = bit_arr2tree(a, size, i * 2 + 1);
    new_node->dx = bit_arr2tree(a, size, i * 2 + 2);
    return new_node;
}

顺便说一句，我要小心 against typedeffing away pointers。这会降低代码的可读性并隐藏信息。

这是一个可运行的概念验证：

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

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node *arr2tree(int arr_len, int *arr, int i) {
    if (i >= arr_len || arr[i] < 0) {
        return NULL;
    }

    struct Node *node = malloc(sizeof(*node));
    node->data = arr[i];
    node->left = arr2tree(arr_len, arr, i * 2 + 1);
    node->right = arr2tree(arr_len, arr, i * 2 + 2);
    return node;
}

void print_tree(struct Node *root, int depth) {
    if (root) {
        print_tree(root->right, depth + 4);

        for (int i = 0; i < depth; i++) {
            printf(" ");
        }

        printf("%d\n", root->data);
        print_tree(root->left, depth + 4);
    }
}

void free_tree(struct Node *root) {
    if (root) {
        free_tree(root->left);
        free_tree(root->right);
        free(root);
    }
}

int main() {
    int a[] = {10,4,7,2,3,-1,8,9,-1,2,4,-1,-1,5};
    struct Node *root = arr2tree(sizeof(a) / sizeof(a[0]), a, 0);
    print_tree(root, 0);
    free_tree(root);
    return 0;
}

输出：

Answer 2

鉴于输入数据结构不能保证父子关系是i*2+1和i*2+2，所以并不需要递归解决方案。输入序列代表广度优先顺序，所以按照广度优先顺序建树会更自然。

附带说明：函数 bit_new 还应初始化 sx 和 dx 成员：您不想留下未定义的值。

这里是你如何编写你的算法：

Bit_node bit_new(int n) {
    Bit_node new_node = malloc(sizeof(struct node));
    new_node -> n = n;
    new_node -> sx = NULL;
    new_node -> dx = NULL;
    return new_node;
}   


Bit_node bit_arr2tree(int a[], int size) {
    if (size == 0) {
        return NULL;
    }
    // Create a temporary array to store the node pointers
    Bit_node nodes[size];
    // Create the nodes
    for (int i = 0; i < size; i++) {
        nodes[i] = a[i] == -1 ? NULL : bit_new(a[i]);
    }
    // To link the nodes, use two indexes: parent and child
    for (int child = 1, parent = 0; child < size; child += 2, parent++) {
        // Here we "skip the gaps": a parent cannot be NULL:
        while (nodes[parent] == NULL) {
            parent++;
        }
        nodes[parent] -> sx = nodes[child];
        if (child + 1 < size) {
            nodes[parent] -> dx = nodes[child + 1];
        }
    }
    return nodes[0];
}

使用递归策略将数组转换为二叉树

convert array to binary tree with recursive strategy

c

algorithm

recursion

binary-tree