关于网友提出的“ 二叉树遍历中序”问题疑问，本网通过在网上对“ 二叉树遍历中序”有关的相关答案进行了整理，供用户进行参考，详细问题解答如下：
问题： 二叉树遍历中序描述:
#include
#include
# define ERROR -2
#define OK 1
# define SIZE 100
#define SIZE_IN 10
typedef int Status ;
typedef struct
{
int * base;
int * top;
int sizebase;
}Stack;
typedef struct Node
{
char data;
struct Node * lchild;
struct Node * rchild;
}BTNode;
Status InitStack(Stack &S)
{
S.base=(int *)malloc(SIZE*sizeof(int));
if(!S.base)
return ERROR;
S.top=S.base=0;
S.sizebase = SIZE;
return OK;
}
int EmptyStack(Stack S)
{
if(S.top == S.base)
return 1;
else return 0;
}
int Push(Stack &S,BTNode B)
{
if(S.top -S.base>=S.sizebase)
{
S.base = (int *)realloc(S.base,S.sizebase+(SIZE+SIZE_IN)*sizeof(int));
if(!S.base)
return 0;
(S).top=(S.sizebase)+(S.base);
S.sizebase= S.sizebase+SIZE_IN;
}
S.top++;
*S.top = (int)B.data;
}
int Pop(Stack &S,BTNode B)
{
if(S.top - S.base == 0)
return 0;
S.top --;
B.data=(char)*S.top;
return 1;
}
Status Create_BTNode(BTNode *T)
{
char ch;
scanf("%c",&ch);
if(ch == '#')
T == NULL;
else {
T = (BTNode *)malloc(sizeof(BTNode));
//分配内存
T->data = ch;//把ch付给data；
if(!T)
return ERROR;
Create_BTNode(T->lchild);//利用递归分别建立左右子树
Create_BTNode(T->rchild);
}
return OK;
}
void MidOrderTraverse(BTNode * B)
{
Stack S;
InitStack(S);
while(B || !EmptyStack(S))
{
if(B)
{
Push(S,B);
B=B->lchild;//86
}else{
Pop(S,B);
printf("%c",B->data);
B=B->rchild;//89
}
}
}
int main()
{
return 0;
}
D:\数据结构\BinaryTree\main.cpp:86: error: conversion from 'BTNode*' to non-scalar type 'BTNode' requested
D:\数据结构\BinaryTree\main.cpp:89: error: conversion from 'BTNode*' to non-scalar type 'BTNode' requested
这个是怎么回事，我看不出错误，谢谢大神，还有.和->有什么区别呀，还有我使用的形参是&的话，使用->就会说error，说木有指针，但是用.就对了，帮我看看吧大神，谢谢啦
解决方案1:
根据你代码改后如下：
#include
#include
# define ERROR -2
# define OK 1
# define SIZE 100
# define SIZE_IN 10
typedef int Status ;
typedef struct Node
{
char data;
struct Node * lchild;
struct Node * rchild;
}BTNode;
typedef struct
{
BTNode ** base;
BTNode ** top;
int sizebase;
}Stack;
Status InitStack(Stack &S)
{
S.base=(BTNode **)malloc(SIZE*sizeof(BTNode*));
if(!S.base)
return ERROR;
S.top=S.base;
S.sizebase = SIZE;
return OK;
}
int EmptyStack(Stack S)
{
if(S.top == S.base)
return 1;
else return 0;
}
int Push(Stack &S,BTNode *B)
{
if(S.top -S.base>=S.sizebase)
{
S.base = (BTNode **)realloc(S.base,S.sizebase+(SIZE+SIZE_IN)*sizeof(BTNode *));
if(!S.base)
return 0;
(S).top=(S.sizebase)+(S.base);
S.sizebase= S.sizebase+SIZE_IN;
}
*S.top = B;
S.top++;
return 1;
}
int Pop(Stack &S,BTNode **B)
{
if(S.top - S.base == 0)
return 0;
S.top --;
*B=*S.top;
return 1;
}
//建立二叉树，二叉树最好全部用c
Status Create_BTNode(BTNode **T)
{
char ch;
scanf("%c",&ch);
if(ch == '#')
*T = NULL;
else {
*T = (BTNode *)malloc(sizeof(BTNode));
//分配内存
(*T)->data = ch;//把ch付给data；
if(!T)
return ERROR;
Create_BTNode(&((*T)->lchild));//利用递归分别建立左右子树
Create_BTNode(&((*T)->rchild));
}
return OK;
}
//二叉树遍历中序输出，非递归
void MidOrderTraverse(BTNode * B)//因为是*B，因此入栈是*B而不是B，B是个地址，因此加上*B
{
Stack S;
InitStack(S);
while(B || !EmptyStack(S))
{
if(B)
{
Push(S,B);
B=B->lchild;
}else{
Pop(S,&B);
printf("%c",B->data);
B=B->rchild;
}
}
}
int main()
{
BTNode * root;
Create_BTNode(&root);
MidOrderTraverse(root);
system("pause");
return 0;
}
Status Create_BTNode(BTNode *T) 如果函数中要想改变T所指向的值，可以；如果是想改变T本身，做不到 因此改为Status Create_BTNode(BTNode **T)
还有其他地方有错，自己对照着看 解决方案2:
#include
#include
#include
#define NULL 0
typedef struct tree{
char Data;
struct tree *left,*right;
}*Bitree;
Bitree create(Bitree T)
{
char ch;
scanf("%c",&ch);
if(ch=='#')//输入#号表示空
{
T=NULL;
}
else
{
if(!(T=(Bitree )malloc(sizeof(Bitree))))
{
printf("错误!\n");
}
T->Data=ch;
T->left=create(T->left);
T->right=create(T->right);
}
return T;
}
void xianxu(Bitree T)
{
if(T)
{
printf("%c",T->Data);
xianxu(T->left);
xianxu(T->right);
}
}
void zhongxu(Bitree T)
{
if(T)
{
zhongxu(T->left);
printf("%c",T->Data);
zhongxu(T->right);
}
}
void houxu(Bitree T)
{
if(T)
{
houxu(T->left);
houxu(T->right);
printf("%c",T->Data);
}
}
void main()
{
Bitree T;
T=create(T);
xianxu(T);
printf("\n");
zhongxu(T);
printf("\n");
houxu(T);
printf("\n");
}
非递归先中后的遍历算法
C/C++ code
//1.先序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
//2.中序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //访问根结点
p=p->rchild; //通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
//3.后序遍历非递归算法
#define maxsize 100
typedef enum{L,R} tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;
typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;
void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;
do
{
while (p!=null) //遍历左子树
{
x.ptr = p;
x.tag = L; //标记为左子树
push(s,x);
p=p->lchild;
}
while (!StackEmpty(s) && s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec