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; } |