учебники о древовидных структурах данных с левым, правым и родительским узлами

Question

Может кто-нибудь направить меня к какому-нибудь учебнику по древовидным структурам данных, используя C с левым, правым и родительским узлами в структуре.Я искал с помощью Google и в переполнении стека, но я нахожу только дерево только с узлом * слева и узлом * справа.Чтобы было ясно, я ищу учебник по дереву с:

struct Node {
  int data;
  Node *parent, *left, *right;  
};  

Answer 1

Я не уверен, что следую.И на самом деле я не думаю, что вы могли бы найти какие-либо учебники для этого, так как это больше похоже на вопрос, связанный с алгоритмикой.Насколько я помню, CLR 1 немного освещал эту тему.

Это пример того, как может выглядеть дополнение для такого дерева.Но я думаю, что CLR освещает это лучше, чем я могу привести в нескольких строках кода.

int add(node **root, int value)
{
   node *var,*parent_node;
   var = malloc(sizeof(node));
   var->data = value;
   /* if the tree hasn't been initialised we do so now */
   if (*root == NULL)
   {
      var->parent = NULL;
      var->left = NULL;
      var->right = NULL;
      return 0;
   }
   /* we look for the future parent of our new node */
   parent_node = search(*root,value);
   /* if the value already exists we return -1 */
   if (parent_node->data == value)
       return 0;
   var->parent = parent_node;
   /* put the new node into position */
   if (parent_node->data > value)
       parent_node->left = var;
   else
       parent_node->right = var;
   return 0;
}

Эта функция поиска может быть любой функцией поиска в учебнике для двоичного дерева, так как родитель не входиткогда вы делаете поиск.Хотя следует отметить, что средний поиск вернет NULL, если значение не найдено, поэтому вы можете изменить его так, чтобы он возвращал «родителя» NULL.Что-то вроде:

node *search(node *root, int value)
{
   node *var, *cursor;
   cursor = root;
   while(cursor->data != value)
   {
      if (cursor->data > value)
          var = cursor->left;
      else
          var = cursor->right;
      if (var == NULL)
          return cursor;
      cursor = var;
   }
   return cursor;
}  

Answer 2

Я думаю, что древовидная структура покрывает все ваши потребности. Сначала взгляните на tree.hh , но в C ++.