當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

5. 树

發布時間：2024/4/17 编程问答 23 豆豆

生活随笔收集整理的這篇文章主要介紹了 5. 树小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

樹

廣義樹概念

子節點表描述方法

樹的“左子節點/右兄弟節點”描述方法 ?

?? 本章將擴展前幾章的內容，討論一種較為復雜的數據結構，即樹(tree)結構。前面所討論的線性表、堆棧等數據結構中，跟每個節點相連的節點的個數都是有限的。本章討論的樹結構中，節點可以有任意數目的子節點。這是的數在實際應用中具有更大的作用，但其結構更復雜。

樹的定義

?? 一棵樹T是由一個或一個以上節點組成的有限集合，其中節點有分為根節點、葉節點和中間節點。樹具有層結構，根節點(R)之外的節點集合{T-R}，可以劃分為一些不相交子集{T1,…,Tn}。這些子集又可以分別構成子樹，并擁有相應的根節點。一般將位于根節點左邊的子節點稱作左子節點，位于右邊的子節點稱作右子節點。位于右邊的子節點稱為最左邊子節點的右兄弟節點。節點的出度定義為其子節點的個數。

圖示意了圖結構，其找R為根節點，根節點下有連個子節點，P和P1。其中P有三個子節點，V，V1，V2。以V為父節點的子集為例，構成了一個子樹。V1和V2是V的有兄弟節點。

圖?廣義樹示例

???? 在樹結構中，根節點之外的節點都有唯一的父節點。所以，在一棵節點總數為n的樹中，邊的個數為n-1。在本章即將詳細討論的二叉樹是一種特殊的樹結構，具有非常豐富的結構性，例如二叉樹的中間節點個數與葉節點個數。

本章內容

???? 本章將從廣義樹開始討論樹結構，并介紹兩種廣義樹的實現方式；將詳細討論二叉樹的性質和四種遍歷算法；最后一部分將介紹huffman編碼樹。

廣義樹的描述方法

??? 本章只討論總節點有限的廣義樹，所有節點存放在大小確定的數組中。節點之間的連接關系用節點在數組中的標號之間的連接關系表示。

廣義樹中每個父節點可能包含多個子節點，并且各個父節點的子節點個數也不盡相同。針對這種結構，每個節點除了存放節點元素項和節點的父節點之外，我們可以對為每個節點設計一個單鏈表，鏈表中的元素項表示該節點所指向的所有子節點在數組中的標號。如圖示意了用這種方法對上圖中樹結構的描述。這種方法通常稱為“子節點表方法”。

圖?子節點表方法描述樹

???? 子節點表方法在每個節點記錄了該節點的所有子節點的信息，這種描述沒有充分挖掘同一個父節點的子節點之間連接關系的傳遞性。另一種常見的描述方式為“左節點/右兄弟節點方法”。這種方法中，每個節點都存放了該節點的子節點中最左邊的子節點的指針以及與該節點相鄰的右兄弟節點。這種方法利用了同一父節點的子節點之間連接關系的傳遞性。

圖?左子節點/右兄弟節點描述方法

?? 利用“左子節點/右兄弟節點”描述方法，在每個節點處所保存的連接信息只需要三個指針，而不需要鏈表結構。下面我們將詳細討論這兩種描述方法的實現過程。

子節點表描述方法

?? 上面我們已經初步了解到，利用子節點表描述樹結構時，關鍵的設計步驟是設計節點的數據結構。這里節點的成員變量包括：節點的所包含的內容信息、該節點的父節點在節點數組中的序號、表示該節點的子節點的鏈表和該節點在節點數組中的序號。其中子節點鏈表中鏈表節點的元素項為子節點的序號，子節點的順序由左向右。在創建節點對象時，需要同時設置四個成員變量。

?? 節點數據結構的定義如下：

package?Tree;

import?Element.ElemItem;
import?List.SingleLink2;

