入門題一：
??? 輸入一顆二叉樹，你的任務是按從上到下、從左到右的順序輸出各個節點的值。每個節點都按照從根節點到它的移動序列給出
（L表示左，R表示右）。在輸入中，每個節點的左括號和右括號之間沒有空格，相鄰節點之間用一個空格隔開。每顆樹的輸入用一
對空括號()結束（這對空括號不代表節點）
?? ?注意，如果從根到某個葉節點的路徑上有的節點沒有在輸入中給出，或者給出了超出一次，應到輸出 -1 。節點個數不超過256。
樣例輸入:
?? ?(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
?? ?(3,L) (4,R) ()
樣例輸出:
?? ?5 4 8 11 13 4 7 2 1
?? ?0
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define maxn 256char buf[maxn]; //保存讀入節點
int failed;
int n=0,ans[maxn]; //節點個數和輸出序列 typedef struct Tnode{int have_value; //是有賦過值 int v; //節點值 struct Tnode *left,*right;
}Node;
Node *root; //二叉樹的根節點 Node* newnode()
{Node *tmp=(Node*)malloc(sizeof(Node));if(tmp!=NULL){tmp->have_value=0; //顯示的初始化為0,因為malloc申請內存時并不把它清零tmp->left=tmp->right=NULL; }return tmp;
}void addnode(int value,char *s)
{int length=strlen(s);Node *tmp=root;for(int i=0;i<length;i++){ //索引對應的位置 if('L'==s[i]){if(NULL==tmp->left) tmp->left=newnode();tmp=tmp->left;}else if('R'==s[i]){if(NULL==tmp->right) tmp->right=newnode();tmp=tmp->right;} }if(tmp->have_value) failed=1; //已經賦過值表明輸入有誤 tmp->v=value; tmp->have_value=1;
}int read_input()
{failed=0;root=newnode();for(;;){if(scanf("%s",buf)!=1) return 0; //整個輸入結束if(!strcmp(buf,"()")) break;int v;sscanf(&buf[1],"%d",&v); //讀入節點的值addnode(v,strchr(buf,',')+1); }return 1;
} /* BFS,Breadth-Firsh Search 寬度優先遍歷 */
int bfs()
{int front=0,rear=1;Node* q[maxn];q[0]=root;while(front<rear){Node* tmp=q[front++];if(tmp->have_value==0) return 0;ans[n++]=tmp->v;if(NULL != tmp->left) q[rear++]=tmp->left;if(NULL != tmp->right) q[rear++]=tmp->right;}return 1;
}void remove_tree(Node* u)
{if(NULL==u) return ;remove_tree(u->left);remove_tree(u->right);free(u);
}int main()
{read_input();if(bfs() && !failed){for(int i=0;i<n;i++){printf("%d ",ans[i]);}}else{printf("0\n");}return 0;
}
入門題二：
輸入一顆二叉樹的先序遍歷和中序遍歷，輸出它的后序遍歷序列。
樣例輸入：
?? ??? ?DBACEGF ABCDEFG
?? ??? ?BCAD CBAD
樣例輸出：
?? ??? ?ACBFGED
?? ??? ?CDAB?
#include "stdio.h"
#include "string.h"
#define maxn 20
char preorder[maxn],inorder[maxn],postOrder[maxn]; //先序、中序 和后序 //n樹的節點個數,pre前序，in中序，post后序
void build(int n,char *pre,char *in,char *post)
{if(n<=0) return;int x=strchr(in,pre[0])-in; //找到根節點在中序遍歷中的位置 build(x,pre+1,in,post); //遞歸構造左子樹的后序遍歷 build(n-x-1,pre+x+1,in+x+1,post+x); //遞歸構造右子樹的后序遍歷 post[n-1]=pre[0]; //根節點添加到最后
}int main()
{while(scanf("%s%s",preorder,inorder)==2){int n=strlen(preorder);build(n,preorder,inorder,postOrder); postOrder[n]='\0';printf("%s\n",postOrder); } return 0;
} 
