Двоичное дерево в Си, использующее только указатели

Question

Я работаю над домашним заданием в C и думаю, что бинарное дерево поиска было бы наилучшим способом реализации моего решения.Проблема в том, что нам не разрешено определять структуры или какие-либо составные типы данных, поэтому нет

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

или чего-либо подобного.

Дерево должно быть полностью реализовано с помощью указателей,поэтому я пытался определить ряд макросов, чтобы упростить навигацию и редактирование дерева, например, этот, чтобы получить указатель на родительский узел узла (где указатели являются пустыми указателями):

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

Проблема, конечно, в том, что вы не можете разыменовать пустые указатели.Мой вопрос: если у вас есть пустой указатель на место в памяти, где хранится другой пустой указатель, как вы можете прочитать этот сохраненный указатель.

Или, если это невозможно, есть ли лучший способ сделать это дерево

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

Answer 2

Вот способ справиться с вашими указателями. Я не написал все ваше дерево (вы можете сделать это), но вот способ управления «структурой» вашего указателя без использования реальной структуры. Это не создает дерево для вас, оно просто показывает, как вы будете создавать «искусственные» узлы и управлять указателями в памяти.

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

unsigned int *newNode();

int main() {
  unsigned int *root;
  unsigned int *data;
  unsigned int *left, *right;
  unsigned int *nodeA, *A, *nodeB, *B;

  /* get a 12 byte root node */
  root = newNode();
  printf("root: %p\n", root);

  /* Setup root node.  Each is an offset unsigned into the 12 bytes in the faux node */
  data = root;
  left = root + 1;
  right = root + 2;

  /* create a NEW 12 byte child node and assign it to the root left child */
  nodeA = newNode();
  memcpy(left,&nodeA,sizeof(unsigned int));
  printf("NodeA ptr (left child root): %p\n", nodeA);

  /* create a NEW 12 byte child node and assign it to the root right child */
  nodeB = newNode();
  memcpy(right,&nodeB,sizeof(unsigned int));
  printf("NodeB ptr (right child root): %p\n", nodeB);

  /* what are my pointers? */
  A = (unsigned int *)*(root + 1); /* root left node is pointing to child nodeA */
  B = (unsigned int *)*(root + 2); /* root right node is pointing to child nodeB */

  printf("A: %p, B: %p\n", A, B);

  /*    
   * hopefully from this you can see the recursive nature of it and how    
   * you would build the tree using these pointer allocations and assignments    
   */    

  /*    
   * This is not meant to be a full working application.  I did not free any    
   * of these mallocs.  You have to free up your memory when the program     
   * finishes.  This was just to show how to go about making nodes    
   */ 

 return(0);
}

/* 
 * allocates 12 bytes to hold three unsigned integers, one to some data stream
 * one for the left node, one for the right node
 *
 * |--data--|--left--|--right--| (each block is a four byte unsigned int)
 *
 */
unsigned int *newNode() {
  /* Allocates 12 bytes to store 3 unsigned integer values */
  unsigned int *ptr = (unsigned int *)malloc(sizeof(unsigned int) * 3);
  memset(ptr,0,sizeof(unsigned int) * 3);
  return(ptr);
}