/**
?*?基于鏈表的樹結構（子節點表示法），
?*?這里的的鏈表是高效單鏈表
?*/
public?class?LinkTNode{
????//節點自身的元素項
????private?ElemItem?elem;
????//節點父節點
????private?int?parentNode;
????//每個樹節點中包含一個單鏈表,
????//鏈表中每個節點中的元素項是LinkTNode類型
????private?SingleLink2?link_idx;
????//節點在節點數組中的位置idx
????private?int?idx;
????
????//無參數的構造函數
????public?LinkTNode(){
????????elem?=?null;
????????parentNode?=?-1;
????????link_idx?=?null;
????????idx?=?-1;
????}
????
????//帶參數的構造函數
????public?LinkTNode(ElemItem?e,?int?pn,
????????????????SingleLink2?sk,?int?_idx){
????????elem?=?e;
????????parentNode?=?pn;
????????link_idx?=?sk;
????????idx?=?_idx;
????}
????
????//設置節點元素項
????public?void?setElem(ElemItem?_elem)?{
????????elem?=?_elem;????
????}
????//獲取節點的元素項
????public?ElemItem?getElem(){
????????return?elem;
????}
????
????//判斷是否是葉節點
????public?boolean?isLeaf()?{
????????//若節點中的鏈表是空，則是葉節點
????????return?link_idx?==?null;
????}

????//返回父節點
????public?int?parent()?{
????????return?parentNode;
????}

????//設定父節點
????public?void?setParent(int?pn)?{
????????parentNode?=?pn;
????}
????
????//返回所有子節點對應的鏈表
????public?SingleLink2?getChildLink(){
????????return?link_idx;
????}
????
????//重新設置節點的子節點
????public?void?setChildLink(SingleLink2?slk){
????????link_idx?=?slk;
????}
????
????//獲取當前節點在節點數組中的位置
????public?int?getIdx(){
????????return?idx;
????}
????//設置當前節點在節點數組中的序號
????public?void?setIdx(int?_idx){
????????idx?=?_idx;
????}
????//返回元素項String形式
????public?String?toString(){
????????return?elem.getElem().toString();
????}
????
}

??? 上述節點類的描述中還包含了toString()函數，其目的是為了更方便地顯示該節點中的內容。

節點連接表的描述方法中，樹的節點全部存放在節點類型的數組中，節點之間的連接關系通過每個節點所保存的子節點鏈表來表示。樹的數據結構中包含節點個數、節點數組、當前樹中有效的節點個數和樹的根節點在數組中的序號。創建樹時，需要確定樹的節點個數，即節點數組的大小。

對樹的操作通常包括節點的添加、節點的刪除和樹的遍歷等。

在樹中插入包含元素項elem的新節點時，需要確定待插入節點在數組中的序號self_idx和父節點在數組中的序號p_idx。如果其父節點為空，則直接將p_idx位置的節點中的元素項設為elem，而self_idx的值無效。如果父節點不為空，則將在節點數組的self_idx處新建元素項為elem的節點，并將self_idx添加到p_idx處節點的子節點鏈表中去。如果當前p_idx的子節點鏈表不為空，則直接將self_idx添加到鏈表中，否則，需要首先創建p_idx的子節點鏈表，然后再添加self_idx。添加新節點后需要更新節點的個數。

從上面的插入節點過程可以看出，插入新的節點最多只會影響一個已存在的節點的子節點鏈表，但是刪除節點相對節點插入過程會更復雜一點。因為刪除一個節點時，需要同時刪除該節點對應的子節點以及子節點的子節點，以此類推。即需要遞歸地刪除該節點的所有子節點。

如果待刪除的節點沒有子節點，即其子節點鏈表為空，則直接將該節點從其父節點的子節點鏈表中刪除，同時更新樹中節點的個數。這個過程首先需要在待刪除節點父節點的子節點鏈表中找到該節點的序號，由于使用的是單鏈表，則需要從鏈表首部開始逐個判斷。

如果待刪除的節點有子節點，其子節點鏈表不為空，則需要遍歷它的所有子節點，并遞歸地對每個子節點執行刪除節點過程。

打印樹結構時需要遍歷樹中的所有節點，在上一章中，堆的遍歷算法包括前序、中序和后續。由于廣義樹中每個節點的子節點個數不一定為兩個，所以這里的遍歷算法主要是前序和后續遍歷。我們將分別討論這兩種遍歷方法。

后序遍歷算法，首先訪問節點的所有子節點，然后再訪問節點本身。一般的實現方法是遞歸遍歷。首先對節點的子節點鏈表中所有節點執行遞歸后序遍歷，直到子節點再沒有子節點位為止，然后再訪問節點自身。

前序遍歷算法，首先訪問節點自身，然后再對節點子節點鏈表中的每個節點遞歸地執行前序遍歷，直到子節點再沒有子節點為止。這種遍歷算法對廣義樹而言更有意義，例如我們通常使用的文件資源管理結構中，文件夾下通常包含子文件夾，并層層包含，如圖。在遍歷文件資源管理器的樹狀結構時，我們通常會自然地采用前序遍歷算法。

在打印樹結構及其中的節點時，為了體現出節點之間的層次性，需要控制節點內容顯示的位置。節點所在的層次越深，其顯示的位置越靠后。

圖?文件資源管理器的樹狀結構

??? 基于上面的討論，樹的節點連接表描述類實現如下：

