#include <bits/stdc++.h> using namespace std; typedef string ElemType; typedef struct BitNode { ElemType data; struct BitNode *lchild,*rchild; } BitNode,*BiTree; //char sc[10]= {"+-*/"}; void CreateBiTree(BiTree &t) { string ch; cin >> ch; if(ch[0] == '#') t = NULL; else { t = new BitNode; t->data = ch; CreateBiTree(t->lchild); CreateBiTree(t->rchild); } } void InOrderTraverse(BiTree t) { if(t) { string op = t->data; if(op[0]<'0' || op[0]>'9') cout << '('; InOrderTraverse(t->lchild); cout << t->data ; InOrderTraverse(t->rchild); if(op[0]<'0' || op[0]>'9') cout << ')'; } /***********************************/ } int main() { BiTree tree = new BitNode; string ch; while(cin >> ch) { tree->data = ch; CreateBiTree(tree->lchild); CreateBiTree(tree->rchild); InOrderTraverse(tree); printf("\n"); } return 0; }

这段代码是一个表达式树的建立和遍历程序，可以读入一条表达式，以二叉树的形式建立表达式树，并按照中序遍历的顺序输出中缀表达式。具体实现过程是先读入一个字符串作为根节点的值，然后递归读入左子树和右子树，再按照中序遍历的顺序遍历树并输出表达式。其中，如果遍历到运算符节点，则输出括号，以保证正确的优先级顺序。