一段二叉树非递归先序遍历的程序请高手查错

一段二叉树遍历，总是不能输出正确结果，debug的时候指出错误在p=p->rchild这里，请高手帮忙看看是怎么回事，拜谢
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream.h>

const int STACK_INIT_SIZE=100;
const int OK=1;
const int ERROR=0;

typedef enum PointerTag{Link,Thread};

typedef struct BiThrNode
{
int data;
struct BiThrNode *lchild,*rchild,*parent;
PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;

typedef struct SqStackptr
{
BiThrTree base;
BiThrTree top;
int stacksize;
}SqStackptr;

void InitStackptr(SqStackptr &s)
{
s.base=(BiThrTree)malloc(STACK_INIT_SIZE*sizeof(BiThrNode));
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
}

int StackEmptyptr(SqStackptr &s)
{
if(s.base==s.top)
  return OK;
return ERROR;
}

int Pushptr(SqStackptr &s,BiThrTree e)
{
s.top=e;
s.top++;
return OK;
}

int Popptr(SqStackptr &s,BiThrTree e)
{
s.top--;
e=s.top;
return OK;
}

int GetTopptr(SqStackptr s,BiThrTree e)
{
if(s.top==s.base)
  return ERROR;
e=s.top-1;
return OK;
}

void visit(BiThrTree p)
{
cout<<p->data<<endl;
}

BiThrTree pre;

//建立二叉树
void CreateBiTree(BiThrTree &t)
{
int data;
printf("Please input the node.\n");
scanf("%d",&data);
if(data==0)
  t=NULL;
else
{
  t=(BiThrTree)malloc(sizeof(BiThrNode));
  t->data=data;
  t->LTag=Link;
  t->RTag=Link;
  CreateBiTree(t->lchild);
  CreateBiTree(t->rchild);
}
}

//先序遍历
void PreOrderTraverse(BiThrTree t)
{
//非递归算法
SqStackptr s;
InitStackptr(s);
BiThrTree p;
p=t;
while(p||!StackEmptyptr(s))
{
  if(p)
  {
   //根指针进栈，遍历左子树
   visit(p);
   Pushptr(s,p);
   p=p->lchild;
  }
  else
  {
   //根指针退栈，遍历右子树
   Popptr(s,p);
p=p->rchild;
  }
}
}

8 个解决方案

#1

没有高手能帮忙看看吗？我估计就是在建栈上的问题

#2

编译通不过啊，好多错误，我也不知道了，up一下，关注

#3

你的Stack实现有误.
int Pushptr(SqStackptr &s,BiThrTree e)
{
s.top=e;
s.top++;
return OK;
}
对s.top赋值后,加1，然后减去1，不可能恢复成s.base了。
因为s.top = e, 然后s.top++, 然后s.top--，这是s.top等于刚才赋的e,不可能回到e.base了

#4

//更改后的Stack如下
typedef struct SqStackptr
{
BiThrTree *base;
BiThrTree *top;
int stacksize;
}SqStackptr;

void InitStackptr(SqStackptr &s)
{
s.base=(BiThrTree*)malloc(STACK_INIT_SIZE*sizeof(BiThrNode*));
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
}

int StackEmptyptr(SqStackptr &s)
{
if(s.base==s.top)
return OK;
return ERROR;
}

int Pushptr(SqStackptr &s,BiThrTree e)
{
*(s.top)=e;
s.top++;
return OK;
}

int Popptr(SqStackptr &s,BiThrTree &e)
{
s.top--;
e=*(s.top);
return OK;
}

int GetTopptr(SqStackptr s,BiThrTree &e)
{
if(s.top==s.base)
return ERROR;
e=*(s.top-1);
return OK;
}

#5

因为你保存的是BiThrTree,申请的内存是BiThrTree*,不是BiThrTree
用*BiThrTree来保存数据，用BiThrTree来作为游标。

#6

按照你写的，我改了，似乎还是没有解决问题哦

#7

因为你保存的是BiThrTree,申请的内存是BiThrTree*,不是BiThrTree
用BiThrTree来保存数据，用BiThrTree*来作为游标。

更改一下
void InitStackptr(SqStackptr &s)
{
s.base=(BiThrTree*)malloc(STACK_INIT_SIZE*sizeof(BiThrNode));
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
}

#8

我试了可以的。
你的测试数据是什么？我的测试数据为
10 15 20 0 0 25 0 0 18 19 0 0 31 0 0 输一个数字按一下回车
输出为
10 15 20 25 18 29 31
显然是先序遍历

完整的代码如下
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream.h>
#include <string.h>

const int STACK_INIT_SIZE=100;
const int OK=1;
const int ERROR=0;

typedef enum PointerTag{Link,Thread};

typedef struct BiThrNode
{
int data;
struct BiThrNode *lchild,*rchild,*parent;
PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;

typedef struct SqStackptr
{
BiThrTree *base;
BiThrTree *top;
int stacksize;
}SqStackptr;

void InitStackptr(SqStackptr &s)
{
s.base=(BiThrTree*)malloc(STACK_INIT_SIZE*sizeof(BiThrNode));
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
}

int StackEmptyptr(SqStackptr &s)
{
if(s.base==s.top)
  return OK;
return ERROR;
}

int Pushptr(SqStackptr &s,BiThrTree e)
{
*(s.top)=e;
s.top++;
return OK;
}

int Popptr(SqStackptr &s,BiThrTree &e)
{
s.top--;
e=*(s.top);
return OK;
}

int GetTopptr(SqStackptr s,BiThrTree &e)
{
if(s.top==s.base)
  return ERROR;
e=*(s.top-1);
return OK;
}

void visit(BiThrTree p)
{
cout<<p->data<<endl;
}

BiThrTree pre;

//建立二叉树
void CreateBiTree(BiThrTree &t)
{
int data;
printf("Please input the node.\n");
scanf("%d",&data);
if(data==0)
  t=NULL;
else
{
  t=(BiThrTree)malloc(sizeof(BiThrNode));
  t->data=data;
  t->LTag=Link;
  t->RTag=Link;
  CreateBiTree(t->lchild);
  CreateBiTree(t->rchild);
}
}

//先序遍历
void PreOrderTraverse(BiThrTree t)
{
//非递归算法
SqStackptr s;
InitStackptr(s);
BiThrTree p;
p=t;
while(p||!StackEmptyptr(s))
{
  if(p)
  {
   //根指针进栈，遍历左子树
   visit(p);
   Pushptr(s,p);
   p=p->lchild;
  }
  else
  {
   //根指针退栈，遍历右子树
   Popptr(s,p);
p=p->rchild;
  }
}
}

void inOrder(BiThrTree root)
{
if (root)
{
inOrder(root->lchild);
cout << root->data << endl;
inOrder(root->rchild);
}
}

int main()
{
BiThrTree root;
CreateBiTree(root);
PreOrderTraverse(root);
return 0;
}

#1