二叉树遍历（c++代码）.doc

二叉树三种遍历：#include#includeusing namespace std;#define max 100typedef struct btnode char data; struct btnode *lc, *rc; *btree;bool prebtree(char pre, int lp, int rp, char mid, int lm, int rm, btree & t)/前中求后 if (lp rp | lm rm) /范围不对 return false; int len = 0; for (int i=lm; i rm - lm) /数据不对 return false; t = new btnode; t-lc = t-rc = NULL; bool flag = true; if (len 0) /有左孩子 flag = prebtree(pre, lp+1, lp+len, mid, lm, lm+len-1, t-lc); if (flag & len rc); if (flag) t-data = prelp; else delete t; return flag; bool postbtree(char post, int lp, int rp, char mid, int lm, int rm, btree & t)/中后求前 if (lp rp | lm rm) /范围不对 return false; int len = 0; for (int i=lm; i rm - lm) /数据不对 return false; t = new btnode; t-lc = t-rc = NULL; bool flag = true; if (len 0) /有左孩子 flag = postbtree(post, lp, lp+len-1, mid, lm, lm+len-1, t-lc); if (flag & len rc); if (flag) t-data = postrp; else delete t; return flag; void preorder(btree p) if(p != NULL) cout data; preorder(p-lc); preorder(p-rc); void inorder(btree p) if(p != NULL) inorder(p-lc); cout data; inorder(p-rc); void postorder(btree p) if(p != NULL) postorder(p-lc); postorder(p-rc); cout data; int main(int argc, char* argv)int a,i=0;string str1,str2,str3;char premax,midmax,postmax; btree root1, root2;cout请选择已知情况 1.前序中序 2.中序后序a;switch(a)case 1:coutstr1;coutstr2;while(str2i!=0)prei=str1i;midi=str2i;i+; if (prebtree(pre, 0, i-1, mid, 0, i-1, root1) cout后序:; postorder(root1); else cout数据错误; break; case 2:coutstr2;coutstr3;while(str2i!=0)midi=str2i;posti=str3i;i+; if (postbtree(post, 0, i-1, mid, 0, i-1,