書名 Java於資料結構與演算法之實習應用 書號　PG20098 原著　河西朝雄著 譯者　周明憲/徐堯譯 台北總公司／台北縣汐止市新台五路一段112號10樓A棟 Building A, 10F, 112, Shin-Tai-Wu Road Sec. 1, Shijr, Taipei, Taiwan. 電話／02-26962869　傳真／02-26962867 台中辦事處／台中市文心路一段540號4樓-1 4-1F, 540, Wen Shing Road, Sec. 1, Taichung, Taiwan. 電話／04-23287870　傳真／04-23108168 博碩網址：http://www.drmaster.com.tw

第六章 學習重點 樹（tree）為資料結構中最重要且常用的單位。將各種須分類的事物（如家譜或公司的組織圖）有階層的顯示出來的方式，正如一棵樹一樣，由根而枝而樹葉的展開。 樹的各個節點(node)的分支(branch)如在2個以下，稱為2元樹(binary tree)，本章以2元樹為中心說明樹的製作方法與樹的追蹤(traversal)法。 追蹤是指以一定的順序尋訪樹的所有節點，為將遞迴演算法與資料結構相連的典型例子。2元樹按資料的性質可分為2元搜尋樹、堆積(heap)、式子的樹與決策樹等。 本書以堆積排序與智慧型資料庫為例來說明樹的應用情形。

6-0 何謂樹 線性串列的資料會依據指標而向一定的方向伸展，且在伸展的途中資料並不會分開。一面將資料分開，一面將資料伸展的資料結構稱為「樹(樹狀結構：tree)」。 樹由數個節點(node)與將節點連接起來的分支(branch)所組成。節點與資料相對應，分支則對應至將資料與資料連接起來的父子關係。節點的分支的節點稱為子節點，其上面的節點稱為父節點。 樹的最上面的節點稱為根(root)，底下沒有子節點的節點稱為樹葉(leaf)。我們可將樹之中的某個節點視為相對的根，其分支與節點的集合則稱為部分樹。

6-0 何謂樹 樹的各節點的分支如在2個以下，則稱為2元樹(binary tree)。樹的演算法的中心為此2元樹。 6-0 何謂樹 樹的各節點的分支如在2個以下，則稱為2元樹(binary tree)。樹的演算法的中心為此2元樹。 2元樹之中，各個節點的資料可以相互比較、父節點與子節點的關係按某種規則（大、小等）排列的樹稱為2元搜尋樹(binary search tree)。 由根到某個節點時所通過的分支數，稱為該頂點的深度(depth)，由根到最深頂點的深度則稱為樹的高度(height)。圖6.2中的節點b、c的深度為1，節點d、e、f的深度為2，節點g、h、i、j的深度為3，樹的高度為3。而根的深度則為0。

6-1 2元搜尋樹的陣列表現 範例中將姓名按辭典順序排列，左邊子節點＜父節點＞右邊子節點之關係在所有的父子之間成立。 6-1 2元搜尋樹的陣列表現 範例中將姓名按辭典順序排列，左邊子節點＜父節點＞右邊子節點之關係在所有的父子之間成立。 這個2元搜尋樹的各節點能以下列的類別來表現： class Girl { private int L; private String name; private int R; } 此2元搜尋樹的陣列形式表現如右： p a[p].L a[p].name a[p].R 1 Machilda 2 3 Candy 4 5 Rolla NIL Ann 6 Emy 7 Nancy Eluza Lisa …

陣列表現 設a[p].L為指向左邊子節點的指標、a[p].R為指向右邊子節點的指標。這些陣列的值使用陣列的元素編號。root為指向根陣列元素的指標。 NIL為指標沒有指向任何物件之意，具體的作法為將其值設為-1。 如要在這種2元搜尋樹中搜尋名資料key時，先要從root開始找起，key若比節點的資料小，則向左側的樹搜尋，key若比節點的資料大，則向右側的樹搜尋。指標為NIL時卻未找到時，代表無此資料。 p a[p].L a[p].name a[p].R 1 Machilda 2 3 Candy 4 5 Rolla NIL Ann 6 Emy 7 Nancy Eluza Lisa …

