c - C 中仅使用指针的二叉树

Question

我正在用 C 语言完成家庭作业，我认为二叉搜索树将是实现我的解决方案的最佳方式。问题是我们不允许定义结构或任何复合数据类型，所以没有

struct TreeNode {
    struct TreeNode* parent;
    struct TreeNode* left;
    struct TreeNode* right;
    int key;
    int value;
}

或者类似的东西。

树必须完全用指针来实现，因此我一直在尝试定义许多宏，以使导航和编辑树更容易，例如这个宏用于获取指向节点父节点的指针(其中指针是空指针):

#define PARENT(ptr) *(void *)(ptr+ALIGNMENT)

当然，问题是您无法取消引用 void 指针。我的问题是:如果您有一个 void 指针，指向内存中存储另一个 void 指针的位置，那么如何读取该存储的指针。

或者如果这是不可能的，是否有更好的方法来制作这棵树？

Answer 1

将节点表示为数组，并使用指针算术来访问给定节点的左节点和右节点。例如，数字序列4,3,7,1,6存储在二叉树中:

     4
    / \ 
   3   7 
  / \ 
 1   6

如果您选择使用数组来表示这棵树，则位置 C 的节点的左子节点的位置为 2 * C，其右节点位于2 * C + 1。在我们的示例中，数字 3 位于第二 位置。它的左子节点位于 2 * 2 处，即位于 第四 位置，右子节点位于 2 * 2 + 1 处，即位于第五名:

values:     4     3     7     1     6
positions: 1st   2nd   3rd   4th   5th 

以下示例代码演示了如何遍历基于数组的二叉树。您可以弄清楚如何将新值插入树中(使用上面的公式)，如何动态增长数组，如何使用指针算术访问子节点等:

#include <stdio.h>

#define ARRAY_SIZE 5
static int btree[ARRAY_SIZE];

static void fill_btree ();
static void walk_btree ();

int
main ()
{
  fill_btree ();
  walk_btree ();
  return 0;
}

static void 
fill_btree ()
{
  btree[0] = 4;
  btree[1] = 3;
  btree[2] = 7;
  btree[3] = 1;
  btree[4] = 6;
}

static int
pos (int i)
{
  return ((i + 1) * 2);
}

static void 
walk_btree ()
{
  int i;

  for (i = 0; i < ARRAY_SIZE; ++i)
    {
      int p = pos(i);
      int root = btree[i];
      int left = ((p - 1) < ARRAY_SIZE) ? btree[p-1] : 0;
      int right = (p < ARRAY_SIZE) ? btree[p] : 0;

      printf ("root: %d, left: %d, right: %d\n", root, left, right);
    }
}