예약 주문 이진 검색 나무 삽입

Question

나는 너무 부끄럽기 때문에 고통스럽게 어리석은 질문입니다. 나는 지난 4 시간 동안 다른 알고리즘을 테스트 해 보았고, 종이로 시도해 보았지만 아직도 제대로 작동하지 못했다.

내가 당신에게 프로젝트 구현의 세부 사항을 아끼지하지만 기본적인 질문은 다음과 같습니다. "당신이 예약 주문 이진 트리에 삽입 노드를 처리하려면 어떻게

을 예약 주문 BST, 나는 모든 것을 의미 노드는 선행 순서 순회 (예 : 인쇄)를 사용하여 트리를 가로 지르는 방식으로 노드를 오름차순으로 인쇄해야합니다.

필요한 모든 간단한 알고리즘이 필요합니다. 간단한 삽입 알고리즘을 시도했습니다. 여기에 (stackoverflow에,하지만 그것은 잘못된 것 (또한 종이에 시도));

노드는 bas 있습니다 ically : like :

typedef struct testNode{ 
    int key; 
    struct testNode *leftChild; 
    struct testNode *rightChild; 
}NODE; 

삽입 데이터는 고유 한 정수 목록 일뿐입니다. int를 키로 사용하여 노드를 만든 다음 노드를 트리에 추가해야합니다. NULL 포인터로 시작하는 루트 노드가 있습니다.

불명의 점이 있으면 죄송합니다.

도움 주셔서 감사합니다.

편집 :

가

void insert(NODE **tree,int key){ 
if(*tree){ 
    if ((*tree)->key >= key){ 
     //Insert before this ..... 
     NODE *temp = createNode(key); 
     temp->lc = (*tree); 
     (*tree) = temp; 

    } 
    else if(!(*tree)->rc){ 
     //Right Child doesn't exist .... 
     insert(&(*tree)->lc,key); 
    } 
    else if((*tree)->rc->key < key){ 
     //Right child exists and is smaller than spread ... insert left ... 
     insert(&(*tree)->lc,key); 
    } 
    else{ 
     //Right child exists and is greater than spread ... insert right ... 
     insert(&(*tree)->rc,key); 
    } 
    //If the code as progressed to this point, insertion must have occured, 
      //and the code returns ...... 
} else { 
    //the **tree pointer points to NULL. Insert here .... 
    SPREADNODE *temp = createSpreadNode(spread); 
    //temp->lc = (*tree); 
    (*tree) = temp; 
} 
} 

Answer 1

는 미리 주문 BST의 정의에 대해 생각 : 아래 제공되는 알고리즘을 기반으로하는이 내가 생각 해낸 것입니다 루트 노드는 가장 작은 요소, 그 두 하위 트리의 루트가 오른쪽 하위 트리의 모든 값보다 커지도록 미리 정렬 된 트리를 만듭니다.

그래서 일하는 것이 하나의 알고리즘은 다음과 같습니다

1. 새 노드가 루트보다 작은 경우, 그것은 두 개의 자식 노드의 하나로서 기존의 트리에 새 루트 및 지점합니다.
2. 새 노드가 루트보다 크지 만 오른쪽 하위 트리의 루트보다 작은 경우 반복적으로 왼쪽 하위 트리에 삽입하십시오.
3. 그렇지 않으면 재귀 적으로 오른쪽 하위 트리에 삽입하십시오.

매우 균형 잡힌 트리를 생성 할 가능성은 없지만 제대로 작동합니다. 나는 적어도 하나의 다른 간단한 대안을 생각할 수 있으며, 독자들에게 운동으로 남겨놓은 것들을 더 균형있게 만드는 방법은 의심의 여지가 없다 .-