現在，我明白下面的代碼只適用於root及其子項，但我不知道如何擴展它。每個節點在傳遞「孫子們」之前都必須有孩子。謝謝。如何從右向左插入C樹中的節點？

void insert_node(IndexTree **root, Node *node) { 
    IndexTree *temp = (IndexTree*)malloc(sizeof(IndexTree)); 
    memcpy(&temp->value.cs, node, sizeof(Node)); 
    temp->left = NULL; 
    temp->right = NULL; 
    temp->tip=1; 

if ((*root) == NULL) { 
    *root = temp; 
    (*root)->left = NULL; 
    (*root)->right = NULL; 
} 
else { 
    while (1) { 
     if ((*root)->right == NULL) { 
      (*root)->right = temp; 
      break; 
     } 
     else if ((*root)->left == NULL) { 
      (*root)->left = temp; 
      break; 
     } 
    } 
}

2017-01-24 xena12

既然你只是把節點放在一個固定的順序，這實際上是一個數組，而不是一棵樹。 – stark

使用遞歸函數。

樹是遞歸數據類型（https://en.wikipedia.org/wiki/Recursive_data_type）。在他們中，每個節點都是自己樹的根。嘗試使用嵌套if s和while來處理它們只會限制您對樹的深度。

考慮以下功能：void print_tree(IndexTree* root)。是越過樹木的所有值的實現執行以下操作：

void print_tree(IndexTree* root) 
{ 
     if (root == NULL) return; // do NOT try to display a non-existent tree 

     print_tree(root->right); 
     printf("%d\n", root->tip); 
     print_tree(root->left); 
}

的函數調用本身，這是一個完全合法的舉動，以確保您可以解析（幾乎）任意深度的樹。但是，請注意無限遞歸！如果你的樹有循環（因此不是樹），或者如果你忘記包含退出條件，你會得到一個錯誤，稱爲...堆棧溢出！您的程序將有效地嘗試在堆棧上添加無限的函數調用，您的操作系統幾乎肯定會不喜歡這種調用。

至於插入，解決方案本身是類似於打印樹：

void insert_value(IndexTree* root, int v) 
{ 
    if (v > root->tip) { 
     if (root->right != NULL) { 
      insert_value(root->right, v); 
     } else { 
      // create node at root->right 
     } 
    } else { 
     // same as above except with root->left 
    } 
}

來源

2017-01-24 19:09:20 Adrien

作爲一個快速提示，我假設你在這裏使用了一個二叉搜索樹，因此'if（v> root-> tip）'條件。 – Adrien

很錯。沒有比較功能。任務是在開始下一個任務之前填充每個級別。遞歸解決方案無法確定哪個方向下降。最好的策略是對節點總數進行計數並在結尾添加下一個節點。 – stark

這可能是一個有趣的編程問題，使用鏈接的表示創建一個完全二叉樹。這裏Linked是一個非數組表示，其中左和右指針（或引用）分別用於引用左側和右側子節點。如何編寫一個總是在最後一級和最左邊的可用位置添加新節點的插入函數？要創建鏈接的完整二叉樹，我們需要以層次順序的方式跟蹤節點，以便下一個要插入的節點位於最左邊的位置。隊列數據結構可用於跟蹤插入的節點。
以下是在完整二叉樹中插入新節點的步驟。（右sckewed）
1. If the tree is empty, initialize the root with new node.

2. Else, get the front node of the queue.

……. if the right child of this front node doesn’t exist, set the right child as the new node. //as per your case
…….else If the left child of this front node doesn’t exist, set the left child as the new node.

3. If the front node has both the left child and right child, Dequeue() it.

4. Enqueue() the new node。

來源

2017-01-24 19:13:28

如何從右向左插入C樹中的節點？

回答

使用遞歸函數。

相關問題