數據結構實驗之二叉樹五：層序遍歷 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic PRoblem Description
已知一個按先序輸入的字符序列，如abd,,eg,,,cf,,,(其中,表示空結點)。請建立二叉樹并求二叉樹的層次遍歷序列。 Input
輸入數據有多行，第一行是一個整數t (t<1000)，代表有t行測試數據。每行是一個長度小于50個字符的字符串。 Output
輸出二叉樹的層次遍歷序列。 Example Input
2 abd,,eg,,,cf,,, xnl,,i,,u,, Example Output
abcdefg xnuli Hint
#include <stdio.h>#include <string.h>int i;typedef struct node{ char data; struct node *l,*r;}node;node *create(char *str)//老樣子，先序植樹{ node *root; if(str[i]==','){ i++; root = NULL; } else{ root = (node *)malloc(sizeof(struct node)); root->data = str[i++]; root->l = create(str); root->r = create(str); } return root;}void *level_tra(node *root)//這里層序遍歷就有門道了{ node *temp[100];//用temp結點數組來臨時存儲根 int in = 0,out = 0; temp[in++] = root;//temp[0]存根 while(in>out){ if(temp[out]){ printf("%c",temp[out]->data);//輸出根的時候，把這個跟的左節點和右節點先存一下，這樣就達到層序遍歷的目的啦 temp[in++] = temp[out]->l; temp[in++] = temp[out]->r; } out++; }}int main(){ int t; char str[100]; node *root; while(~scanf("%d",&t)){ while(t--){ i = 0; scanf("%s",str); root = create(str); level_tra(root); printf("/n"); } } return 0;}新聞熱點
疑難解答
