Cのツリーを右から左に挿入するには？

Question

以下のコードは、ルートとその子だけで動作することを理解していますが、展開方法はわかりません。すべてのノードには、「孫」を渡す前に子供がいなければなりません。ありがとうございました。

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

Answer 1

再帰関数を使用します。

ツリーは再帰的なデータ型（https://en.wikipedia.org/wiki/Recursive_data_type）です。それらの中では、すべてのノードがそれ自身のツリーのルートです。 ifと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); 
} 

機能は、あなたが（ほぼ）任意の深ツリーを解析できることを確実にするために、完全に合法動きである、自分自身を呼び出します。しかし、無限の再帰の注意してください！あなたのツリーにサイクルがある場合（したがってツリーではない場合）、または終了条件を含めることを忘れると、... Stack Overflowと呼ばれるエラーが発生します。あなたのプログラムはスタック上に無限の関数呼び出しを効果的に追加しようとしますが、あなたのOSはほとんど嫌いです。挿入するよう

、ソリューション自体は、ツリーを印刷するのと同じである：

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

Answer 2

リンクの表現を使用して完全なバイナリツリーを作成するために、興味深いプログラミングの質問かもしれません。ここでLinkedとは左と右のポインタ（または参照）をそれぞれ左と右の子を参照するために使用する非配列表現を意味します。最後のレベルと利用可能な最も左の位置に常に新しいノードを追加する挿入関数を書く方法は？ リンクされた完全なバイナリツリーを作成するには、挿入する次のノードが一番左の位置になるように、レベル順にノードを追跡する必要があります。キューデータ構造を使用して、挿入されたノードを追跡することができます。
以下は、Complete Binary Treeに新しいノードを挿入する手順です。 （右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。