【聲明：本文為原創(chuàng)文章,未經(jīng)同意,嚴(yán)禁轉(zhuǎn)載和抄襲,違者將追究其法律責(zé)任】

蘇世機(jī)試小課堂，考研機(jī)試不再慌！

公主號(hào)：蘇世學(xué)社考研　　蘇世計(jì)算機(jī)考研

二叉樹遍歷

題目描述

編一個(gè)程序，讀入用戶輸入的一串先序遍歷字符串，根據(jù)此字符串建立一個(gè)二叉樹（以指針方式存儲(chǔ)）。例如如下的先序遍歷字符串：ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹。建立起此二叉樹以后，再對(duì)二叉樹進(jìn)行中序遍歷，輸出遍歷結(jié)果。

示例

輸入

輸入包括1行字符串，長(zhǎng)度不超過100。

輸出

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，輸出將輸入字符串建立二叉樹后中序遍歷的序列，每個(gè)字符后面都有一個(gè)空格。每個(gè)輸出結(jié)果占一行。

樣例輸入

? ?abc##de#g##f###

樣例輸出

? ?c b e g d f a

? ??

答案

①讀題:

本題題意很明顯，根據(jù)給出的先序遍歷找出中序遍歷。

②想出思路：

創(chuàng)建一個(gè)字符數(shù)組存放接收的字符，調(diào)用創(chuàng)建函數(shù)，先序創(chuàng)建一個(gè)二叉樹，然后調(diào)用中序遍歷函數(shù)輸出。

③動(dòng)手編程：

④測(cè)試樣例：

⑤提交代碼：

進(jìn)入下面的鏈接提交核心代碼：

https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=40&&tqId=21342&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

⑥返回測(cè)評(píng)結(jié)果：

本題總結(jié)

本題是一道由先（前）序遍歷轉(zhuǎn)換為中序遍歷的問題，創(chuàng)建一個(gè)字符數(shù)組用來存字符，做一個(gè)結(jié)構(gòu)體表示一個(gè)樹結(jié)點(diǎn)，調(diào)用CreateTree()函數(shù)來遞歸建樹，建好之后遞歸中序輸出即可。注意建樹的時(shí)候傳的參數(shù)是地址。

未完待續(xù)

蘇世學(xué)社旗下品牌，專注于計(jì)算機(jī)考研

計(jì)算機(jī)考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學(xué)習(xí)分享丨咨詢前輩丨個(gè)性化指導(dǎo)