二叉树的非递归遍历出问题

linbin0182 发布于 2013/04/15 13:23
阅读 237
收藏 0

@cut 你好,想跟你请教个问题:#include<stdio.h>
#include<stdlib.h>
typedef struct BTree{
int data;
struct BTree *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct {
BiTree top,base;
int length;
}stack;//栈的结构定义
void CreatBinaryTree(BiTree &T)
{//构造一个二叉树(递归定义)
int ch;//以0表示空树
printf("输入结点:");                                                
scanf("%d",&ch);
if(ch==0) T=NULL;//约定值为零的结点为空
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T) exit(1);
T->data=ch;
CreatBinaryTree(T->lchild);//递归
CreatBinaryTree(T->rchild);
}
}
void VistTree(BiTree &T)
{//输出结点
if(T!=NULL)
printf("%d ",T->data);
}
void InitStack(stack &s)
{//初始化一个栈
s.base=(BiTree)malloc((4)*sizeof(BiTNode));
if(!s.base)
exit(1);
s.top=s.base;
s.length=0;
printf("InitStack Successfully!\n");
}
int StackEmpty(stack &s)
{//判断栈是否为空
if(s.length==0||s.base==NULL)
return 0;
else
return  1;
}
void PushStack(stack &s,BiTree &p)//注意参数类型
{//入栈操作
//栈中依次存放的是二叉树中各结点,而且不打乱各结点之间的连接关系
if(s.length>=4)
s.base=(BiTree)realloc(s.base,(4+4)*sizeof(BiTNode));
if(!s.base)
exit(1);
s.top=p;
s.top++;
s.length++;
}
void PopStack(stack &s,BiTree &p)//注意参数类型
{//出栈操作
if(StackEmpty(s))
{
s.top--;
p=s.top;
s.length--;
}
}
void MiddleTree(BiTree &T,stack &S)
{//中序遍历二叉树非递归实现
    BiTree p;
InitStack(S);p=T;
while(p!=NULL||StackEmpty(S))
{
if(p!=NULL)
{
PushStack(S,p);
p=p->lchild;
}
else
{
PopStack(S,p);
VistTree(p);
p=p->rchild;
}
}
}
int main(void)
{
BiTree T;
stack S;
CreatBinaryTree(T);
MiddleTree(T,S);
return 0;
}为什么输入数字1Enter 2Enter 3Enter 0Enter 0Enter 0Enter 0Enter得出的是31然后显示错误啊

加载中
1
ling0
ling0

发表一下个人看法:

同学,你的代码真够乱的,别急着解释,听我说:

首先,你发贴时难道不会用插入代码格式么,你直接贴上的代码真的真不容易看,连个缩进都没有,别告诉我你写的时候就这样(如果真这样,请忽视我这句话)。

其次,你代码写的是 C 还是 C++,我可以肯定你的代码不是 C,因为我不会 C++, 用 C 没有编译通过,至于是不是 C++, 请会 C++ 的帮你看看,不过我看着里面的头引用,printf, scanf, 指针之类的像是 C 语言, 但是那个取地址符是干什么的,我就不清楚了。

再次,说说我能看明白的 C 的部分,你的代码结构,明显,代码里有栈又有树,不能分开写么,分模块你应该知道吧,分开写, 代码也能清楚一些。

再再次,说说你的代码内容,我扫了一遍,你建树的时候,我不知道你用的是什么原则建树,但是,这个树好像没有退出条件,是强制用户输入的程序,你知道,这样的程序调起来就必须输入多少个树结点什么的,你看是不是?

以上,先说这么多, 话比较直接,如果这回复令你很不爽或者你觉得我说得不对,请自觉无视我的回复。

另,@中山野鬼 兄的 C 语言系列很好,里面有很多有用的知识,对于 C 的设计讲的很好,有空你可以看一下。

0
中山野鬼
中山野鬼
把你代码,整整干净,或许问题自然搞定。哈。
linbin0182
linbin0182
很干净啊,不乱的
0
中山野鬼
中山野鬼
void InitStack(stack &s) ,你是c语言还是c++,c++就用c++的代码书写方式,c就用c的。还说不乱?语言就乱用了。。。
linbin0182
linbin0182
嘻嘻,我再看看啊
0
cut
cut

这个不是要自己调才有乐趣的么。

还有建议不要直接遍历,说实话没有任何意义,蛋疼的话去看看神马叫迭代器,使用迭代器模式进行树的遍历,代码可以参考STL的黑红树迭代器的代码。

0
cut
cut
https://github.com/burningsun/pecker_framework.git 这个是我蛋疼的时候写的,在data文件夹里的都是一些数据结构,自己看二叉树的遍历实现,有AVL树的实现和迭代器的遍历实现,三叉字符搜索树的实现和迭代器遍历实现,代码比较乱,怎么用的看vs工程里面testcode的代码,发现什么BUG也可以给我说
返回顶部
顶部