Cでバイナリツリーにノードを追加する方法は？

Question

A（左）とB（右）がすでにいっぱいの場合、バイナリツリーにノードを追加するにはどうすればよいですか？バランスのとれたツリーを作成するだけです。しかし、ツリーにデータを追加する方法を理解することはできません。どんな助けでも大歓迎です。

ありがとうございます。

#include <stdio.h> 
#include <string.h> 
#include <ctype.h> 
#include <stdlib.h> 

struct node 
{ 
    char *titel; 
    struct node *A; 
    struct node *B; 
}; 

void display(struct node *leaf) 
{ 
    if (leaf != NULL) 
    { 
     display(leaf->A); 
     printf("%s\n",leaf->titel); 
     display(leaf->B); 
    } 
} 

struct node *insert(char* titel, struct node **leaf) 
{ 
    if (*leaf == 0) 
    { 
     *leaf = (struct node*)malloc(sizeof(struct node)); 
     (*leaf)->titel = malloc(strlen(titel)+1); 
     strcpy((*leaf)->titel,titel); 
     (*leaf)->A = NULL; 
     (*leaf)->B = NULL; 
    } 
    else if ((*leaf)->A == NULL) 
    { 
     (*leaf)->A = insert(titel,&(*leaf)->A); 
    } 
    else if ((*leaf)->B == NULL) 
    { 
     (*leaf)->B = insert(titel,&(*leaf)->B); 
    } 
    //WHAT TO ADD HERE TO CREATE ANOTHER NODE? 
    return(*leaf); 
} 

int main(int argc, char const *argv[]) 
{ 
    struct node *root = NULL; 
    insert("root",&root); 
    insert("chapter_1A",&root); 
    insert("chapter_1B",&root); 
    insert("chapter_2A",&root); 
    insert("chapter_2B",&root); 
    insert("chapter_3A",&root); 
    display(root); 
    return 0; 
} 

出力はバランスのとれたバイナリツリーのようにする必要があります。印字する必要はありませんが、メモリにそのように保存してください。

実際の出力：

chapter_1A 
root 
chapter_1B 

---

     root 
       /  \ 
      chapter_1A chapter_1B 
     / \ / \ 
     ch_2A ch_2B ch_3A ch_3B 
       and so on. 

Answer 1

A（左）とB（右）がすでに満杯であれば、私は私のバイナリツリーにノードを追加するにはどうすればよいですか？

「フル」とは、両方の子ノード自体に2つの子があることを意味します。この場合、子ノードの子ノードのいずれかに新しいノードを追加する必要があります。通常は、再帰関数を使用してこれを行います。これにより、子どもの子も "完全"なようなケースを正しく処理できるようになります。

は、私はちょうど（「バランス」は、それ自体は、いくつかのものを意味することに注意してください。例えば、「高さのバランス」と「重量バランスの取れた」木がある

バランスが取れているツリーを作成する必要があります。どちらを指定するかは指定しないでください）。

質問は、（フル）子が新しいノードを右または左に追加するかどうかです。 1つの選択肢は、各ノードの子孫の総数を保持し、常に子ノードに追加することです。

ツリー内のノードの総数をカウントし、その番号のビットを使用して（最初の1ビットを無視して）、新しいノードを挿入する場所を決定します。あなたは5つのノードでツリーを持っている場合たとえば、新しいノードを追加するには

    A 
      B   C 
     D E 

、バイナリで110である、6にノードカウントをインクリメント。最初の文字は無視してください1;次の1を「右に」（Cに）、「0」を「左に」（Cの左の子として挿入するように指示する）と解釈します。あなたが値を返す必要がないので、私はvoidに戻り値の型を変更し

void insert(char* titel, struct node **leaf, int nodeCount, int bitPos) 
{ 
    if (*leaf == 0) 
    { 
    *leaf = (struct node*)malloc(sizeof(struct node)); 
    (*leaf)->titel = malloc(strlen(titel)+1); 
    strcpy((*leaf)->titel,titel); 
    (*leaf)->A = NULL; 
    (*leaf)->B = NULL; 
    } 
    else 
    { 
    int currentBit = (nodeCount >> bitPos) & 1; 
    if (currentBit == 0) { 
     // insert to left 
     insert(titel, &((*leaf)->A), nodeCount, bitPos - 1); 
    } 
    else 
    { 
     // insert to right 
     insert(titel, &((*leaf)->B), nodeCount, bitPos - 1); 
    } 
    } 
} 

お知らせ：あなたのコードは次のようになります。私は最初の計算の値をbitPosのままにしておきます（覚えておいてください：最高位の位置は1ビットから1を引いたものです）。

ツリーから要素を削除する必要がある場合は、その要素を再バランスする方法を見つける必要があります。

挿入と削除の両方をサポートするバランスのとれたツリーを維持するためのいくつかのデータ構造とアルゴリズムがあります。例えば、red-black treesおよびAVL treesを参照してください。これらは通常順序付けされたツリーに使用されますが、順序付けられていないバランスのとれたツリーに適合させるのは簡単です。