………… class Girl { private int L; // 指向左側部分樹的指標 private String name; private int R; // 指向右側部分樹的指標 public Girl(int l,String n,int r) { L=l; name=n; R=r; }

將資料新增至2元搜尋樹 以例題42的原則搜尋新資料key所要插入的位置old。比較key資料與父節點資料的大小關係，若key資料比較大則將其插至父節點的右側，反之則插至父節點的左側。 新資料則存入陣列節點位置(sp)所顯示的陣列元素中。

public void actionPerformed(ActionEvent e) { int i,p=0,old=0; String key=tf.getText(); while (p!=NIL) { // 樹的搜尋 old=p; if (key.compareTo(a[p].name)<0) p=a[p].L; else p=a[p].R; } a[n]=new Girl(NIL,key,NIL); // 連接至新的節點 if (key.compareTo(a[old].name)<0) a[old].L=n; a[old].R=n; n++; ta.setText(""); // 顯示節點表格 for (i=0;i<n;i++) ta.setText(ta.getText()+a[i].L+", "+a[i].name+" , "+a[i].R+"\n");

6-2 2元搜尋樹的製作 練習問題42將新的資料新增至現有的樹內，接下來要從空的樹開始製作2元搜尋樹。因此我們將根節點的製作與第2個以後的節點之連接分開處理。

public void actionPerformed(ActionEvent e) { int i,p=0,old=0; String key=tf.getText(); if (n==0) { // 根節點 a[0]=new Girl(NIL,key,NIL); n=1; } else { // 第2個以後的節點 p=0; while (p!=NIL) { // 樹的搜尋 old=p; if (key.compareTo(a[p].name)<0) p=a[p].L; else p=a[p].R; a[n]=new Girl(NIL,key,NIL); // 新節點的連接 if (key.compareTo(a[old].name)<0) a[old].L=n; a[old].R=n; n++; ……………………………

最小節點與最大節點的搜尋 從2元搜尋樹中搜尋最小的節點與最大的節點 向2元搜尋樹的左側節點搜尋到最後時有1個最小的節點，相反的向右側節點搜尋到最後時有1個最大的節點。 搜尋最小的節點的做法如下： p=root; while (a[p].L!=NIL){ p=a[p].L; } a[p].name為最小的節點。

………… p=0; // 搜尋最小節點 while (a[p].L!=NIL) p=a[p].L; ta.setText(ta.getText()+"最小節點="+a[p].name+"\n"); p=0; // 搜尋最大節點 while (a[p].R!=NIL) p=a[p].R; ta.setText(ta.getText()+"最大節點="+a[p].name+"\n"); …………………

6-3 2元搜尋樹的遞迴表現 以遞迴製作2元搜尋樹： 6-3 2元搜尋樹的遞迴表現 以遞迴製作2元搜尋樹： 設gentree(p,key)為將新資料key連接至父節點p的程序，則求連接位置並向左側的樹前進時，則 a[p].L=gentree(a[p].L,key); 若向右側的樹前進時，則 a[p].R=gentree(a[p].R,key); gentree()則傳回下列的值。 ‧新節點製作完成時為指向該節點的指標 ‧否則為gentree呼叫時傳至p的資料，即原來的指標值。 執行了a[p].L=gentree(a[p].L,key)，但結果為NIL，因而結束遞迴呼叫然後製作新的節點Eluza，再呼叫指向該節點的指標後返回。換句話說，已經產生了指向新節點的指標，父節點與子節點已經連接起來。

……… public int gentree(int p,String key) { // 遞迴方法 if (p==NIL) { a[n]=new Girl(NIL,key,NIL); n++; return n-1; } else if (key.compareTo(a[p].name)<0) a[p].L=gentree(a[p].L,key); // 向左側的遞迴呼叫 else a[p].R=gentree(a[p].R,key); // 向右側的遞迴呼叫 return p;

2元搜尋樹的搜尋（遞迴版） 以遞迴搜尋2元搜尋樹 尋找具有key的節點p之演算法大致內容如下： ‧若節點p來到NIL或在節點p找到key，則傳回p的值。 ‧若key的值較小，則進行指向左側樹的搜尋遞迴呼叫，否則進行指向右側樹的搜尋遞迴呼叫。 public int search(int p,String key) { // 遞迴程序 if (p==NIL || key.equals(a[p].name)) return p; if (key.compareTo(a[p].name)<0) return search(a[p].L,key); // 指向左側的遞迴呼叫 else return search(a[p].R,key); // 指向右側的遞迴呼叫 }

6-4 2元搜尋樹的追蹤 以一定的步驟巡視樹的所有節點稱為樹的追蹤(traversal)。圖6.7為樹的追蹤的例子，先盡可能的向左側的節點前進，當到達節點的邊界時，便回到前面的父節點，然後再往右邊的節點前進，如此反覆操作同樣的步驟。

樹的追蹤過程方式 在樹的追蹤過程中，「巡視過的節點之顯示處理」方式可分為下列3種： ‧前序追蹤(preorder traversal) (1)顯示節點 (2)巡視左側樹的遞迴呼叫 (3)巡視右側樹的遞迴呼叫 資料的顯示順序為50、35、25、40、36、41、60 ‧中序追蹤(inorder traversal) (1)巡視左側樹的遞迴呼叫 (2)顯示節點 資料的顯示順序為25、35、36、40、41、50、60，剛好按遞增順序排列。 若將向右追蹤與向左追蹤的先後順序對調，則資料的顯示順序便按遞減順序排列。 ‧後序追蹤(postorder traversal) (2)巡視右側樹的遞迴呼叫 (3)顯示節點 資料的顯示順序為25、36、41、40、35、60、50

public int gentree(int p,String key) { if (p==NIL) { a[n]=new Girl(NIL,key,NIL); n++; return n-1; } else if (key.compareTo(a[p].name)<0) a[p].L=gentree(a[p].L,key); else a[p].R=gentree(a[p].R,key); return p; public void treewalk(int p) { // 樹的追蹤 if (p!=NIL) { treewalk(a[p].L); ta.setText(ta.getText()+a[p].name+"\n"); // 顯示節點 treewalk(a[p].R);

練習問題45-1 按遞減順序排列 追蹤2元搜尋樹的節點，並按遞減順序顯示 練習問題45-1 按遞減順序排列 追蹤2元搜尋樹的節點，並按遞減順序顯示 public void treewalk(int p) { // 樹的追蹤 if (p!=NIL) { treewalk(a[p].R); ta.setText(ta.getText()+a[p].name+"\n"); // 顯示節點 treewalk(a[p].L); }

2元搜尋樹追蹤的非遞迴版 以非遞迴方式製作2元搜尋樹的追蹤（中序追蹤），如圖6.8所示，將父節點的位置儲存至堆疊w[]內，併同時執行追蹤作業。 (1)由於將「堆疊已空且位於右邊邊界」設為程式的結束條件，因此在未達到此條件前須執行以下步驟。 (2)盡可能的向左側的子節點前進。將此時的父節點位置儲存在w[sp]內。 (3)回到前1個父節點，並顯示此節點。將sp-1時，w[sp]會顯示出父節點位置的資料。本步驟利用這種情況。 (4)向右側的子節點前進。

………………………… public void actionPerformed(ActionEvent e) { int[] w=new int[128]; int p,q,sp; ta.setText(""); sp=0;p=root;q=p; while (sp!=0 || q!=NIL) { while (q!=NIL) { // 盡可能的向左側前進 w[sp]=q; // 將父節點的位置儲存至堆疊內 sp++; q=a[q].L; } sp--; // 回到前1個父節點 ta.setText(ta.getText()+a[w[sp]].name+"\n"); q=a[w[sp]].R; // 向右側前進 ………………………

6-5 各層的追蹤 若將指向階層n各節點的指標按由最左端節點到最右端節點的順序儲存在堆疊q[]內，便能以此堆疊資訊為基礎，由左至右的追蹤階層n的各節點。這個追蹤過程將各節點的子節點按左側的子節點與右側的子節點的順序排列，如果找到，便將該指標儲存在堆疊w[]內。這時w[]內的資料就成為下1階層的全部節點。 因此，只要複製w[]→q[]，並反覆操作上列步驟，即可做到階層n+1的追蹤。

public void treewalk(int p) { // 各層的追蹤 int[] q=new int[128], // 指標表格 w=new int[128]; // 作業使用 int i,m,child,Level; child=1;q[0]=p;Level=0; // 初始值 do { m=0; ta.setText(ta.getText()+"Level "+Level+" : "); for (i=0;i<child;i++) { ta.setText(ta.getText()+a[q[i]].name+"\t"); if (a[q[i]].L!=NIL) { w[m]=a[q[i]].L;m++; } if (a[q[i]].R!=NIL) { w[m]=a[q[i]].R;m++; ta.setText(ta.getText()+"\n"); child=m; // 下1階層的子節點的數目 for (i=0;i<child;i++) q[i]=w[i]; Level++; } while (child!=0);

6-6 堆積(Heap) 完全2元樹的全部父節點一定擁有2個以上的子節點（最後的元素如僅是左側的子節點亦無妨），不管取走哪個父節點與子節點，此樹都是父節點＞子節點的關係，這種樹稱為堆積。而左側的子節點與右側的子節點之大小關係則不予理會。 這個堆積可按2元樹分層追蹤所得到的順序存入陣列內，並顯示出來。

新增資料至堆積 新增資料至堆積時，可按下列步驟進行。這項操作可由空的堆積開始執行。 >將新的資料儲存為堆積的最後元素。 >將該元素與做為子節點的父節點做比較，若父節點較大，則父節點與子節點互相交換。 >然後將父節點設為子節點，其上的父節點則反覆執行同樣的步驟。反覆執行的結束條件為，子節點的位置到達根的位置或當父節點≦子節的時候點。 像這樣將新的資料往上移動的情形稱為上移(shift up)。 實際新增資料12進去的範例如下：

public void actionPerformed(ActionEvent e) { int i,s,p,w; heap[n]=Integer.parseInt(tf.getText()); // 加至堆積的最後 s=n; p=s/2; // 父節點的位置 while (s>=2 && heap[p]>heap[s]) { // 上移 w=heap[p];heap[p]=heap[s];heap[s]=w; s=p;p=s/2; } n++;

堆積的製作（下移） 例題47是將1筆筆的資料新增至堆積內，有1個方法是將全部的資料分配成2元樹後再建構成堆積，其方法如下： ‧由擁有子節點的最後1個父節點開始反覆操作至根為止。 ‧若父節點比子節點小，則2個子節點中較小的一方與父節點交換。交換好的子節點則重新設為父節點，在符合父節點＜子節點之前，對下面的迴圈執行同業的作業。 具體範例如下：

public void actionPerformed(ActionEvent e) { int i,p,s,t,m; m=n-1; for (i=m/2;i>=1;i--) { p=i; // 父節點的位置 s=2*p; // 左側的子節點的位置 while (s<=m) { if (s<m && heap[s+1]<heap[s]) s++; if (heap[p]<=heap[s]) break; t=heap[p];heap[p]=heap[s];heap[s]=t; p=s;s=2*p; // 父節點與子節點的位置的更新 } ta.setText(""); for (i=1;i<=m;i++) ta.setText(ta.getText()+heap[i]+" ");

6-7 堆積排序 堆積排序大致由下列2個部分組成： (1) 製作初始堆積 (2) 將進行交換作業時分離開的堆積修改成正確的堆積 6-7 堆積排序 堆積排序大致由下列2個部分組成： (1) 製作初始堆積 (2) 將進行交換作業時分離開的堆積修改成正確的堆積 (2)部分的詳細說明如下： ‧ 當堆積資料有n個時，根的值為最小值。將這個根與最後的元素(n)交換，然後將最後的元素（根的值）從樹切離開來。 ‧ 如此一來就形成了n-1個堆積，但根的資料卻不符合堆積的條件。因此將根的資料下移（練習問題47）以製作正確的堆積。 ‧ 在n-1個堆積方面，將根與最後的元素(n-1)交換，然後將最後的元素由樹中切離。 只要反覆執行以上步驟，資料即能按n、n-1、n-2、...的遞減順序排列，同時堆積的大小也會越來越小，到了最後排序即告結束。

bt1.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { int i,s,p,w; // 加至堆積的最後元素 heap[n]=Integer.parseInt(tf.getText()); s=n; p=s/2; // 父節點的位置 while (s>=2 && heap[p]>heap[s]) { // 上移 w=heap[p];heap[p]=heap[s];heap[s]=w; s=p;p=s/2; } n++; }); bt2.addActionListener(new ActionListener() { int m,p,s,t,i; m=n-1; // 資料數量 while (m>1) { t=heap[1];heap[1]=heap[m];heap[m]=t; m--; p=1;s=2*p; while (s<=m) { if (s<m && heap[s+1]<heap[s]) s++; if (heap[p]<=heap[s]) break; t=heap[p];heap[p]=heap[s];heap[s]=t; p=s;s=2*p; ta.setText(""); for (i=1;i<n;i++) ta.setText(ta.getText()+heap[i]+" "); n=1; // 回到初始狀態

6-8 計算式樹 製作計算式樹 以逆向波蘭標記法製作計算式樹 計算式 a*b-(c+d)/e 可用波蘭標記法改寫成： ab*cd+e/- 6-8 計算式樹 製作計算式樹 以逆向波蘭標記法製作計算式樹 計算式 a*b-(c+d)/e 可用波蘭標記法改寫成： ab*cd+e/- 接下來我們要使用波蘭標記法來製作如右圖所示的樹（這種樹的名稱為計算式樹）。 計算式樹有下列的特徵： ‧根為計算式的最後的字元（一定是運算子），這意味著追蹤是由計算式的後面向前進行的。 ‧常數（運算元）則為樹葉。追蹤的遞迴呼叫來到樹葉之後便返回。

製作計算式樹之演算法 將這些特徵考慮進去後，製作計算式樹之演算法的大致內容如下： ‧ 由波蘭標記法計算式的後面取出1個字元，將將其配置成節點。 ‧ 若該字元為常數，則將NIL儲存至左右指標內，然後從遞迴呼叫中返回。 ‧ 若該字元為運算子，則將下1個字元當作右側的子節點並執行連接的遞迴呼叫，然後再將下1個字元當作左側的子節點並執行連接的遞迴呼叫。

計算式樹以不同方式追蹤 ‧前序追蹤後，便如計算式 -*ab/+cde 所示，可製作成運算子在前面的計算式，這種計算式稱為接頭型計算式。 ‧中序追蹤後，便如計算式 a*b-c+d/e 所示，可製作成運算子在運算元之間的計算式，這種計算式稱為插入型計算式。不過，真正的插入型計算式如所示，須加上()。 ‧後序追蹤後，便如計算式 ab*cd+e/- 所示，可製作成運算子在後面的計算式，這種計算式稱為接尾型計算式（逆向波蘭標記法）。

void prefix(int p) { // 接頭型—前序追蹤 if (p!=NIL) { ta.setText(ta.getText()+a[p].ope); prefix(a[p].L); prefix(a[p].R); } void infix(int p) { // 插入型—中序追蹤 infix(a[p].L); infix(a[p].R); void postfix(int p) { // 接尾型—後序追蹤 postfix(a[p].L); postfix(a[p].R);

計算式樹的計算 由計算式樹求出計算式的值 以後序追蹤計算式樹的過程中，關於運算子的左側的子節點與右側的子節點方面，先以該運算子計算再將解答儲存至含有運算子的節點內，再向下1個目標前進。當走到樹的尾端時，即可在跟節點得到計算式的值。

int gentree(int p) { int n; n=exp.length(); m++;p=m; a[p]=new Node(NIL,exp.charAt(n-1),NIL); // 將字串終端設為節點 exp=exp.substring(0,n-1); // 將終端排除在外 if (!(a[p].ope=='-' || a[p].ope=='+' || a[p].ope=='*' || a[p].ope=='/')) { a[p].ope=a[p].ope-'0'; } else { a[p].R=gentree(a[p].R); a[p].L=gentree(a[p].L); return p; void postfix(int p) { // 計算式樹的運算 if (p!=NIL) { postfix(a[p].L); postfix(a[p].R); switch (a[p].ope) { case '+':a[p].ope=a[a[p].L].ope+a[a[p].R].ope;break; case '-':a[p].ope=a[a[p].L].ope-a[a[p].R].ope;break; case '*':a[p].ope=a[a[p].L].ope*a[a[p].R].ope;break; case '/':a[p].ope=a[a[p].L].ope/a[a[p].R].ope;break;

public Dr49Frame() { setSize(200,100); addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent e) { System.exit(0); } }); Button bt; add(bt=new Button("計算式樹的運算"),"North"); add(ta=new TextArea(5,40),"Center"); bt.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { root=NIL;m=0; ta.setText(exp+"="); root=gentree(root); postfix(root); // 計算式的運算 ta.setText(ta.getText()+a[root].ope);

6-9 智慧型資料庫 製作在電腦與人類的對話過程中，讓電腦具有學習功能、累積智慧型資料庫的系統。 6-9 智慧型資料庫 製作在電腦與人類的對話過程中，讓電腦具有學習功能、累積智慧型資料庫的系統。 某個問題（如：你是男的嗎？）的答案如被限定為yes與no，則此問題可視為由節點(node)形成的2元樹。這種樹稱為決策樹。

已學習過的問題節點 元素 左側指標 問題節點 右側指標 p a[p].L a[p].node a[p].R 1 愛吃肉 2 3 愛吃義大利麵 1 愛吃肉 2 3 愛吃義大利麵 4 NIL 日本料理族 義大利菜族 5 愛吃糖醋排骨 6 中餐族 正統西餐族 7 異國風味族 8 9 Max lp 已學習過的問題節點 7 愛吃辣的食物 8