UC知道二叉树非递归后序遍历
来源：百度知道 编辑：UC知道 时间：2024/06/02 18:35:19
请教下高手我的程序为什么遍历不了，要如何修改啊，（比如输入二叉树数据：abd..e..c..）
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
struct TREE //二叉树结点结构
{
char data;
struct TREE *lsubtree;
struct TREE *Rsubtree;
};
struct TREE *tree;
void createtree(struct TREE *&p) //先序创建二叉树
{
char ch;
ch = getchar();
if (ch == '\n')
{
p = NULL;
}
else if(ch == '.')
p = NULL;
else
{
p = (struct TREE*)malloc(sizeof(struct TREE));//分配结点空间
p->data = ch;
createtree(p->lsubtree); //递归创建左子树
createtree(p->Rsubtree); //递归创建右子树
}
return;
}
void lastorder(TREE *tree)//非递归后序遍历
{
struct TREE *p;
struct TREE *s[100];//用一个指针数组来用作栈
int top=-1;//下标
int mack[100];//标志数组
p=tree;
do
{
while(
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
struct TREE //二叉树结点结构
{
char data;
struct TREE *lsubtree;
struct TREE *Rsubtree;
};
struct TREE *tree;
void createtree(struct TREE *&p) //先序创建二叉树
{
char ch;
ch = getchar();
if (ch == '\n')
{
p = NULL;
}
else if(ch == '.')
p = NULL;
else
{
p = (struct TREE*)malloc(sizeof(struct TREE));//分配结点空间
p->data = ch;
createtree(p->lsubtree); //递归创建左子树
createtree(p->Rsubtree); //递归创建右子树
}
return;
}
void lastorder(TREE *tree)//非递归后序遍历
{
struct TREE *p;
struct TREE *s[100];//用一个指针数组来用作栈
int top=-1;//下标
int mack[100];//标志数组
p=tree;
do
{
while(
你只要后序遍历成功对吧,你的错误真难找,很细微的错误.
错误在下面那个函数:
void lastorder(TREE *tree)//非递归后序遍历
{
struct TREE *p;
struct TREE *s[100];//用一个指针数组来用作栈
int top=-1;//下标
int mack[100];//标志数组
p=tree;
do
{
while(p!=NULL)//循环 直到让p向左滑到最左子树
{ top=top+1;
s[top]=p;//每循环一次，当前结点入栈
mack[top]=1;//结点第一次入栈时，标志为1
p=p->lsubtree;//找最左子树
}
这句就错了,应该是:
while((p->lsubtree)!=NULL)//循环 直到让p向左滑到最左子树
写成你那样的话,p的值这时都成null了,后面还做什么呀?应该是判断p左边还有没有,没有了那p就是最左的了.
是最左的了,那么就该把他打出来,那么下面就该加上
printf("%c\n",p->data);
还有这里:
p=s[top];//出栈顶元素
top=top-1;//每出一个栈顶元素，下标就后退一位
if (mack[top]==1)//若结点是第一次出栈，则再入栈
你让top退了一位,那么下面的判断还是判断这个节点了么?你成判断上个节点了!
所以是
if (mack[top+1]==1)//若结点是第一次出栈，则再入栈
最后呢,while (top!=-1 || p!=NULL); 要知道p不可能为NULL的,你这样会死循环诶!
要不就写成while (top!=-1);
另外指出你的一个bug就是当二叉树为空时,do wile语句是先做再判断的,为空时,
p=s[top];//出栈顶