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

问题描述

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

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

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

标签： calgorithmrecursionbinary-tree

首先，int a[] = {10,4,7,2,3,-1,8,9,-1,2,4,5};不应该产生您期望的树，5 作为 8 的左孩子。由于 8 在索引 6 处，它的左孩子将在 index 处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，您希望返回 NULL，就像您在数组越界时所做的一样。返回 NULL 表示“这里没有孩子”，这正是您想要与父框架通信的内容，以便它将丢失的孩子设置为 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;
}

顺便说一句，我会警告不要将指针类型化。这会降低代码的可读性并隐藏信息。

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

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

输出：

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

问题描述

解决方案

推荐阅读