問題 I(1186): 【基礎(chǔ)算法】以先序字符串方式建立二叉樹

時間限制:?1 Sec??內(nèi)存限制:?64 MB

題目描述

輸入一個二叉樹的先序串，輸出其后序遍歷結(jié)果。如果結(jié)點(diǎn)的子樹為空，先序串的對應(yīng)位置為空格符。

輸入

第1行：先序串（結(jié)點(diǎn)數(shù)≤26，以單個大寫字母表示）

輸出

第1行：后序序列

樣例輸入

Copy?(如果復(fù)制到控制臺無換行，可以先粘貼到文本編輯器，再復(fù)制)

AB C D

樣例輸出

CBDA

提示

#------------------------------------------------------------------------------#
乍一看，貌似與以括號形式輸出二叉樹差不多，事實上，差得挺多……
括號輸出是不需要建樹的，而這道題現(xiàn)在（注意這里）是需要建樹的，于是我們便開始建樹。 把代碼變成一段一段的顯然不是我的風(fēng)格，所以先講思路。 首先肯定要存當(dāng)前節(jié)點(diǎn)的左兒子和右兒子（結(jié)構(gòu)體）。 輸入字符串后，開始遞歸，如果當(dāng)前節(jié)點(diǎn)沒有左兒子，就把這個字符放到左兒子里，反之，再右兒子里，然后，只要當(dāng)前字符不為空格，就繼續(xù)遞歸。
這里要牽扯到字母，用一般的數(shù)組下標(biāo)很麻煩，于是我又借此裝了個逼——map數(shù)組上場 如果知道m(xù)ap的朋友可以跳過此處，這里大概講講map： map其實是一種映射（不要問我映射是什么，我反正直接理解為儲存），它的下標(biāo)可以為任何變量——字符類，字符串（string）類，普通的數(shù)字，甚至結(jié)構(gòu)體都行，它儲存（我不說映射了）的內(nèi)容也可以是任何變量。 就這樣。 頭文件： #include<map> using namespace std; 聲明方式： map <下標(biāo)，儲存類型> 數(shù)組名;
如： map <string,int> a; 這樣的話就可以這樣用： string x[10]; for(...) { cin>>x[i]; map[x[i]]=1; }
就是這樣了，關(guān)于map還有很多類似于find之類的函數(shù)很好用，以后再說吧
好了，建樹就說完了，后序就不想說了，當(dāng)然注意的是空格不要輸出。
代碼： #include<map> #include<cstdio> #include<cstring> using namespace std; struct node {char l,r; }; map <char,node> tree;//定義一個下標(biāo)為char，存儲類型為node（結(jié)構(gòu)體）的map數(shù)組 char a[300]; int len,x; void f(char s) {if(x==len) return;//如果長度到了returnchar c=a[x++];//當(dāng)前字符存入（其實不存也行）if(!tree[s].l) tree[s].l=c;//左兒子else tree[s].r=c;//右兒子if(c!=' ') f(c);//遞歸找完左子樹if(c!=' ') f(c);//右子樹 } void last(char g){//倒序輸出這個很容易不講了if(g){last(tree[g].l);last(tree[g].r);if(g!=' ')printf("%c",g);} } int main() {fgets(a,300,stdin);//讀入len=strlen(a);f(0);last(a[0]); }當(dāng)然，有100多b的方法

其實，是不需要建樹的，只用一個變量加遞歸就可以完成此題 超簡單的方法： 讀入一個字符，只要不是空格就再次遞歸，最后輸出即可，因為一旦有了空格就代表當(dāng)前結(jié)點(diǎn)的某一兒子為空，二叉樹有兩個兒子，所以遞歸兩次便可以把左子樹和右子樹找完。
代碼： #include<cstdio> void h() {char c=getchar();//getchar一個一個處理if(c==' ')//是空格代表一個兒子沒有了return;h();//找左子樹h();//找右子樹（此時已經(jīng)遇到了一個空格，才會返回，進(jìn)行這一步，說明左子樹找完了）printf("%c",c);//打印 } int main() {h(); }
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?By WZY
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

轉(zhuǎn)載于:https://www.cnblogs.com/LinqiongTaoist/p/7203742.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的【图论】【二叉树】以先序字符串方式建立二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。