九度oj 題目1078 二叉樹遍歷

2022-11-24 16:07:02 字數 2266 閱讀 2534

題目1078:二叉樹遍歷

時間限制:1 秒

記憶體限制:32 兆

特殊判題:

提交:5326

解決:3174

題目描述:

二叉樹的前序、中序、後序遍歷的定義:

前序遍歷:對任一子樹,先訪問跟,然後遍歷其左子樹,最後遍歷其右子樹;

中序遍歷:對任一子樹,先遍歷其左子樹,然後訪問根,最後遍歷其右子樹;

後序遍歷:對任一子樹,先遍歷其左子樹,然後遍歷其右子樹,最後訪問根。

輸入:

兩個字串,其長度n均小於等於26。

第一行為前序遍歷,第二行為中序遍歷。

二叉樹中的結點名稱以大寫字母表示:a,b,c....最多26個結點。

輸出:

輸入樣例可能有多組,對於每組測試樣例,

輸出一行,為後序遍歷的字串。

樣例輸入:

abc

bacfdxeag

xdefag

樣例輸出:

bca

xedgaf

分析:先遞迴重建二叉樹,在遞迴後序遍歷。

1 #include2 #include3 #include4 #include 

5using

namespace

std;

67 typedef struct

nodebtree;

1213

string

str1, str2;

14void postorder(btree *t)

1523

return;24

}2526 btree *trans(int l1,int h1,int l2,int

h2)32

33//

構造根節點

34 btree *t=(btree*)malloc(sizeof

(btree));

35 t->data=str2[j];

36 t->lchild=null;

37 t->rchild=null;

3839 t->lchild=trans(l1+1,l1+j-l2,l2,j-1); //

返回左子樹

40 t->rchild=trans(l1+j-l2+1,h1,j+1,h2); //

返回右子樹

41return

t;42}43

4445

intmain()

4656

return0;

57 }

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

using

namespace

std;

67 typedef struct

nodebtree;

1213

char str1[30], str2[30

];14

15void postorder(btree *t)

23return;24

}2526 btree *trans(int l1,int h1,int l2,int

h2)32

33//

構造根節點

34 btree *t = (btree*)malloc(sizeof

(btree));

35 t->data =str2[j];

36 t->lchild =null;

37 t->rchild =null;

3839 t->lchild = trans(l1+1, l1+j-l2, l2, j-1); //

返回左子樹

40 t->rchild = trans(l1+j-l2+1, h1, j+1, h2); //

返回右子樹

41return

t;42}43

4445

intmain()

4655

return0;

56 }

九度oj 題目1184 二叉樹遍歷

題目1184 二叉樹遍歷 時間限制 1 秒 記憶體限制 32 兆 特殊判題 否 提交 4167 解決 1690 題目描述 編一個程式,讀入使用者輸入的一串先序遍歷字串,根據此字串建立一個二叉樹 以指標方式儲存 例如如下的先序遍歷字串 abc de g f 其中 表示的是空格,空格字元代表空樹。建立起...