105年關務三等資料結構
|
二、(一)請解釋何謂引線二元樹 (threaded binary tree) 及其優點為何。（10分） (二)若要以鏈結串列 (linked list) 來表達引線二元樹，試設計一適當之節點結構。（5分） (三)請畫出下圖所示二元樹之引線二元樹。請分別畫出有頭端節點 (header node) 與無頭端節點之引線二元樹。（10分） (四)請寫出在引線二元樹中以線性時間（即時間複雜度為 O(n)）進行中序尋訪的演算法。（10分） |
答：
(一)引線二元樹及其優點為何？
1.引線二元樹：
引線二元樹的左引線 (left thread) 指向節點本身的中序前行者，右引線 (left thread) 指向節點本身的中序後繼者。引線分成中引線、前引線、後引線。利用原先二元樹中的空指標能更方便進行追蹤。
2.引線二元樹的優點：
(1)在引線二元樹中，做中序走訪，不需要使用堆疊或遞迴處理，但是一般二元樹需要。
(2)在引線二元樹中，由於充分使用空鏈結，所以避免了鏈結閒置浪費的情形。
(3)在引線二元樹中，做中序走訪時速度比較快。
(4)在引線二元樹中，任一節點都容易找出它中序後繼者與中序前行者。
※參考資料：https://puremonkey2010.blogspot.tw/2010/10/blog-post_19.html
(二)若要以鏈結串列來表達引線二元樹，試設計一適當之節點結構
|
typedef struct tagtNode { int data; // 資料欄位 int left_thread; // 標示左鏈結是指標或引線，0表示指向子節點的指標；1表示引線 int right_thread; // 標示右鏈結是指標或引線，0表示指向子節點的指標；1表示引線 struct tagtNode *left; // 左鏈結 struct tagtNode*right; // 右鏈結 } Th_Node; |
示意圖：
|
data |
|
|
left_thread |
right_thread |
|
left |
right |
(三)畫出二元樹的引線二元樹
中序：B A D F C E
(四)在引線二元樹中以線性時間進行中序尋訪的演算法
|
void inorder(treeptr tree) { treeptr t; t = tree; do { t = insuc(t); if(t != tree) cout << t->data; } while(t != tree); // 不是首節點，則繼續取出中序後繼者 } treeptr insuc(treeptr s) { treeptr t; if(s->right_thread) // s 右邊是引線 t = s->right; else { t = s->right; // 記錄 s 的右節點 if(!s->right_thread) // 右邊是指標 while(!t->left_thread) // 左邊是指標 t = t->left; } return t; } |
留言列表
國考資訊處理解答 (7)
