이진 트리 InOrderWalk 구현이 예상대로 작동하지 않습니다.

Question

C에서 이진 트리 데이터 구조를 구현하고 몇 번의 삽입 후 인라인 순회를 수행하려고합니다. 프로그램은 내가 삽입 한 첫 번째 요소 만 인쇄하고 다른 노드는 인쇄하지 않습니다.

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

struct tree 
{ 

    struct node *root; 

}; 


struct node 
{ 

    int val; 

    struct node *left; 

    struct node *right; 

}; 


struct tree *init() 
{ 

    struct tree *t = malloc (sizeof (struct tree)); 


    t->root = NULL; 

    return t; 

} 



void insert (struct tree *t, int val) 
{ 

    struct node *succ; 

    struct node *new = malloc (sizeof (struct node)); 


    new->val = val; 

    new->left = NULL; 

    new->right = NULL; 


    succ = NULL; 

    struct node *insertPlace = t->root; 

    while (insertPlace != NULL) 
    { 

     succ = insertPlace; 

     if (insertPlace->val < new->val) 

     insertPlace = insertPlace->right; 

     else 

     insertPlace = insertPlace->left; 

    } 

    if (succ == NULL) 
    t->root = new; 

    else if (new->val < succ->val) 

    insertPlace = succ->right; 

    else 

    insertPlace = succ->left; 

} 



void inorderWalk (struct node *p) 
{ 

    if (p != NULL) 
    { 

    if (p->left != NULL) 
     inorderWalk (p->left); 

    printf ("%d ", p->val); 

    if (p->right != NULL) 
     inorderWalk (p->right); 

    } 

} 



void 
print (struct tree *t) 
{ 

struct node *p; 

p = t->root; 


inorderWalk (p); 


} 



int 

main() 
{ 

struct tree *t = init(); 

insert (t, 5); 

insert (t, 15); 

insert (t, 20); 

insert (t, 1); 

insert (t, 2); 

insert (t, 4); 

insert (t, 10); 


print (t); 


return 0; 

} 

코드

또한 온라인 GDB 디버거 here 사용할 수 있습니다.

코드가 예상대로 작동하지 않는 이유에 대한 의견을 보내 주시면 감사하겠습니다.

도움을 주셔서 감사합니다.

Answer 1

코드는 루트 이외의 트리에 요소를 추가하지 않습니다. insertPlace = succRight을 설정하면 insertPlace 변수 만 업데이트되며 트리는 업데이트되지 않습니다.

나는 올바른 노드를 찾고 실제 루프에서 왼쪽 또는 오른쪽 노드의 값을 설정하는 것이 좋습니다 :

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

struct tree 
{ 
    struct node *root; 
}; 


struct node 
{ 
    int val; 

    struct node *left; 

    struct node *right; 
}; 


struct tree *init() 
{ 
    struct tree *t = malloc (sizeof (struct tree)); 
    t->root = NULL; 
    return t; 
} 



void insert (struct tree *t, int val) 
{ 

    struct node *succ; 

    struct node *new = malloc (sizeof (struct node)); 
    new->val = val; 
    new->left = NULL; 
    new->right = NULL; 

    succ = NULL; 

    struct node* insertAtNode=t->root; 
    if (insertAtNode==NULL) { 
    t->root=new; 
    return; 
    } 
    do { 
    if (insertAtNode->val < new->val) { 
     if (insertAtNode->right==NULL) { 
     insertAtNode->right=new; 
     return; 
     } else { 
     insertAtNode=insertAtNode->right; 
     } 
    } else if (insertAtNode->left==NULL) { 
     insertAtNode->left=new; 
     return; 
    } 
    else { 
     insertAtNode=insertAtNode->left; 
    } 
    } 
    while(1); 
} 



void inorderWalk (struct node *p) 
{ 
    if (p != NULL) 
    { 
    if (p->left != NULL) 
     inorderWalk (p->left); 
    printf ("%d ", p->val); 
    if (p->right != NULL) 
     inorderWalk (p->right); 
    } 
} 



void print (struct tree *t) 
{ 
    struct node *p; 

    p = t->root; 

    inorderWalk (p); 
    printf("\n"); 
} 



int main() 
{ 
    struct tree *t = init(); 

    insert (t, 5); 

    insert (t, 15); 

    insert (t, 20); 

    insert (t, 1); 

    insert (t, 2); 

    insert (t, 4); 

    insert (t, 10); 


    print (t); 


    return 0; 

}