建立二元樹並進行各種遍歷

題目敘述

學生會的幹部架構畫成了一棵二元樹，現在要讓程式把它存起來，並用不同的順序列出每個人的編號。請實作一個二元樹模組：先依層序資料建樹，之後可以回答前序、中序、後序、層序四種遍歷，以及樹的高度與節點數。

樹以陣列形式的層序資料給定：第 i 個槽位（從 0 起算）的左、右子節點分別在槽位 2i+1 與 2i+2，值 −1 代表該槽位沒有節點。請提交 tree.h 與 tree.c，介面如下。

函式介面

typedef struct tree tree;

void tree_build(tree *t, const int *level, int n); /* -1 = null slot */
void tree_preorder(tree *t); /* print values space-separated, one line */
void tree_inorder(tree *t);
void tree_postorder(tree *t);
void tree_levelorder(tree *t);
int tree_height(tree *t);
int tree_size(tree *t);

輸入格式

• 第一行：整數 n，為層序槽位數（空樹時為 0）。
• 若 n > 0，第二行有 n 個整數，依上述規則表示整棵樹。
• 若 n < 0，則沒有數值那一行，樹是把 1, 2, …, |n| 依序插入二元搜尋樹得到的結果（一條只往右延伸的鏈）。此時 tree_build 會收到 level 為 NULL 與負的 n，請自行處理。
• 接著一行整數 Q，再來 Q 行，每行一個操作：preorder、inorder、postorder、levelorder、height、size。

輸出格式

每個操作輸出一行。四種遍歷印出走訪到的節點值，以單一空白分隔（只含真正存在的節點，空樹則是空白行）；height 與 size 各印一個整數。高度以最長路徑的邊數計，單一節點為 0，空樹也視為 0。

限制

• 0 ≤ n ≤ 2000（另有以 n < 0 表示的鏈狀測資）
• 隨機測資中的節點值為 [0, 100] 的整數
• 每筆測資 1 ≤ Q ≤ 6

範例

範例 1

輸入

7
1 2 3 4 5 6 7
3
preorder
postorder
levelorder

輸出

1 2 4 5 3 6 7
4 5 2 6 7 3 1
1 2 3 4 5 6 7

範例 2

輸入

1
5
2
preorder
size

輸出

5
1

範例 3

輸入

0
1
size

輸出

0

範例 4

輸入

15
1 2 3 4 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
6
preorder
inorder
postorder
levelorder
height
size

輸出

1 2 4 5 3
4 2 5 1 3
4 5 2 3 1
1 2 3 4 5
2
5

範例 5

輸入

1
5
3
preorder
inorder
height

輸出

5
5
0

說明

範例 1 是一棵完全二元樹，可以對照三種順序的差別：前序先印根，後序最後才印根，層序則一層一層由上往下。範例 2 只有一個節點，所以遍歷只印出它，節點數為 1。範例 3 沒有任何槽位，是空樹，節點數為 0。