include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

define MaxNodeNum 100

typedef struct bitnode{
char data;
struct bitnode lchild,rchild;
}bitnode,bitree;
void createbitree(bitree& bt,int &n,char pre[]){
char c=pre[n];
if(c==’#’){
bt=NULL;
return;
}
n+=1;
bt=(bitnode )malloc(sizeof(bitnode));
bt->data=c;
createbitree(bt->lchild,n,pre);
n+=1;
createbitree(bt->rchild,n,pre);
}
void inorder(bitree bt){
//这里我使用非递归算法
bitnode * stack[MaxNodeNum];//初始化栈
int top=0;//指向可以插入的位置
bitnode * p=bt;
while(p!=NULL||top>0){//非递归就是要么入栈要么出栈
if(p!=NULL){
stack[top++]=p;
p=p->lchild;
}
else
{
p=stack[–top];
cout<[HTML_REMOVED]data<<’ ‘;
p=p->rchild;//这里合并两种情况，应该判断r,然后决定p的值，但是都一样
}
}
}
int main(){
bitree p;
char pre[]={‘a’,’b’,’d’,’#’,’#’,’e’,’#’,’g’,’#’,’#’,’c’,’f’,’#’,’#’,’#’};
int m=0;
int& n = m;
createbitree(p,n,pre);
//dbegafc正确的中序遍历序列
inorder(p);
free(p);

}