有關左樹，右樹和父樹節點樹數據結構的教程

Question

有人能指示我使用C 的樹數據結構的一些教程，結構中有左，右和父節點。我用谷歌和堆棧溢出進行搜索，但我只找到只有Node *左側和Node *右側的樹。 要清楚，我在尋找樹與教程：

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 structure涵蓋所有的需求。首先看看tree.hh，但是在C++中。