이진 검색 트리가 아닌 이진 트리 만들기

Question

왼쪽에서 오른쪽으로 채워지는 이진 트리를 만들고 싶습니다. 1,2,3 다음 삽입 할 경우 즉 나무는 트리의 노드를 삽입, 내가 삽입 기능을 썼다

1 
/ \ 
2  3 

처럼 보일 것입니다. 첫 번째 노드에 대해서는 모든 것이 정상적으로 작동합니다. 그러나 다음 노드 (부모 노드가 4,5를 자식 노드로 삽입하고 나중에 6,7을 자식 노드로 3을 삽입하려면 3)을 부모 노드 (2,3)간에 어떻게 전환해야합니까? ?

다음은 컴퓨터 프로그래밍의 예술의 사본을해야합니까 내 삽입 기능

struct node * Insert(struct node * node, int data) { 
if(node == NULL) 
    return (newNode(data)); 
else { 
    if(!node->left) 
     node->left = Insert(node->left,data); 
    if(!node->right) 
     node->right = Insert(node->right,data); 
    //can't figure out the condition when they both fail 
} 
} 

Answer 1

struct node **InsertPoint(struct node **node, int *level){ 
    if(*node == NULL) 
     return node; 

    int left_level, right_level; 
    struct node **left_node, **right_node; 
    left_level = right_level = *level + 1; 
    left_node = InsertPoint(&(*node)->left, &left_level); 
    right_node = InsertPoint(&(*node)->right, &right_level); 
    if(left_level <= right_level){ 
     *level = left_level; 
     return left_node; 
    } else { 
     *level = right_level; 
     return right_node; 
    } 
} 

struct node *Insert(struct node *node, int data) { 
    struct node **np; 
    int level = 0; 
    np = InsertPoint(&node, &level); 
    *np = newNode(data); 
    return node; 
}