二叉树InOrderWalk实现不按预期方式工作
问题描述:
我想在C中实现一个Binary Tree数据结构,并在几次插入后执行一次inorder遍历。 程序只打印我插入的第一个元素,而不打印其他任何节点。二叉树InOrderWalk实现不按预期方式工作
#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调试器。
关于为什么代码不能按预期工作的任何反馈将非常感激。
非常感谢您的帮助。
答
您的代码不会将元素添加到树中,除了根。设置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;
}
这工作就像一个魅力!现在节点被正确插入并按正确的顺序遍历。非常感谢,保罗! –