c - 关于具有左节点、右节点和父节点的树数据结构的教程

Question

有人可以指导我使用 C 结构中的具有左节点、右节点和父节点 的树数据结构教程。我用 Google 和 Stack Overflow 进行了搜索，但我只找到只有 Node *left 和 Node *right 的树。明确地说，我正在搜索树教程:

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