題目1184：二叉樹遍歷時間限制：1 秒 內存限制：32 兆 特殊判題：否 提交：1562 解決：621 題目描述： 編一個程序，讀入用戶輸入的一串先序遍歷字符串，根據此字符串建立一個二叉樹（以指針方式存儲）。 例如如下的先序遍歷字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹。建立起此二叉樹以後，再對二叉樹進行中序遍歷，輸出遍歷結果。 輸入： 輸入包括1行字符串，長度不超過100。 輸出： 可能有多組測試數據，對於每組數據， 輸出將輸入字符串建立二叉樹後中序遍歷的序列，每個字符後面都有一個空格。 每個輸出結果占一行。 樣例輸入： abc##de#g##f###樣例輸出： c b e g d f a 來源： 2002年華中科技大學計算機研究生機試真題 [cpp] /********************************* * 日期：2013-3-7 * 作者：SJF0115 * 題號: 九度OJ 題目1184：二叉樹遍歷 * 來源：http://ac.jobdu.com/problem.php?pid=1184 * 結果：AC * 來源：2002年華中科技大學計算機研究生機試真題 * 總結： **********************************/ #include<stdio.h> #include<stdlib.h> #include<string.h> char array[101]; //二叉樹結點 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //按先序序列創建二叉樹 int CreateBiTree(BiTree &T,int &index,int &n){ if(index == n){ return 0; } //按先序次序輸入二叉樹中結點的值（一個字符），‘#’表示空樹 if(array[index] == '#'){ T = NULL; index++; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //生成根結點 T->data = array[index]; index++; //構造左子樹 CreateBiTree(T->lchild,index,n); //構造右子樹 CreateBiTree(T->rchild,index,n); } return 0; } //輸出 void Visit(BiTree T){ if(T->data != '#'){ printf("%c ",T->data); } } //中序遍歷 int InOrder(BiTree T){ if(T != NULL){ //訪問左子結點 InOrder(T->lchild); //訪問根節點 Visit(T); //訪問右子結點 InOrder(T->rchild); } return 0; } int main() { int len,index; while(scanf("%s",array) != EOF){ BiTree T; len = strlen(array); index = 0; //創建二叉樹 CreateBiTree(T,index,len); //中序遍歷 InOrder(T); printf("\n"); } return 0; } /********************************* * 日期：2013-3-7 * 作者：SJF0115 * 題號: 九度OJ 題目1184：二叉樹遍歷 * 來源：http://ac.jobdu.com/problem.php?pid=1184 * 結果：AC * 來源：2002年華中科技大學計算機研究生機試真題 * 總結： **********************************/ #include<stdio.h> #include<stdlib.h> #include<string.h> char array[101]; //二叉樹結點 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //按先序序列創建二叉樹 int CreateBiTree(BiTree &T,int &index,int &n){ if(index == n){ return 0; } //按先序次序輸入二叉樹中結點的值（一個字符），‘#’表示空樹 if(array[index] == '#'){ T = NULL; index++; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //生成根結點 T->data = array[index]; index++; //構造左子樹 CreateBiTree(T->lchild,index,n); //構造右子樹 CreateBiTree(T->rchild,index,n); } return 0; } //輸出 void Visit(BiTree T){ if(T->data != '#'){ printf("%c ",T->data); } } //中序遍歷 int InOrder(BiTree T){ if(T != NULL){ //訪問左子結點 InOrder(T->lchild); //訪問根節點 Visit(T); //訪問右子結點 InOrder(T->rchild); } return 0; } int main() { int len,index; while(scanf("%s",array) != EOF){ BiTree T; len = strlen(array); index = 0; //創建二叉樹 CreateBiTree(T,index,len); //中序遍歷 InOrder(T); printf("\n"); } return 0; }
