九度oj 題目1184 二叉樹遍歷

2022-11-24 15:41:44 字數 1612 閱讀 4130

題目1184:二叉樹遍歷

時間限制:1 秒

記憶體限制:32 兆

特殊判題:

提交:4167

解決:1690

題目描述:

編一個程式,讀入使用者輸入的一串先序遍歷字串,根據此字串建立一個二叉樹(以指標方式儲存)。

例如如下的先序遍歷字串:

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

其中“#”表示的是空格,空格字元代表空樹。建立起此二叉樹以後,再對二叉樹進行中序遍歷,輸出遍歷結果。

輸入:

輸入包括1行字串,長度不超過100。

輸出:

可能有多組測試資料,對於每組資料,

輸出將輸入字串建立二叉樹後中序遍歷的序列,每個字元後面都有一個空格。

每個輸出結果佔一行。

樣例輸入:

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

樣例輸出:

c b e g d f a 

分析:如資料結構課本上有一個先序構建二叉樹的偽**,然而問題在於這樣重複輸入字串構造二叉樹,解決辦法是一行一行讀入

字串,當讀入為空行時結束。讀入的字串在一個一個用來構造二叉樹。

1 #include 2 #include 3 #include 4 #include 5

using

namespace

std;67

char str[101];8

intx;

910 typedef struct

nodetnode, *tree;

1415

//tnode* creat()

20//

tnode *t = new tnode;

21//

t->c = str[x++];

22//

t->lchild = creat();

23//

t->rchild = creat();

24//

return t;

25//}26

2728

void creat(tree &t)

34 t = (tnode*)malloc(sizeof(tnode));//

一定要開闢記憶體空間

35 t->c = str[x++];

36 t->lchild =null;

37 t->rchild =null;

38 creat(t->lchild);

39 creat(t->rchild);

40return;41

}424344

void

print(tree t)

5152

intmain()

61return0;

62 }