将二维数组呈现为树

Question

我有以下问题：

我有一个 n x n 整数数组，其中 n 是 2 的幂（1、2、4...）。我们可以想象整个数组（当n > 1时）被分成4块：

A B
D C

每块如果没有1个元素也可以类似的划分。我想将这个数组呈现为一棵树，其中每个节点都包含：

   a) integer, when the "square" cannot be divided futher
   or
   b) 4 nodes, corresponding to each piece: A,B,C,D

我有二维数组中的所有整数，我想编写一个函数来创建一棵树。到目前为止，我只设法创建了一个节点结构：

 struct node {
  int number;
  struct node *child[4];
};

问题是，我找不到遍历数组的方法，同时创建节点并为它们赋值。

你能用这个程序的伪代码支持我吗？

Answer 1

我建议您自下而上创建树的层：

首先创建一个 n x n 节点数组并将编号分配给节点。该数组将包含树的叶子。
然后创建一个新的二维节点数组，尺寸为 n/2 * n/2。对于每个节点，将原始数组的各个节点分配为子节点。因此，对于新数组中坐标为 (x,y) 的节点，您将分配子节点 (x*2,y*2)、(x*2+1,y*2)、(x*2,y* 2+1), 和 (x*2+1,y*2+1) 在旧数组中。
对新数组递归重复最后一步，直到数组的维度为 1 x 1。

因此，您最终得到一个代表树根的节点。

Answer 2

我想介绍一种自上而下的方法：

最好定义一个为您创建节点的函数。该函数负责递归地创建它自己的所有子项。

只有叶子会在其 int number; 字段中包含有价值的信息。

您将所有信息保存在二维数组中，并为树中的每个节点传入适当的上下 x 和 y 坐标。

这是描述我的方法的 C 代码：

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

#define DIM 4


struct treeNode{
int number;
struct treeNode * A,*B,*C,*D;
//A top left,
//B top right
//C bottom right
//D bottom left
};
struct treeNode* createNode(int input[][DIM], int x1, int x2, int y1, int y2)
{
    struct treeNode * output = malloc(sizeof(struct treeNode));
    output->number=-1; //arbitrary value gets overwritten in leafs
    output->A=NULL;
    output->B=NULL;
    output->C=NULL;
    output->D=NULL;

    if(x1==x2)// single integer
    {
       output->number=input[x1][y1];
    }
    else
    {
    int midX = x1 + (x2-x1)/2;
    int midY = y1 + (y2-y1)/2;

    output->A = createNode(input,     x1, midX,     y1, midY);
    output->B = createNode(input,     x1, midX, 1+midY,   y2);
    output->C = createNode(input, 1+midX,   x2, 1+midY,   y2);
    output->D = createNode(input, 1+midX,   x2,     y1, midY);
    }
    return output;
};

由于您的树是动态分配的，因此您需要一种优雅的方式来递归释放内存：

void deleteTree(struct treeNode* t)
{
    if(t==NULL) return; //NULL passed in
    if(t->A==NULL) //leaf
    {
        free(t);
        return;
    }
    deleteTree(t->A);
    deleteTree(t->B);
    deleteTree(t->C);
    deleteTree(t->D);
    free(t);//free memory for pointer;
}

在你的 main 函数中你有：

int main()
{

    int A[DIM][DIM]={0};

    int i=0, counter=1;
    for(;i<DIM;++i)
    {
        int j=0;

        for(; j<DIM; ++j) A[i][j]=counter++;
    }
    struct treeNode* root = createNode(A,0,DIM-1,0,DIM-1);

    struct treeNode* nonLeaf = root->B;

    struct treeNode* leaf = nonLeaf->B;
    printf("%d", leaf->number);


    deleteTree(root);

    return 0;
}

将二维数组呈现为树

Presenting 2D array as a tree

c

algorithm

pseudocode