105年關務三等資料結構

二、()請解釋何謂引線二元樹 (threaded binary tree) 及其優點為何。(10分)

()若要以鏈結串列 (linked list) 來表達引線二元樹,試設計一適當之節點結構。(5分)

()請畫出下圖所示二元樹之引線二元樹。請分別畫出有頭端節點 (header node) 與無頭端節點之引線二元樹。(10分)

                      undefined

()請寫出在引線二元樹中以線性時間(即時間複雜度為 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

undefined

()在引線二元樹中以線性時間進行中序尋訪的演算法

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;

}

arrow
arrow
    文章標籤
    資料結構
    全站熱搜
    創作者介紹
    創作者 jacksaleok 的頭像
    jacksaleok

    國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

    jacksaleok 發表在 痞客邦 留言(0) 人氣()