大家好，我在写C语言代码，非递归实现二叉树后序遍历过程中遇到了问题。用的是.c，不是.cpp。就是一直循环输出其中一个元素！以下是代码：
BiTreeH.h文件：
//二叉树结构体
typedef struct BT{
DataType data;
struct BT *lchild;
struct BT *rchild;
}BiNode,*BiTree;
//栈结构体
#define MAXSIZE 100
typedef struct Stack{
BiNode data1[MAXSIZE];
int top;
}StackList;
//访问结点
void Visit(DataType d){
printf("%c\n",d);
}
//栈初始化
void InitiateStack(StackList *s){
s->top = 0;
}
//入栈
void InStack(StackList *s,BiNode *p){
if(s->top == MAXSIZE){
printf("栈已满，无法入栈！\n");
}else{
s->data1[s->top] = *p;
s->top++;
}
}
//出栈
void OutStack(StackList *s,BiNode **p){
if(s->top == 0){
printf("栈已空，无法出栈！\n");
}else{
s->top--;
*p = &s->data1[s->top];/非常重要/
}
}
//获取栈顶元素
void StackGetTop(StackList *s,BiNode **p){
if(s->top == 0){
printf("栈已空，无法获取！\n");
}else{
*p = &s->data1[s->top - 1];
}
}
//非空否
int NotEmpty(StackList s){
if(s.top == 0)
return 0;
else
return 1;
}
//先序法创建二叉树
void PreCreatTree(BiTree *root){
char x;
x = getchar();
if(x == '6')*root = NULL;
else{
(*root) = (BiTree)malloc(sizeof(BiNode));
(*root)->data = x;
PreCreatTree(&(*root)->lchild);
PreCreatTree(&(*root)->rchild);
}
}
//先序遍历
void PreOrder(BiTree root){
StackList s;
BiNode p;
InitiateStack(&s);
p = root;
while(p != NULL || NotEmpty(s)){
while(p != NULL){
Visit(p->data);
InStack(&s,p);
p = p->lchild;
}
if(NotEmpty(s)){
OutStack(&s,&p);
p = p->rchild;
}
}
}
//中序遍历
void MidOrder(BiTree root){
BiTree p;
StackList s;
InitiateStack(&s);
p = root;
while(p != NULL || NotEmpty(s)){
while(p != NULL){
InStack(&s,p);
p = p->lchild;
}
if(NotEmpty(s)){
OutStack(&s,&p);
Visit(p->data);
p = p->rchild;
}
}
}
//后序遍历
void PostOrder(BiTree root){
StackList s;
BiTree p,q;
InitiateStack(&s);
p = root;q = NULL;
while(p != NULL || NotEmpty(s)){
while(p != NULL){
InStack(&s,p);
printf("%c入栈了！\n",p->data);
p = p->lchild;
}
if(NotEmpty(s)){
StackGetTop(&s,&p);
printf("%c\n",p->data);
system("pause");
if(p->rchild == NULL || p->rchild == q){
OutStack(&s,&p);
printf("%c出栈了！\n",p->data);
Visit(p->data);
q = p;
printf("q为：%c\n",q->data);
p = NULL;
}else{
p = p->rchild;
printf("11111111111\n");
}
}
}
}
//求结点个数(用后序遍历)
int NodeNumber(BiTree root){
StackList s;BiTree p,q;
int Count;
Count = 0;
p = root;q = NULL;
InitiateStack(&s);
while(p != NULL || NotEmpty(s)){
while(p != NULL){
InStack(&s,p);
p = p->lchild;
}
if(NotEmpty(s)){
if(p->rchild == NULL || p->rchild == q){
OutStack(&s,&p);
Count++;
q = p;
p = NULL;
}else
p = p->rchild;
}
}
return Count;
}
//求树的高度(用中序遍历)
int TreeHeight(BiTree root){
StackList s;
int h;int max;
BiTree p;
p = root;
h = 0;max = 0;
InitiateStack(&s);
while(p != NULL || NotEmpty(s)){
while(p != NULL){
InStack(&s,p);
h++;if(h>max)max = h;
p = p->lchild;
}
if(NotEmpty(s)){
OutStack(&s,&p);
h--;
p = p->rchild;
}
}
return max;
}
//打印二叉树
Main.c文件：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef char DataType;
#include"BiTreeH.h"
void test01(){
int h;int Count;
BiTree Bi;
//先序创建//
PreCreatTree(&Bi);
//先序遍历
PreOrder(Bi);
//中序遍历
MidOrder(Bi);
//后序遍历
PostOrder(Bi);
//统计结点个数
Count = NodeNumber(Bi);
printf("结点个数为：%d\n",Count);
//求二叉树高度
h = TreeHeight(Bi);
printf("二叉树高度为：%d\n",h);
//打印二叉树
//PrintTree(Bi,h);
}
int main(){
test01();
return 0;
}
文章不让重复用#，我就用汉字代替，烦请测试的时候稍微修改一下
测试案例是：ABD6G666CE6H66F66
以下是运行结果（我用system("pause")隔开了），有一些检测的语句没有删除，如printf啥的：
我肯定的是问题出现在函数void PostOrder(BiTree root)的里面，具体在
if(p->rchild == NULL || p->rchild == q){
OutStack(&s,&p);
printf("%c出栈了！\n",p->data);
Visit(p->data);
q = p;
printf("q为：%c\n",q->data);
p = NULL;
}else{
p = p->rchild;
printf("*111111*\n");
}
里面，第二次循环的时候，p应该等于q，但是不知道为什么不等。所以就跳过了一步，应该和结构体的传参有关系！
感谢各位帮助