package?Tree;
????
????import?Element.ElemItem;
????import?List.SingleLink2;
????
????/**
?????*?鏈表樹，基于數組的節點存儲方式
?????*/
????public?class?LinkTree?{
????????//私有成員變量，LinkNode類型的數組，固定長度
????????private?int?len;//節點最大個數
????????//私有成員變量，樹節點個數
????????private?LinkTNode?node_array[];
????????//私有成員變量，樹的根節點在數組中序號
????????private?int?root;
????????//樹中當前節點的個數
????????private?int?curr_num;
????????
????????//有參數的構造函數
????????public?LinkTree(int?_len){
????????????len?=?_len;
????????????node_array?=?new?LinkTNode[_len];
????????????root?=?-1;????????
????????????//位置0處為樹根前驅節點
????????????node_array[0]?=?new?LinkTNode(
????????????????????new?ElemItem<Integer>(0),
????????????????????-1,????null,?0);
????????????for(int?i??=?1;?i?<?_len;?i++){
????????????????node_array[i]?=?new?LinkTNode();
????????????}
????????}
????????
????????//設置樹的根節點
????????public?void?setRoot(int?r){
????????????root?=?r;
????????????node_array[r].setParent(0);
????????????SingleLink2?slk?=?new?SingleLink2();
????????????slk.insert(new?ElemItem<Integer>(r));
????????????node_array[0].setChildLink(slk);
????????}
????????
????????//清除數組中的元素項
????????public?void?clear(){
????????????root?=?-1;
????????????for(int?i??=?0;?i?<?len;?i++){
????????????????node_array[i].setElem(null);
????????????}
????????????curr_num?=?0;
????????}
????????
????????//數組中第n_idx個節點添加子節點（類型的元素項），
????????//n_idx為父節點號
????????//自身的節點號為self_idx
????????public?boolean?addChild(int?p_idx,?
????????????????????????????????int?self_idx,?
????????????????????????????????ElemItem?e){
????????????if(p_idx?<?0?||?p_idx?>=?len?||?
????????????????self_idx?<?0?||?self_idx?>=?len?||
????????????????curr_num?>?len){
????????????????return?false;
????????????}
????????????//如果節點數組在父節點號處沒有元素項，
????????????//則直接將元素項e賦值到數組的p_idx處，self_idx無效用
????????????if(node_array[p_idx].getElem()?==?null){
????????????????node_array[p_idx].setElem(e);
????????????????node_array[p_idx].setChildLink(null);
????????????????node_array[p_idx].setParent(-1);
????????????????node_array[p_idx].setIdx(p_idx);
????????????????curr_num++;
????????????????return?true;
????????????}
????????????//如果節點數組在父節點號處有元素項了
????????????//則將e賦值到數組self_idx處，同時設置相關參數
????????????node_array[self_idx].setElem(e);
????????????node_array[self_idx].setIdx(self_idx);
????????????node_array[self_idx].setParent(p_idx);
????????????node_array[self_idx].setChildLink(null);
????????????//如果父節點的子樹鏈表是空的，則新建鏈表并插入self_ode處的節點
????????????if?(node_array[p_idx].getChildLink()?==?null){
????????????????node_array[p_idx].setChildLink(
????????????????????????new?SingleLink2());
????????????}
????????????//在節點的子節點
????????????node_array[p_idx].getChildLink().insert(
????????????????????new?ElemItem<Integer>(self_idx));
????????????node_array[p_idx].getChildLink().next();
????????????curr_num++;
????????????return?true;
????????}
????????
????????//刪除pIdx父節點的子節點序號sIdx,即鏈表清除
????????protected?void?removeSon(int?pIdx,?int?sIdx){
????????????node_array[pIdx].getChildLink().goFirst();
????????????//定位父節點的子節點鏈表中要刪除的子節點的序號的位置
????????????while(((Integer)(node_array[pIdx].getChildLink(
????????????????).getCurrVal().elem)).intValue()!=?sIdx){
????????????????node_array[pIdx].getChildLink().next();
????????????}
????????????//刪除該位置上的子節點的序號（鏈表節點）
????????????node_array[pIdx].getChildLink().remove();
????????????curr_num--;
????????}
????????
????????//刪除位置為nidx的節點的子節點
????????public?boolean?removeChild(int?nidx){
????????????if(nidx?<?0?||
????????????????node_array[nidx].getElem()?==?null){
????????????????return?false;
????????????}
????????????//子節點不為空，則將子節點一一清空
????????????if(node_array[nidx].getChildLink()?!=?null){
????????????????node_array[nidx].getChildLink().goFirst();
????????????????while(node_array[nidx].getChildLink().getCurrVal()
????????????????????????!=?null){
????????????????????int?idx?=?
????????????????????????((Integer)(node_array[nidx].getChildLink(
????????????????????????????).getCurrVal().getElem())).intValue();
????????????????????//遞歸調用
????????????????????removeChild(idx);
????????????????}
????????????????
????????????}
????????????
????????????//清除當前節點
????????????//首先清除
????????????removeSon(node_array[nidx].parent(),?nidx);
????????????//鏈表和元素都清空
????????????node_array[nidx]?=?new?LinkTNode();????????
????????????return?true;
????????}
????????
????????//在特定高度打印一個元素項
????????protected?void?printnode(int?pos,?int?h){
????????????for(int?i?=?0;?i?<?h;?i++)
????????????????System.out.print("\t");
????????????System.out.println(
????????????????"|——?"?+node_array[pos]?+?"("?+?pos+?")");
????????}
????????
????????//后序遍歷樹中元素項
????????protected?void?posOrder(int?pos,?int?h){
????????????if(pos?<?0?||?
????????????????//pos?>?curr_num?||
????????????????node_array[pos].getElem()?==?null)?
????????????????return;
????????????//訪問左子節點
????????????SingleLink2?lftMostChild?=?
????????????????node_array[pos].getChildLink();
????????????if(lftMostChild?!=?null){
????????????????lftMostChild.goFirst();
????????????????while(lftMostChild.getCurrVal()?!=?null){
????????????????????int?idx?=?((Integer)(
????????????????????????lftMostChild.getCurrVal().getElem())
????????????????????????).intValue();
????????????????????posOrder(idx,?h?+?1);
????????????????????lftMostChild.next();
????????????????????
????????????????}
????????????}
????????????//訪問父節點
????????????printnode(pos,?h);
????????}
????????
????????//前序遍歷樹中元素項
????????protected?void?preOrder(int?pos,?int?h){
????????????if(pos?<?0?||?
????????????????//pos?>?curr_num?||
????????????????node_array[pos].getElem()?==?null)?
????????????????return;
????????????//訪問父節點
????????????printnode(pos,?h);
????????????//訪問左子節點
????????????SingleLink2?lftMostChild?
????????????????=?node_array[pos].getChildLink();
????????????if(lftMostChild?!=?null){
????????????????lftMostChild.goFirst();
????????????????while(lftMostChild.getCurrVal()?!=?null){
????????????????????int?idx?=?((Integer)(
????????????????????????lftMostChild.getCurrVal().getElem())
????????????????????????).intValue();
????????????????????preOrder(idx,?h?+?1);
????????????????????lftMostChild.next();????????
????????????????}
????????????}
????????}
????????
????????//后序打印樹
????????public?void?post_print_tree(){
????????????if(curr_num?==?0)?{
????????????????System.out.println("當前樹中沒有節點。");
????????????????return;
????????????}
????????????System.out.println(curr_num?+?"?節點,后序遍歷打印：");
????????????posOrder(1,?0);
????????}
????????//前序打印樹
????????public?void?ford_print_tree(){
????????????if(curr_num?==?0)?{
????????????????System.out.println("當前樹中沒有節點。");
????????????????return;
????????????}
????????????System.out.println(curr_num?+?"?節點,前序遍歷打印：");
????????????preOrder(1,0);
????????}
????}

