程序改错:非递归先序遍历二叉树

发布网友 发布时间：2022-05-15 23:27

我来回答

共5个回答

热心网友 时间：2023-11-04 23:02

do
{
////while(p!=null)注意：当跳出循环的时候，p==null,那么下面的p->data访问非法
while(p->lchild)
{
s[top]=p;
top++;
p=p->lchild;
}
////if(top>0)注意，第一次栈空的时候，p指向树根，这时候应该输出树根，并继续遍历右子树
////因此，这个if不恰当
////下面面的语句，基本上算是重新写了,后边有代码分析
printf("%c\t",p->data);//中序遍历，只要没有左孩子就要输出
p=p->rchild;//访问右孩子
if(!p
&&
top>0)
{
////如果p没有右孩子，则是叶子结点，父结点出栈
top--;
p=s[top];
printf("%c\t",p->data);//它的左子树访问完了，输出自身(中序嘛)
p=p->rchild;//开始访问右子树
}
////如果有右孩子，就以它为树根，重新循环
////如果没有右孩子，且栈空(达到了下面一行的退出条件)，说明树遍历完成，不能在进入if语句
}while(top>0||p!=null);
//-------------------------------------------------------------------------------
//------------------------------------------------------------------------------
////对你的代码做一下简要分析，上面提到的就不重复了
do
{
while(p!=null)
{
s[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
printf("%c\t",p->data);
top--;
p=s[top];
p=p->rchild;
}
}while(top>0||p!=null);
////举一个简单的例子，如图
////1
先假设你的while()循环访问正常，如果top改为>=0，那么势必造成top<0时访问s[]，出错
////2
当if语句面的p=s[top]使得a出栈后，如果top>0没改，那么p就进入下一次循环，
////
while()将重新访问a的左孩子，貌似死循环了
////也就是说，你程序上面的错误导致你下面怎么改都不对，而一旦将上面该了，
////整个路线也基本算变了
////当然也可以按照课本p130的算法去改，大同小异

热心网友 时间：2023-11-04 23:02

建好树，用递归遍历试一下，看是否建树函数正确;如果正确，就是非递归遍历函数的问题

热心网友 时间：2023-11-04 23:02

#include<iostream.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 20

typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//创建结点的数据类型

typedef struct {
// BiTNode *base;
// BiTNode *top;
// int stacksize;
BiTree Elem[STACK_INIT_SIZE];
int top;
}SqStack;//存放结点的栈

void InitStack(SqStack &S);//构造空栈
void GetTop(SqStack &S,BiTree &q);//获取栈顶元素
bool StackEmpty(SqStack &S);//判断栈是否为空
void Push(SqStack &S,BiTree &q);//进栈
void Pop(SqStack &S,BiTree &q);//出栈
void CreatBiTree(BiTree &T);//创建二叉树
void PreOrderTraverse(BiTree &T);//非递归先序遍历二叉树

void main()
{
BiTree p;

CreatBiTree(p);
cout<<"先序遍历二叉树的非递归算法结果："<<endl;
SqStack S;//创建存放结点的栈
InitStack(S);
Push(S,p);
while(!StackEmpty(S))
{
while((GetTop(S,p),p))
{
cout<<" "<<p->data;//访问结点
Push(S,p->lchild);//向左走到尽头
}
Pop(S,p);//空指针出栈
if(!StackEmpty(S))
{
Pop(S,p);
Push(S,p->rchild);
}
}
cout<<endl;
}

void CreatBiTree(BiTree &T)
{
char ch;
cout<<"输入一个结点后按回车:"<<endl;
cin>>ch;
if(ch=='@')
T=NULL;
else
{
if(!(T=new BiTNode))
exit(-1);
T->data=ch;
CreatBiTree(T->lchild);
CreatBiTree(T->rchild);
}
}

void InitStack(SqStack &S)
{
// S.base=new BiTNode [STACK_INIT_SIZE];
// if(!S.base) exit(-1);
// S.top=S.base;
// S.stacksize=STACK_INIT_SIZE;
S.top=-1;
}

void GetTop(SqStack &S,BiTree &q){
if(S.top<=-1||S.top>=STACK_INIT_SIZE)
{cout<<"stack is empty";exit(0);}
else
{
q=S.Elem[S.top];
}
}

bool StackEmpty(SqStack &S){
if(S.top==-1)
return true;
else
return false;
}

void Push(SqStack &S,BiTree &q){
if(S.top>=STACK_INIT_SIZE)
{cout<<"stack is full!";exit(1);}
S.Elem[++S.top]=q;
}

void Pop(SqStack &S,BiTree &q){
if(S.top <=-1)
{cout<<"stack is empty!"; exit(-1);}
else
{
q=S.Elem[S.top--];
}
}

热心网友 时间：2023-11-04 23:03

太麻烦......

热心网友 时间：2023-11-04 23:04

学习。。