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位于该second位置.它的左孩子在2 * 2,即fourth位置和右孩子在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);
    }
}