類中包含四個私有成員變量，分別為樹中最多包含的節點的個數len，節點類型的數字node_array[]，樹根root和樹中當前節點的個數curr_num。

節點添加函數addChild函數，首先判斷添加節點self_idx的父節點p_idx是否為空，若為空則直接將p_idx節點的內容設置為待添加元素項。否則，設置self_idx處節點內容為待添加元素項，并設置其父節點為p_idx，其子節點鏈表為空，如果p_idx的子節點鏈表為空則創建新的子節點鏈表并添加self_idx，如果p_idx的子節點鏈表不為空，則在子節點鏈表中添加self_idx。

節點刪除過程包含兩個函數，removeSon和removeChild。其中removeChild為遞歸函數，如果節點的子節點鏈表不為空，則遞歸地調用removeSon刪除節點的所有子節點。如果節點的子節點鏈表為空，則調用removeSon函數。removeSon函數的入參包括待刪除的節點的父節點在節點數組pIdx中的序號和待刪除節點自身在節點數組中的序號sIdx。在執行時，首先在pIdx節點的子節點鏈表中找到sIdx，然后在鏈表中刪除它并更新樹中的節點個數curr_num。removeSon執行后，還需要將節點數組中的待刪除節點的序號處賦值為空。

兩種樹的遍歷打印過程都需要調用節點打印函數printnode，該函數具有兩個入參，即節點在節點數組中的位置pos和節點所在的層數h。函數執行時首先打印h個制表位，然后再打印節點的內容。

后序打印函數post_print_tree，調用后續遍歷函數posOrder，從樹第一個節點開始打印。執行時，posOrder首先遞歸地調用自身，遍歷節點的所有子節點，遞歸調用時需要改變的是子節點所在的層數。如果子節點為空則調用printnode函數打印該節點。然后調用printnode函數打印節點自身。

前序打印函數ford_print_tree，調用前序遍歷函數preOrder，也從樹的第一個節點開始打印。執行時，preOrder函數首先調用printnode函數打印節點自身，然后遞歸地調用preOrder，遍歷所有子節點，遞歸調用時子節點所在層數也需要變化。如果子節點為空，則調用printnode函數打印該節點。

下面介紹一個實例程序，進一步說明子節點表描述方法類。

