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

가 어떻게 내 이진 트리에 노드를 추가하려면와 B (오른쪽)가 이미 가득?

"전체"로 말하면 두 자식 노드 자체에 두 개의 자식이 있음을 의미합니다. 이 경우 새 노드를 자식의 자식 중 하나에 추가해야합니다. 일반적으로 재귀 함수를 통해이 작업을 수행하므로 어린이의 자식도 "전체"인 경우를 올바르게 처리 할 수 ​​있습니다.

난 그냥 ("균형"이 자체가 몇 가지를 의미 할 수 있습니다. 예를 들어, "높이 균형 '과'무게 균형"나무가

균형 트리를 만들어야합니다. 원하는 것을 지정하지 않았습니다.)

다음 질문은 (전체) 자식이 오른쪽 또는 왼쪽에 새 노드를 추가하는 것입니다. 한 가지 옵션은 각 노드의 전체 자손 수를 유지하고 항상 가장 적은 수의 자식 노드에 추가하는 것입니다.

또 다른 옵션은 트리에있는 노드의 총 수를 유지하고 해당 숫자의 비트 (첫 번째 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을 참조하십시오.이것들은 일반적으로 정렬 된 트리에 사용되지만, 정렬되지 않은 트리에 맞게 조정해야합니다.