void inorder(node *root)
{
deque<node*> q;
while(!q.empty())q.pop_front();
node * t = root;
do{
while(t)
{
q.push_back(t);
t = t->lc;
}
t = q.back();
printf("%c ",t->ch);
q.pop_back();
if(t->rc)
{
t = t->rc;
}else t = NULL;
}while(t||(!q.empty()));
}
完整代码如下,这是我在做了广义表建立二叉树后顺便写的中序遍历二叉树,所以输入是广义表
例如:A(B(E(K,L),F),C(D(,H)))
#include <bits/stdc++.h>
using namespace std;
struct node{
char ch;
node *lc,*rc;
};
char s[100];
int flag=0;
int n;
int i=0;
node * build_tree()
{
if(i>=n)
return NULL;
node *p = new node;
p->lc = NULL; p->rc = NULL; p->ch = '0';//初始化
for(;i<n;i++)
{
if(flag)
{
flag = 0;
p->rc = build_tree();
}else if(s[i]=='(')
{
++i;
p->lc = build_tree();
}else if(s[i]==',')
{
flag = 1;
if(p->ch=='0')return NULL;
else return p;
}else if(s[i]>='A'&&s[i]<='Z')
{
p->ch = s[i];
}else if(s[i]==')')
{
return p;
}
}
return p;
}
void inorder(node *root)
{
deque<node*> q;
while(!q.empty())q.pop_front();
node * t = root;
do{
while(t)
{
q.push_back(t);
t = t->lc;
}
t = q.back();
printf("%c ",t->ch);
q.pop_back();
if(t->rc)
{
t = t->rc;
}else t = NULL;
}while(t||(!q.empty()));
}
int main()
{
scanf("%s",s);
n = strlen(s);
node *root = build_tree();
inorder(root);
return 0;
}
//A(B(E(K,L),F),C(D(,H)))