package?Tree;
????
????import?Element.ElemItem;
????
????/**
?????*?鏈表樹結構測試示例程序，
?????*?測試樹中插入、刪除節點以及打印樹中元素項
?????*?ExampleLinkTree.java
?????*?
?????*/
????public?class?ExampleLinkTree?{
????????public?static?void?main(String?args[]){
????????????LinkTree?ltree?=?new?LinkTree(100);
????????????ltree.addChild(0,?1,?
????????????????????new?ElemItem<String>("Root"));
????????????ltree.setRoot(1);
????????????ltree.addChild(1,?2,?
????????????????????new?ElemItem<String>("C:"));
????????????ltree.addChild(1,?3,?
????????????????????new?ElemItem<String>("D:"));
????????????ltree.addChild(1,?4,?
????????????????????new?ElemItem<String>("E:"));
????????????ltree.addChild(2,?5,?
????????????????????new?ElemItem<String>("System"));
????????????ltree.addChild(2,?6,?
????????????????????new?ElemItem<String>("Programme"));
????????????ltree.addChild(3,?7,?
????????????????????new?ElemItem<String>("EBook"));
????????????ltree.addChild(7,?13,?
????????????????????new?ElemItem<String>("Communication?Network"));
????????????ltree.addChild(3,?8,?
????????????????????new?ElemItem<String>("Game"));
????????????ltree.addChild(8,?14,?
????????????????????new?ElemItem<String>("LianLianKan"));
????????????ltree.addChild(8,?15,?
????????????????????new?ElemItem<String>("LianLianKan2"));
????????????ltree.addChild(8,?16,?
????????????????????new?ElemItem<String>("LianLianKan3"));
????????????ltree.addChild(8,?17,?
????????????????????new?ElemItem<String>("LianLianKan4"));
????????????ltree.addChild(4,?9,?
????????????????????new?ElemItem<String>("Work"));
????????????ltree.addChild(4,?10,?
????????????????????new?ElemItem<String>("Paper"));
????????????ltree.addChild(9,?11,?
????????????????????new?ElemItem<String>("Java?Algo"));
????????????ltree.addChild(9,?12,?
????????????????????new?ElemItem<String>("Java?Code"));
????????????//調用前序、后序打印函數打印該樹
????????????ltree.ford_print_tree();
????????????ltree.post_print_tree();
????????????//刪除節點8和節點12
????????????ltree.removeChild(8);
????????????ltree.removeChild(12);
????????????//前序打印節點刪除后的樹
????????????System.out.println("前序打印節點8和12被刪除后的樹：");
????????????ltree.ford_print_tree();
????????}
????}
??

該實例程序中首先創建一個樹，其結構如下：

可見，前序打印的結果更符合樹的自然觀察次序，很類似于圖中的樹結構。

本示例程序還示例了在樹中刪除節點的過程，包括葉節點12的刪除和非葉節點8的刪除，刪除這兩個節點后樹的前序打印結果如下：

從刪除節點后樹中的總節點樹可以發現在刪除節點8的同時其子樹中的所有子節點也被成功刪除。

樹的“左子節點/右兄弟節點”描述方法

??? 上面我們討論了基于子節點表的樹的描述方法。這種方法的關鍵思想是將樹的所以節點保存在數組中，每一個節點與其它節點的連接關系用鏈表來描述。樹的另一種描述方法是“左子節點/右兄弟節點”描述法。這種方法中，樹中的節點同樣保存在一個數組中，每個節點除了保存其父節點之外，只保存該節點的一個子節點和一個兄弟節點，每個節點的信息量比較均等，并且避免了鏈表結構的使用。

一下將“左子節點/右兄弟節點”描述方法簡寫為LsRs?(Left?son?Right?sibling)方法。LsRs的節點類中將包含五個私有變量，即節點的內容、節點在節點數組中序號、節點的父節點的序號、節點的左子節點序號以及節點的右兄弟節點序號。

?? 節點類的實現如下：

package?Tree;

import?Element.ElemItem;

