c - 二叉搜索树的中序遍历,显示一些错误
问题描述
这是我用于 BST 中序遍历的函数
void inOrder(struct node* root)
{
if(root==NULL)
{
return;
}
inOrder(root->left);
printf("Key:%d,Pointer:%p\n",root->key,root);
inOrder(root->right);
}
相同的结构是
struct node{
int key;
struct node *left,*right;
};
当我运行该函数时,我会为以下插入获得两个 0 额外元素:
root=insert(root,7);
insert(root,4);
insert(root,10);
insert(root,3);
insert(root,5);
insert(root,1);
insert(root,2);
insert(root,0);
insert(root,8);
insert(root,14);
insert(root,6);
insert(root,9);
insert(root,16);
insert(root,12);
insert(root,15);
insert(root,17);
inOrder(root);printf("\n");
插入函数如下:
struct node *insert(struct node * root,int ele)
{
struct node *temp=newNode(ele);
struct node *tree=root;
struct node *saver;
if(root==NULL)
{
root=temp;
}
else
{
while(tree!=NULL)
{
saver=tree;
if(ele<tree->key)
tree=tree->left;
else
tree=tree->right;
}
if(ele<saver->key)
{
saver->left=temp;
}
else
{
saver->right=temp;
}
}
return saver;
}
除了我添加的主要元素之外,输出显示了两个 0。我最近学习了二叉搜索树,并尝试实现它,有人可以帮我纠正这个错误。先感谢您
解决方案
在插入
if(root==NULL)
{root=temp;
}
一定是
if(root==NULL)
{
saver=temp;
}
因为您返回保护程序(未在您的版本中初始化)
我想在你的主要代码中,代码不是你给出的,而是类似的
struct node * root = NULL;
root=insert(root,7);
insert(root,4);
...
如果我这样定义newNode:
struct node * newNode(int ele)
{
struct node * r = malloc(sizeof(struct node));
r->key = ele;
r->left = r->right = NULL;
return r;
}
我做了其他更改:
pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra n.c
pi@raspberrypi:/tmp $ ./a.out
Key:0,Pointer:0xf04078
Key:1,Pointer:0xf04058
Key:2,Pointer:0xf04068
Key:3,Pointer:0xf04038
Key:4,Pointer:0xf04018
Key:5,Pointer:0xf04048
Key:6,Pointer:0xf040a8
Key:7,Pointer:0xf04008
Key:8,Pointer:0xf04088
Key:9,Pointer:0xf040b8
Key:10,Pointer:0xf04028
Key:12,Pointer:0xf040d8
Key:14,Pointer:0xf04098
Key:15,Pointer:0xf040e8
Key:16,Pointer:0xf040c8
Key:17,Pointer:0xf040f8
完整的代码是:
#include <stdio.h>
#include <stdlib.h>
struct node{
int key;
struct node *left,*right;
};
void inOrder(struct node* root)
{
if(root==NULL)
{return;}
inOrder(root->left);
printf("Key:%d,Pointer:%p\n",root->key,root);
inOrder(root->right);
}
struct node * newNode(int ele)
{
struct node * r = malloc(sizeof(struct node));
r->key = ele;
r->left = r->right = NULL;
return r;
}
struct node *insert(struct node * root,int ele)
{
struct node *temp=newNode(ele);
struct node *tree=root;
struct node *saver;
if(root==NULL)
{
saver=temp;
}
else
{
while(tree!=NULL)
{
saver=tree;
if(ele<tree->key)
tree=tree->left;
else
tree=tree->right;
}
if(ele<saver->key)
{
saver->left=temp;
}
else
{
saver->right=temp;
}
}
return saver;
}
int main()
{
struct node * root = NULL;
root=insert(root,7);
insert(root,4);
insert(root,10);
insert(root,3);
insert(root,5);
insert(root,1);
insert(root,2);
insert(root,0);
insert(root,8);
insert(root,14);
insert(root,6);
insert(root,9);
insert(root,16);
insert(root,12);
insert(root,15);
insert(root,17);
inOrder(root);printf("\n");
}
推荐阅读
- excel - 如何将宏应用于整个列?
- r - 在RMarkdown中以错误的顺序输出R中的for循环
- php - 有没有办法直接重定向下载流请求,而不是下载文件两次(由服务器然后由用户)?
- spring-boot - 将新条目添加到 postgree 数据库时如何将数据发送到 ionic 4?
- java - 如何设计批量 GET 调用?
- apollo - 如何在 next.js 中改变 apollo 上下文?
- c++ - 本征为零,但在每个矩阵元素上
- python - 在熊猫数据框中解压缩具有与索引相似值的行?
- sql-server - SSIS - 从不同的数据库中查找记录
- javascript - 如何并排排序 html javascripts 明信片?