关于排序二叉树的插入操作和输出节点的问题
本帖最后由 Ranbo_ 于 2020-2-25 23:16 编辑刚学排序二叉树，题目描述这样的：有N个关键字值各不相同的节点，要求按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。
我的代码是这样的：
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int val;
struct Node *lchild;
struct Node *rchild;
}BTNode;
//创建节点
void create(BTNode *T, int value)
{
T = (BTNode*) malloc(sizeof(BTNode));
T -> lchild = NULL;
T -> rchild = NULL;
T -> val = value;
}
//插入节点，并输出父节点的值
int insert(BTNode *T, int value, int father)//T为当前访问的节点，value是待插入节点的键值，father为当前访问节点的父节点的键值
{
if(T == NULL) //若T为空，说明已经找到叶节点，则创建新节点并输出父节点的值
{
create(T, value);
//printf("%d\n", father);
return father;
}
else if(value > T -> val)//若待插键值>当前节点键值，则插入到右子树上
{
return insert(T -> rchild, value, T -> val);
//T -> rchild = insert(T -> rchild, value, T -> val);
}
else//若待插键值<当前节点键值，则插入到左子树上
{
return insert(T -> lchild, value, T -> val);
//T -> lchild = insert(T -> lchild, value, T -> val);
}
}
/*
//后序遍历清空树
void clear(BTNode *p)
{
clear(p -> lchild);
clear(p -> rchild);
free(p);
}
*/
int main()
{
int n;
int i;
BTNode *T = (BTNode*) malloc(sizeof(BTNode));
BTNode *root = T;
scanf("%d", &n);//n个节点
scanf("%d", &i);
root -> val = i;
root -> lchild = NULL;
root -> rchild = NULL;
printf("%d\n", -1);
int value;
for(i = 0; i < n - 1; i++)
{
T = root;
//int father = -1; //初始化储存的父节点的值
int father;
scanf("%d", &value);
father = insert(T, value, -1);
printf("%d\n", father);
}
/*
BTNode *p = root;
//后序遍历清空树
clear(p);
*/
return 0;
}有一个问题，就是我不管输入啥玩意儿进去它永远都输出的是根节点的值，这是为啥呀
一段怎么看怎么别扭的代码。
对指针还没有理解到位， 对树理解还很不足，对递归不理解。
BTNode *T = (BTNode*) malloc(sizeof(BTNode));
T = NULL; // 这2行代码看着不别扭？
直接
BTNode *T = NULL不行吗？
// 前面看你传father 后面又看你传-1，是我没搞懂你的思维方式？ 我觉得father = insert(T, value) 这样够了吧。
father = insert(T, value, father);
father = insert(T, value, -1);
// 实现递归的2个基本条件
// -调用函数本身
// -设置了正确的结束条件
int insert(BTNode *T, int value, int father)//T为当前访问的节点，value是待插入节点的键值，father为当前访问节点的父节点的键值
{
if(T == NULL) //若T为空，说明已经找到叶节点，则创建新节点并输出父节点的值
{
create(T, value);
//printf("%d\n", father);
return father;
}
else if(value > T -> val)//若待插键值>当前节点键值，则插入到右子树上
{
return insert(T -> rchild, value, T -> val);
//T = insert(T -> rchild, value, T -> val);
}
else//若待插键值<当前节点键值，则插入到左子树上
{
return insert(T -> lchild, value, T -> val);
//T = insert(T -> lchild, value, T -> val);
}
}
我的建议 把基础打好，多练习，多打代码；别一头牛似的什么基础都没搞懂就一直冲。。。你这代码跟本没法给你解答，给你改完就以经全不是你的代码了。 #include<stdio.h>
#include<stdlib.h>
typedef struct Node{
int val;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;
BTNode* insert(BTNode *T, int value, int *father)//T为当前访问的节点，value是待插入节点的键值，father为当前访问节点的父节点的键值
{
if(T == NULL)
{
T = (BTNode*) malloc(sizeof(BTNode));
T -> lchild = NULL;
T -> rchild = NULL;
T -> val = value;
return T;
}
else if(value > T -> val)
{
*father = T -> val;
T -> rchild = insert(T -> rchild, value, father);
}
else
{
*father = T -> val;
T -> lchild = insert(T -> lchild, value, father);
}
return T;
}
int main()
{
BTNode *t = NULL;
int n;
int i;
scanf("%d", &n);//n个节点
int value;
for(i = 0; i < n; i++)
{
int father = -1; //初始化储存的父节点的值
scanf("%d", &value);
t = insert(t, value, &father);
printf("%d\n", father);
}
return 0;
}
重新学习了排序二叉树的构建和函数调用改了一遍终于改出来了，确实是基础超级不行哈，还是得慢慢摸索。我本科生物，只学了数据库技术，对计算机各类语言一点都不了解，考研834数据结构极其简单所以只学了皮毛，复试要笔试算法和机试，前一个多月恶补C语言，现在再写完整代码力不从心，本来就是实操不足哈，再过一个多月就得复试，只能边敲代码便理解了。问的问题确实很蠢，还希望各位不吝赐教哈
页:
[1]