/**
????*?左子樹-右兄弟樹節點數據結構，
?*/
public?class?LcRsTNode{
????//節點元素項
????private?ElemItem?elem;
????//節點序號
????private?int?idx;
????//節點的父節點
????private?int?parentNode;
????//節點的左子節點
????private?int?leftMostChildNode;
????//節點的右兄弟節點
????private?int?rightSiblingNode;
????
????//無參數構造函數
????public?LcRsTNode(){
????????elem?=?null;
????????parentNode?=?-1;
????????leftMostChildNode?=?-1;
????????rightSiblingNode?=?-1;
????}
????
????//有參數構造函數
????public?LcRsTNode(ElemItem?_elem,?
????????????????????int?_parentNode,
????????????????????int?_leftMtChild,?
????????????????????int?_rightSibling){
????????elem?=?_elem;
????????parentNode?=?_parentNode;
????????leftMostChildNode?=?_leftMtChild;
????????rightSiblingNode?=?_rightSibling;
????}
????
????//設置節點的序號
????public?void?setIdx(int?_idx){
????????idx?=?_idx;
????}
????
????//獲取節點的序號
????public?int?getIdx(){
????????return?idx;
????}
????
????//獲取元素項
????public?ElemItem?getElem()?{
????????return?elem;
????}
????
????//設置元素項
????public?void?setElem(ElemItem?_elem)?{
????????elem?=?_elem;
????}
????
????//獲取節點的父節點
????public?int?parent()?{
????????return?parentNode;
????}
????
????//獲取節點的最左子節點
????public?int?leftMostChild()?{
????????return?leftMostChildNode;
????}

????//獲取節點的右兄弟節點
????public?int?rightSibling()?{
????????return?rightSiblingNode;
????}
????
????//重設節點的父節點
????public?void?setParent(int?n)?{
????????parentNode?=?n;
????}
????
????//重設節點的最左子節點
????public?void?setLeftMostChild(int?n)?{
????????leftMostChildNode?=?n;
????}
????
????//重設節點的右兄弟節點
????public?void?setNextSibling(int?n)?{
????????rightSiblingNode?=?n;
????}
????
????//節點是否是葉節點
????public?boolean?isLeaf()?{
????????return?leftMostChildNode?==?-1;
????}
????
????//返回元素項String形式
????public?String?toString(){
????????return?elem.getElem().toString();
????}
}

?? 由于節點之間連接關系的表示方法與子節點表描述法有所不同，對用LsRs法描述的樹的操作方法也有所變化。

向樹中插入新的節點時，同樣需要指明帶插入的節點在節點數組中的序號self_idx及其父節點的序號p_idx。如果父節點為空，則直接設置p_idx處節點的內容。否則，首先設置self_idx的內容，此時self_idx處節點的左子節點和右兄弟節點都為空，其父節點序號為p_idx。關鍵的步驟是將self_idx賦值給當前p_idx的最右子節點的右兄弟節點，即將self_idx設置為p_idx處節點的新的最右兄弟節點。這一過程需要迭代地尋找當前的最右兄弟節點。這一過程的實現復雜度較節點表描述法要高一些，因為在節點表描述法中p_idx處的最右子節點可以直接通過獲取。

節點刪除包含兩個函數，removeChild和removeSon。在刪除序號為nidx的節點時，首先要先刪除該節點的所有子節點，然后再刪除節點自身。在刪除該節點的子節點時，需要首先找到該節點的最左子節點，然后遞歸調用刪除節點的函數刪除左子節點和它的右兄弟節點（及其子節點）。如果該節點沒有子節點，即其最左子節點為空，則直接調用removeSon函數刪除該節點。removeSon函數在刪除節點nidx時，首先找到該節點的父節點p，如果nidx是p的最左子節點則將p的最左子節點重新置為nidx的右兄弟節點，并將當前樹中節點數減一。如果nidx不是p的最左子節點，則需要先找到右兄弟節點為nidx的節點idx，并將idx的右兄弟節點重置為nidx的兄弟節點，同時將樹中當前的節點數減一。

