作者cat99961 (阿汤)
看板C_and_CPP
标题[问题] 二元搜寻树插入节点的回圈改递回
时间Mon May 4 17:53:42 2020
我要将二元搜寻树的回圈改成递回(改原程式的insert_node函数)
原程式如下:
#include <stdlib.h>
struct tree /* 树的结构宣告 */
{
int data; /* 节点资料 */
struct tree *left; /* 指向左子树的指标 */
struct tree *right; /* 指向右子树的指标 */
};
typedef struct tree treenode; /* 树的结构新型态 */
typedef treenode *btree; /* 宣告树节点指标型态 */
/* ---------------------------------------- */
/* 插入二元树的节点 */
/* ---------------------------------------- */
btree insert_node(btree root,int value)
{
btree newnode; /* 树根指标 */
btree current; /* 目前树节点指标 */
btree back; /* 父节点指标 */
/* 建立新节点记忆体 */
newnode = ( btree ) malloc(sizeof(treenode));
newnode->data = value; /* 建立节点内容 */
newnode->left = NULL; /* 设定指标初值 */
newnode->right = NULL; /* 设定指标初值 */
if ( root == NULL ) /* 是否是根节点 */
{
return newnode; /* 传回新节点位置 */
}
else
{
current = root; /* 保留目前树指标 */
while ( current != NULL )
{
back = current; /* 保留父节点指标 */
if ( current->data > value ) /* 比较节点值 */
current = current->left; /* 左子树 */
else
current = current->right; /* 右子树 */
}
if ( back->data > value ) /* 接起父子的链结 */
back->left = newnode; /* 左子树 */
else
back->right = newnode; /* 右子树 */
}
return root; /* 传回树根指标 */
}
/* ---------------------------------------- */
/* 建立二元树 */
/* ---------------------------------------- */
btree create_btree(int *data,int len)
{
btree root = NULL; /* 树根指标 */
int i;
for ( i = 0; i < len; i++ ) /* 用回路建立树状结构 */
root = insert_node(root,data[i]);
return root;
}
/* ---------------------------------------- */
/* 二元树後序走访 */
/* ---------------------------------------- */
void postorder(btree ptr)
{
if ( ptr != NULL ) /* 终止条件 */
{
postorder(ptr->left); /* 左子树 */
postorder(ptr->right); /* 右子树 */
printf("[%2d]\n",ptr->data); /* 列印节点内容 */
}
}
/* ---------------------------------------- */
/* 主程式: 建立二元树且用後序走访列印出来. */
/* ---------------------------------------- */
void main()
{
btree root = NULL; /* 树根指标 */
/* 二元树节点资料 */
int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
root = create_btree(data,9); /* 建立二元树 */
printf("树的节点内容 \n");
postorder(root); /* 後序走访二元树 */
}
後来我自己改成递回程式(改了insert_node函数)如下:
#include <stdlib.h>
#include <stdio.h>
struct tree /* 树的结构宣告 */
{
int data; /* 节点资料 */
struct tree *left; /* 指向左子树的指标 */
struct tree *right; /* 指向右子树的指标 */
};
typedef struct tree treenode; /* 树的结构新型态 */
typedef treenode *btree; /* 宣告树节点指标型态 */
/* ---------------------------------------- */
/* 插入二元树的节点 */
/* ---------------------------------------- */
btree insert_node(btree root,int value)
{
btree newnode; /* 树根指标 */
btree current; /* 目前树节点指标 */
btree back; /* 父节点指标 */
/* 建立新节点记忆体 */
newnode = ( btree ) malloc(sizeof(treenode));
newnode->data = value; /* 建立节点内容 */
newnode->left = NULL; /* 设定指标初值 */
newnode->right = NULL; /* 设定指标初值 */
current = root;
if ( root == NULL ) /* 是否是根节点 */
{
return newnode; /* 传回新节点位置 */
}
else if(current->data>value) {
insert_node(current->left,value);
return root;
}
else {;
insert_node(current->right,value);
}
}
/* ---------------------------------------- */
/* 建立二元树 */
/* ---------------------------------------- */
btree create_btree(int *data,int len)
{
btree root = NULL; /* 树根指标 */
int i;
for ( i = 0; i < len; i++ ) /* 用回路建立树状结构 */
root = insert_node(root,data[i]);
return root;
}
/* ---------------------------------------- */
/* 二元树後序走访 */
/* ---------------------------------------- */
void postorder(btree ptr)
{
if ( ptr != NULL ) /* 终止条件 */
{
postorder(ptr->left); /* 左子树 */
postorder(ptr->right); /* 右子树 */
printf("[%2d]\n",ptr->data); /* 列印节点内容 */
}
}
/* ---------------------------------------- */
/* 主程式: 建立二元树且用後序走访列印出来. */
/* ---------------------------------------- */
void main()
{
btree root = NULL; /* 树根指标 */
/* 二元树节点资料 */
int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
root = create_btree(data,9); /* 建立二元树 */
printf("树的节点内容 \n");
postorder(root); /* 後序走访二元树 */
}
但改成递回後，程式结果不一样
请问我哪里错了呢?
我搞了超久了
希望各位高手帮帮忙
拜托拜托拜托拜托拜托拜托拜托拜托拜托拜托拜托拜托
拜托拜托拜托拜托拜托拜托拜托拜托拜托拜托拜托拜托
拜托拜托拜托拜托拜托拜托拜托拜托拜托拜托拜托拜托
拜托拜托拜托拜托拜托拜托拜托拜托拜托.....
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.42.19.41 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1588586024.A.B65.html
1F：推 firejox: 没接上回传的结点当然会失败 05/04 18:34
2F：推 firejox: 你是用指标不是用参考，所以需要加上赋值 05/04 18:37
感谢你!但可能是我学得不好，是否要改写insert_node(current->left,value)这句呢?我不知道这句要怎麽改才能有结果可以帮帮我吗?
※ 编辑: cat99961 (114.42.19.41 台湾), 05/04/2020 21:25:53
3F：推 elysium5290: 楼上正解，你改写递回但你递回的部分怎麽会没有处理r 05/05 13:04
4F：→ elysium5290: eturn node呢？ 05/05 13:04
5F：推 firejox: current->left= insert_node(current->left,value) 这样 05/05 17:24
6F：推 elysium5290: 稍微回一下大概 05/05 18:35
7F：→ elysium5290: btree insert_node(btree root, int value) 05/05 18:35
8F：→ elysium5290: { 05/05 18:35
9F：→ elysium5290: if(NULL != root){ 05/05 18:35
10F：→ elysium5290: If(root->data > value) 05/05 18:35
11F：→ elysium5290: root->left = insert_node(root->left 05/05 18:35
12F：→ elysium5290: , value); 05/05 18:35
13F：→ elysium5290: else 05/05 18:35
14F：→ elysium5290: root->right = insert_node(root->rig 05/05 18:35
15F：→ elysium5290: ht, value); 05/05 18:35
16F：→ elysium5290: return root; 05/05 18:35
17F：→ elysium5290: } 05/05 18:35
18F：→ elysium5290: else{ 05/05 18:35
19F：→ elysium5290: btree newnode; 05/05 18:35
20F：→ elysium5290: //以下大概 05/05 18:35
21F：→ elysium5290: newnode = malloc() 05/05 18:35
22F：→ elysium5290: return newnode; 05/05 18:35
23F：→ elysium5290: } 05/05 18:35
24F：→ elysium5290: } 05/05 18:35
太感谢了!!我做出来了@@~~太热心了....弄了超久的...我要来好好地把我一些基础给搞好
※ 编辑: cat99961 (114.42.19.41 台湾), 05/05/2020 23:39:30