二叉树InOrderWalk实现不按预期方式工作

Question

我想在C中实现一个Binary Tree数据结构，并在几次插入后执行一次inorder遍历。 程序只打印我插入的第一个元素，而不打印其他任何节点。

#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; 

} 

该代码也可用here与在线gdb调试器。

关于为什么代码不能按预期工作的任何反馈将非常感激。

非常感谢您的帮助。

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; 

}