最后討論一下樹的這種實現方法下前序打印樹中各個節點的函數，即preOrder函數。preOrder函數也是一個遞歸函數，該函數從高度為h的節點pos開始該打印，并遞歸地在適當的高度打印pos節點的子節點。該函數函數調用了函數printnode，printnode函數的功能是在特定的高度h打印節點的內容。在打印整個樹的函數為ford_print_tree，該函數中將preOrder的輸入初始節點序號置為根節點，高度置為0即可實現打印整棵樹的功能。

下面用類似于“子節點表”法的示例樹結構測試“左子節點/右兄弟節點”方法。實例代碼如下：

package?Tree;
????
????import?Element.ElemItem;
????
????/**
?????*
?????*?左子節點/右兄弟節點描述法示例程序，
?????*?包括樹的創、節點刪除和樹的前序遍歷打印
?????*/
????public?class?ExampleLcRsTree?{
????????public?static?void?main(String[]?args){
????????????LcRsTree?lrTree?=?new?LcRsTree(100);
????????????lrTree.addChild(0,?0,?
????????????????????new?ElemItem<String>("Root"));
????????????lrTree.addChild(0,?1,?
????????????????????new?ElemItem<String>("C:"));
????????????lrTree.addChild(0,?2,?
????????????????????new?ElemItem<String>("D:"));
????????????lrTree.addChild(0,?3,?
????????????????????new?ElemItem<String>("E:"));
????????????lrTree.addChild(1,?4,?
????????????????????new?ElemItem<String>("System"));
????????????lrTree.addChild(1,?5,?
????????????????????new?ElemItem<String>("Programme"));
????????????lrTree.addChild(2,?6,?
????????????????????new?ElemItem<String>("EBook"));
????????????lrTree.addChild(2,?7,?
????????????????????new?ElemItem<String>("Game"));
????????????lrTree.addChild(3,?8,?
????????????????????new?ElemItem<String>("Work"));
????????????lrTree.addChild(3,?9,?
????????????????????new?ElemItem<String>("Paper"));
????????????lrTree.addChild(8,?10,?
????????????????????new?ElemItem<String>("Java?Algo"));
????????????lrTree.addChild(8,?11,?
????????????????????new?ElemItem<String>("Java?Code"));
????????????lrTree.addChild(6,?12,?
????????????????????new?ElemItem<String>("Communication?Network"));
????????????lrTree.addChild(7,?13,?
????????????????????new?ElemItem<String>("LianLianKan"));
????????????lrTree.addChild(7,?14,?
????????????????????new?ElemItem<String>("LianLianKan2"));
????????????lrTree.addChild(7,?15,?
????????????????????new?ElemItem<String>("LianLianKan3"));
????????????lrTree.addChild(7,?16,?
????????????????????new?ElemItem<String>("LianLianKan4"));
????????????System.out.println("整棵樹的節點如下：");
????????????lrTree.ford_print_tree();
????????????System.out.println("刪除節點二以及其子樹后樹的節點如下：");
????????????lrTree.removeChild(2);
????????????lrTree.ford_print_tree();
????????}
????}

該實例程序中，同樣先調用addChild函數向樹中添加節點，從而構建整個樹。調用ford_print_tree函數打印整棵樹。然后調用removeChild函數刪除樹中的第二個節點及其子樹。實例代碼的運行結果如下：

從運行結果可以看出，樹被前序打印出來，其顯示方式符合我們對樹結構的正常觀察順序。刪除節點2后樹中的節點數從原來的17個變為9個，減少的8個節點正好為節點2和其子樹的節點個數。

轉載于:https://www.cnblogs.com/ajian005/archive/2012/11/08/2841162.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的5. 树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： [存储引擎基础知识]InnoDB与MyI
下一篇： android NDK 知识汇总