还是二叉树的插入、删除子树问题

剑麟 发布于 2012/05/01 22:31
阅读 554
收藏 1
#include <stdio.h>
#include <stdlib.h>
typedef struct bitnode
{
char data;
struct bitnode *lchild, *rchild;
} BiTNode, *BiTree;
BiTree Initiate();
BiTree Insert_L(BiTree bt, char x, BiTree parent);
void PreOrder_0(BiTree bt);
void CreateBinTree(BiTree *T);
void PreOrder(BiTree bt);
int i,n;
BiTree parent;
BiTree Initiate()                           //带头结点的空二叉树
{
BiTNode *bt;
bt=(BiTNode*)malloc(sizeof(BiTNode));
bt->lchild=NULL;
bt->rchild=NULL;
return bt;
}
BiTree Insert_L(BiTree bt, char x, BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\n插入错误");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->lchild==NULL)
parent->lchild=p;
else
{
p->lchild=parent->lchild;
parent->lchild=p;
}
return bt;
}
void PreOrder_0(BiTree bt)        //查找parent函数
{
i++;
if(bt==NULL)
return;
    if(i==n)                     //关键是这里,明明设置了结束子程序条件,可就是对右子树无效。
{
parent=bt;
return;
}
PreOrder_0(bt->lchild);
PreOrder_0(bt->rchild);
}
void CreateBinTree(BiTree *T)
{
char a;
scanf("%c",&a);
getchar();
if(a=='0')
(*T)=NULL;
else
{
(*T)=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->data=a;
CreateBinTree(&((*T)->lchild));
CreateBinTree(&((*T)->rchild));
}
}
void PreOrder(BiTree bt)
{
if(bt==NULL)
return;
    printf("%c ",bt->data);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
void main()
{
char x;
BiTree bt;
bt=Initiate();
if(bt)
{
printf("请输入二叉树元素:");
CreateBinTree(&bt);
printf("二叉树的先序遍历为:");
        PreOrder(bt);
printf("\n");
printf("输入要作为父节点所在的位置:");
scanf("%d",&n);
i=0;
        PreOrder_0(bt);
getchar();
printf("输入要插入的元素:");
scanf("%c",&x);
        Insert_L(bt, x, parent);
        PreOrder(bt);
printf("\n");
}
} 
我今天写了个这样的插入程序,可是不知为什么,只对整颗树的左子树可以插入,右子树总是失败,找来找去都找不到原因。

以下是问题补充:

@剑麟:void PreOrder_0(BiTree bt) { i++; if(bt==NULL) return; if(i==n) //关键是这里,明明设置了结束子程序条件,可就是对右子树无效。 { parent=bt; return; } PreOrder_0(bt->lchild); PreOrder_0(bt->rchild); } 关键是这部分。比如一颗二叉树的先序:ABDCEF,中序:DBAECF;我的程序是想,根据先序的顺序,输入要作为父节点的元素在先序中的位置,然后用PreOrder_0() 函数来找出这个元素。 例如我要把B作为parent,它在先序中的位置为n=2,然后用 i 来计算循环次数,从而找出parent。 可是不知为什么,对C\E\F 这种元素却没效,很是头疼! (2012/05/01 22:39)
加载中
0
中山野鬼
中山野鬼
你等10分钟。我把电脑切到ubuntu下,给你看一下。
0
中山野鬼
中山野鬼
我看了下代码 ,不在编辑器里,还真没感觉。你的错误在于 CreateBinTree 函数里。你这样操作,只能保证你前面连续的输入都存放在当前结点和左子树里。除非你有很多个输入字符“0”在你有效字符之间。也就是说。你想把 1,2,3,4,5,6,7放在三层的二叉树里面你的输入应该是 1,2,4,0,5,0,3,6,0,7,0
剑麟
剑麟
我输入测试数据为: A B D 0 0 0 C E 0 0 F 0 0 把A B D 作为parent 出入插入函数都可以成功,但对于 C E F 这种元素 却失败,传入的parent竟然是空。 我调试了一遍,发现问题在 PreOrder_0( ) 这个函数,比如要 C 做parent,输入 n = 4,当 i 增加到4时,尽然不能 return bt 回来,而是继续运行。 很是诡异。
剑麟
剑麟
我输入元素时,也是这样输入的,把0当作空
0
中山野鬼
中山野鬼
另外你还有个错误。init时对根malloc了,但是你在 create时,又malloc一遍。空间有泄漏。
剑麟
剑麟
我刚才试了一下,任意去掉了其中一个 malloc ,都运行不了,不知为什么
0
中山野鬼
中山野鬼
A B D 0 0 0 C E 0 0 F 0 0 按照你的逻辑,会这样存放。 A,B,D会存放在BT的左侧叶子,A在BT自身。但你 000三个了。所以会跳到 BT的兄弟结点上,开始折腾后面的。所以你在BT结点下面查找自然找不到。我的输入,和你的输入不一样,不要说,你也是这样输入的。。。。
中山野鬼
中山野鬼
回复 @剑麟 : 你还没有递归函数的概念。你跟踪下create函数。搞清楚连续的0究竟发生了什么。你甚至可在create函数里打印信息,在每次create 调用create前,打印是L还是R。
剑麟
剑麟
是吗?因为我还不是很懂,所以都不知道该怎样去写那程序和测试数据。 按你说,也就是我的测试数据的问题,不是函数问题,是这样吗? @红薯
返回顶部
顶部