二叉树 InOrderWalk 实现未按预期工作
Binary Tree InOrderWalk implementation not working as expected
我正在尝试在 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获得。
任何有关代码未按预期工作的原因的反馈都将不胜感激。
预先感谢您的帮助。
除了根之外,您的代码没有向树中添加元素。设置 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;
}
我正在尝试在 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获得。
任何有关代码未按预期工作的原因的反馈都将不胜感激。
预先感谢您的帮助。
除了根之外,您的代码没有向树中添加元素。设置 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;
}