侵權投訴

樹的遞歸結構和樹的存儲結構分析

39度創意研究所 2020-10-16 14:33 次閲讀

樹的遞歸結構

從一張圖中解釋什麼是樹

這張圖,主要講解關於cart這個單詞的所有的可能組合,按照常理,需要先考慮三個字母的排列,然後對三個字母進行拆分,直到最後一個節點,這個過程就類似於樹 到底什麼是樹

什麼是樹

樹是節點集合(A tree is a collection of nodes),

集合:集合是允許一個元素都沒有的集合,稱之為空集。

首先,集合是允許一個元素都沒有的集合,稱之為空集,那麼書是不是也允許一個節點都沒有的呢,是的,一個節點都沒有的樹,稱之為空樹,如果不是空的,則會存在根節點r和零個或更多非空子樹,T1,T2.。。Tk,他們的根由來自r的有向連接,什麼叫有向邊,大致可以理解為箭頭。用圖的關係説明樹的內部關係

根節點(root)一棵樹只有一個跟節點,所有的節點都在該節點的下面,嘗試把圖倒過來看,可以看成一個我們日常見到的數的根部,在這裏顯然字母A就是這顆樹的根節點。

子節點,父節點,一個節點,它對應的下面有連這的節點,那麼被連着的節點就是這個節點的子節點,也叫做孩子,那麼這個節點叫做被連接的節點的父親,看圖,B被A連這,所以B是A的一個孩子,同理,CDE等等這一行都是A的孩子,同時F,它連這K L M 同時被A連這,那麼F是A的一個孩子,同時又是K L M 的父親。

樹葉:樹葉就是那些沒有孩子的節點,比如B,C,D等等,例如下圖的綠色部分。

兄弟: 按照我們的理解,同一個父母生的當然是兄妹,如下圖所示,顏色相同的都是兄妹

路徑 我們同樣可以定義從父親到他孩子的路徑,下面的路徑,我們就取上圖的一部分,一個子樹,作為例子

比如,A->O的路徑為A->E->J->O它的長度為3,實際為它的邊數,圖中紅色的部分。

節點的深度:節點的深度指的是節點到樹根的長度,看下圖,我們可以輕易的知道,j節點的深度為2,可以理解為 A-> E -> J 邊長為2.顯然,此時根節點的深度為0.

節點的高度:高度是從節點到葉子的最長路徑,比如節點F的高度為1,顯然所有葉子節點高度為0.

樹的高度,樹的高度是跟的高度,顯然在這圖中,樹的高度為3,A->O

樹的特點

按照正常的邏輯,一個人不能同時有兩個父親,所以樹也一樣,下圖的兩個就解釋了這個問題

一顆正常的樹,它的樹枝是不會長成一個圓的,所以,樹中,是不可能出現環形的。圖中,紅色箭頭構成了一個環,所以都不是一顆樹。

樹的存儲結構

樹的存儲結構有三種,分別為,雙親表示法,孩子表示法,孩子兄弟表示法。

雙親表示法

假設一組連續空間保存着樹的特點,同時在每個節點中,附帶一個指示器表示雙親節點中鏈表的為位置,也就是説,每個節點除了知道自己是誰以外,還知道他的雙親在哪裏。

其中data是數據域,存儲結點的數據信息。而parent是指針域,存儲該結點的雙親在數組中的下標。

  //樹的雙親表示法結點結構定義  #define MAX_TRUE_SIZE 100  typedef int TElemType //樹結點的數據類型    //結點結構  typedef struct PTNode     {  	TElemType data;  //結點數據  	int parent;   	//雙親位置  }PTNode    //樹結構  typedef struct  {  	PTNode nodes[MAX_TRUE_SIZE];  //結點數組  	int r,n     //根的位置和結點數  }PTree

有了這樣的數據結構就可以來實現雙親表示法。由於根結點是沒有雙親的,所以我們約定根結點的位置域設置為-1,這也就意味着,我們所有的結點都存有他雙親的位置。如圖1-2中的樹結構和表1-3中的樹雙親表示。

這樣的存儲結構,我們可以根據結點的parent’指針很容易找到他的雙親結點,時間複雜度為O(1),直到parent為-1時,表示找到了樹結點的根

孩子表示法

換一種完全不同的考慮方法,由於樹中每個結點可能有多棵子樹,可以考慮用多重鏈表。每個結點有多個指針域,其中每個指針指向一顆子樹的根結點,我們把這種方法叫做多重鏈表的表示方法。不過,樹的每個結點的度,也就是他的孩子個數是不同的,所以設計兩種方法:

方案一

指針域的個數就等於樹的度,樹的度就是樹各個結點度的最大值。其結構如圖

其中data是數據域,child1到childd是指針域,用來指向該結點的孩子結點。對於圖1-1來説,樹的度是3,所以我們指針域個數就是3,

方案二

每個結點指針域的個數等於該結點的度,我們專門取一個位置來存儲結點指針的個數。

data為指針域,degree為度域,也就是存儲該結點的孩子結點的個數

這就是我們要説的孩子表示法,把每個結點的孩子都排列起來,以單鏈表為存儲結構,則n個結點有n個孩子鏈表,如果是葉子結點則此單鏈表為空。然後n個頭指針又組成一個線性表,採用順序存儲結構,存放進一個一維數組,

為此,設計兩種存儲結構,一個是孩子鏈表的孩子結點,

child是數據域,用來存儲某個結點在表頭數組中的下標。next是指針域,用來存儲指向結點的下一個孩子結點的指針。另一個是表頭數組的表頭結點。

data是數據域,存儲某結點的數據信息,firstchild是頭指針域,存儲該結點的孩子鏈表的頭指針。

  //樹的孩子表示法結構定義  #define MAX_TRUE_SIZE 100  typedef struct CTNode  //孩子結點  {  	int child;  	struct CTNode *next;  }*ChildPtr;  //表頭結構  typedef struct  {  	TElemType data;  	ChildPtr firstchild;  }CTBox;  //樹結構  typedef struct  {  	CTBox nodes[MAX_TRUE_SIZE];  //結點數組  	int r,n;               //根的位置和結點數  }CTree

把把雙親表示法和孩子表示法綜合一下表示如下

這種表示法叫做雙親孩子表示法,應該算是孩子表示法的改進。

孩子兄弟表示法

任一棵樹,它的結點的第一個孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此。我們設置兩個指針,分別指向該結點的第一個孩子和此結點的右兄弟。

data是數據域,fitstchild為指針域,存儲該結點的第一個孩子結點的存儲地址,rightsib是指針域,存儲該結點的右兄弟結點的存儲位置。

  //孩子兄弟表示法結構定義  typedef struct CSDNode  {  	TElemType data;  	struct CSNode *firstchild,*rightsib;  }CSNode,*CSTree;

這種方法的示意圖如下所示

這種表示法,給查找某個結點的某個孩子帶來了方便,只需要通過firstchild找到此結點的長子,然後在通過長子結點的rightsib找到它的二弟,接着一直找下去,直到找到具體的孩子。
編輯:hfy

收藏 人收藏
分享:

評論

相關推薦

隊列的概念

隊列是一個線性的數據結構,並且這個數據結構只允許在一端進行插入,另一端進行刪除,禁止直接訪問除這兩端....
的頭像 玩轉單片機 發表於 10-30 11:39 38次 閲讀
隊列的概念

常見數據結構以及面試中的高頻手撕算法題

簡單的説就是向 head 指向的鏈表的 ind 位置插入一個由 a 指向的節點,返回值為插入新節點後....
的頭像 算法與數據結構 發表於 10-30 09:56 111次 閲讀
常見數據結構以及面試中的高頻手撕算法題

計算機編程領域的知識

那的確可以把數學優先級放後面一點,用得確實不多,不過上數學課的時候總該認真聽下吧,拿個高績點也是百利....
的頭像 算法與數據結構 發表於 10-30 09:51 176次 閲讀
計算機編程領域的知識

什麼是“紅黑樹”看了就知道

今天我們要説的紅黑樹就是就是一棵非嚴格均衡的二叉樹,均衡二叉樹又是在二叉搜索樹的基礎上增加了自動維持平衡的性質,插入、搜...
發表於 10-27 17:00 30次 閲讀
什麼是“紅黑樹”看了就知道

如何使用鄰接樹的數據結構提高遺傳算法的挖掘效率

為提高複雜網絡中遺傳算法的子圖挖掘效率,在鄰接表的鏈式結構基礎上加入雙樹狀結構,作為一種新型數據結構....
發表於 10-23 11:47 35次 閲讀
如何使用鄰接樹的數據結構提高遺傳算法的挖掘效率

深度解析Linux網絡路徑及sk_buff struct 數據結構

理解 Linux 網絡棧(1):Linux 網絡協議棧簡單總結 本系列文章總結 Linux 網絡棧,....
的頭像 39度創意研究所 發表於 10-22 15:04 431次 閲讀
深度解析Linux網絡路徑及sk_buff struct 數據結構

數據結構中堆棧出棧序列問題解析

這是工作中遇到的小問題。 數據結構中有一種數據類型堆棧,該結構中的數據項有如下特點: 除了最前面和最....
的頭像 39度創意研究所 發表於 10-19 15:46 206次 閲讀
數據結構中堆棧出棧序列問題解析

Git 底層知識:詳細分析對象查詢流程和算法

本文將系統分享 Git 底層知識:對象生命週期變化,底層數據結構,數據包文件結構,數據包文件索引,以....
的頭像 39度創意研究所 發表於 10-13 15:29 562次 閲讀
Git 底層知識:詳細分析對象查詢流程和算法

一文了解go hashmap(數據結構、實現原理、讀寫操作)

這是看着別人的文章結合源碼來整理的自己一套理解 理解 Golang 哈希表 Map 的原理​drav....
的頭像 39度創意研究所 發表於 09-30 16:19 303次 閲讀
一文了解go hashmap(數據結構、實現原理、讀寫操作)

什麼是數據結構 數據及數據之間的關係分析

數據結構,直白地理解,就是研究數據的存儲方式。 我們知道,數據存儲只有一個目的,即為了方便後期對數據....
的頭像 39度創意研究所 發表於 09-30 16:14 319次 閲讀
什麼是數據結構 數據及數據之間的關係分析

一堂數據結構和算法的基礎課

遞歸空間 O(logn):遞歸是一個比較特殊的場景。雖然遞歸代碼中並沒有顯式的聲明變量或集合,但是計....
的頭像 算法與數據結構 發表於 09-03 10:28 303次 閲讀
一堂數據結構和算法的基礎課

《程序設計與數據結構》【丹陽到香港快遞】分享!

       在程序設計過程中,很多開發人員在沒有全局思維的把控,科學、系統的組織以及嚴密的測試與部署下,...
發表於 08-31 16:20 187次 閲讀
《程序設計與數據結構》【丹陽到香港快遞】分享!

一文讀懂緩存淘汰算法:LFU 算法

從實現難度上來説,LFU 算法的難度大於 LRU 算法,因為 LRU 算法相當於把數據按照時間排序,....
的頭像 算法與數據結構 發表於 08-25 17:37 496次 閲讀
一文讀懂緩存淘汰算法:LFU 算法

C語言教程之數據類型的學習課件免費下載

一個程序應包括兩個方面的內容: 1. 數據的描述(數據結構) 2. 操作的描述(即操作步驟、算法....
發表於 08-17 16:38 76次 閲讀
C語言教程之數據類型的學習課件免費下載

page struct的三種存放方式

隨着內存容量的增加,相對應的page struct也就增加。而這部分內存和其他的內存略有不同,因為這....
的頭像 Linuxer 發表於 08-03 16:33 392次 閲讀
page struct的三種存放方式

光纖通道到以太網存儲結構解析

行業專家認為,以太網存儲結構(ESF)是下一代存儲網絡的理想選擇,因為其具有卓越的性能、智能和效率。
發表於 07-21 15:59 131次 閲讀
光纖通道到以太網存儲結構解析

Python參考手冊第4版PDF電子書免費下載

本書是Python編程語言的傑出參考手冊,書中詳盡講解了Python核心和Python庫中重要的部分....
發表於 07-17 08:00 122次 閲讀
Python參考手冊第4版PDF電子書免費下載

數據結構C語言版習題集答案合集免費下載

1.1 簡述下列術語:數據,數據元素、數據對象、數據結構、存儲結構、數據類型和抽象數據類型。解:數據....
發表於 06-23 08:00 86次 閲讀
數據結構C語言版習題集答案合集免費下載

Ruby編程語言PDF電子書免費下載

《Ruby編程語言》詳細介紹了Ruby 1.8和1.9版本各方面的內容。在對Ruby進行了簡要的綜述....
發表於 06-12 08:00 51次 閲讀
Ruby編程語言PDF電子書免費下載

請問大神這種數據結構一般如何解析額?

請問大神,這種數據結構一般如何解析額。。 不太懂。。 ...
發表於 06-10 09:27 41次 閲讀
請問大神這種數據結構一般如何解析額?

棧是一種LIFO後入先出的什麼數據結構?

棧在哪裏定義大小,定多大合適?這可能很多剛接觸單片機開發的同學不是太清楚,下面就將比較常見的IAR開....
的頭像 lhl545545 發表於 06-09 09:26 1053次 閲讀
棧是一種LIFO後入先出的什麼數據結構?

面向對象與C++程序設計實驗之熟悉開發環境和簡單程序設計的資料説明

練習string類的使用。掌握string類的insert,erase,find,replace等常....
發表於 06-09 08:00 75次 閲讀
面向對象與C++程序設計實驗之熟悉開發環境和簡單程序設計的資料説明

為什麼Linux如此流行?

Linux是免費的。你不需要為使用Linux而付費,你可以自由查看,編輯和分發源代碼。當你購買裝有W....
的頭像 電子工程技術 發表於 06-08 16:31 581次 閲讀
為什麼Linux如此流行?

python算法圖解PDF電子書免費下載

本書示例豐富,圖文並茂,以簡明易懂的方式闡釋了算法,旨在幫助程序員在日常項目中更好地利用算法為軟件開....
發表於 06-04 08:00 24次 閲讀
python算法圖解PDF電子書免費下載

你要的算法和數據結構的學習路線來了!

大公司更注重基礎紮實,發展潛力,而小公司希望你立刻、馬上為他幹活,通常是沒什麼技術含量的活。小公司喜....
的頭像 算法與數據結構 發表於 06-03 17:21 823次 閲讀
你要的算法和數據結構的學習路線來了!

數據結構C語言題集電子書免費下載

本文檔的主要內容詳細介紹的是數據結構C語言題集電子書免費下載。
發表於 06-01 08:00 115次 閲讀
數據結構C語言題集電子書免費下載

數據結構的基本概念是什麼

數據結構之基本概念
發表於 05-27 08:29 32次 閲讀
數據結構的基本概念是什麼

請問C怎麼提高啊??

C怎麼提高啊,指針結構體,數據結構完全明白,有什麼實戰練習嗎 ? 要打好什麼基礎?如何能通過做方案來提高自己啊?...
發表於 05-24 23:58 32次 閲讀
請問C怎麼提高啊??

DeBug太枯燥?讓VS Code畫個圖

寫代碼,難免會遇到各種神奇的問題,代碼短我們在腦海中「運行」一遍也就差不多能找出原因。但代碼要是比較....
的頭像 人工智能愛好者社區 發表於 05-12 09:19 1313次 閲讀
DeBug太枯燥?讓VS Code畫個圖

數據結構C語言版電子書免費下載

本書的前半部分從抽象數據類型的角度討論各種基本類型的數據結構及其應用;後半部分主要討論查找和排序的各....
發表於 05-12 08:00 201次 閲讀
數據結構C語言版電子書免費下載

程序設計與數據結構電子書免費下載

在學習程序設計時,很多初學者常常會陷入這樣的誤區,他們總將阻礙個人成長的原因歸結為缺少機會。其實問題....
發表於 05-10 08:00 96次 閲讀
程序設計與數據結構電子書免費下載

常見的數據結構

數據結構在實際應用中非常常見,現在各種算法基本都牽涉到數據結構,因此,掌握數據結構算是軟件工程師的必備技能。 一、什麼是...
發表於 05-10 07:58 291次 閲讀
常見的數據結構

我的第一本算法書電子書免費下載

本書採用大量圖片,通過詳細的分步講解,以直觀、易懂的方式展現了 7 個數據結構和 26 個基礎算法的....
發表於 05-08 08:00 131次 閲讀
我的第一本算法書電子書免費下載

一個數據結構-線段樹

對於求區間和的問題,前綴和數組 是一個不錯的選擇,構建好前綴和數組後,求一個區間和的話只要前後一減就....
的頭像 算法與數據結構 發表於 05-06 11:02 1026次 閲讀
一個數據結構-線段樹

一道LeetCode的多種解法

對於這道題目,因為我們要求的是子串的長度,因此我們可以考慮在棧中保存 index,這樣子我們不僅可以....
的頭像 算法與數據結構 發表於 05-06 10:39 956次 閲讀
一道LeetCode的多種解法

Linux內核快速處理路徑儘量多用kmem_cache而慎用kmalloc

僅僅為了測試是否會宕機,所以我的所有的數據結構的hash值均是一樣的,這樣插入200個項的話,它們會....
的頭像 Linuxer 發表於 04-30 15:35 1216次 閲讀
Linux內核快速處理路徑儘量多用kmem_cache而慎用kmalloc

企業如何解決數據科學家短缺詳細方法什麼

 隨着企業以數據為中心的文化,以做出決策和規劃,數據科學家對全球企業的重要性日益增加。但是企業無法足....
的頭像 Wildesbeast 發表於 04-18 10:31 1406次 閲讀
企業如何解決數據科學家短缺詳細方法什麼

是什麼使神經網絡變成圖神經網絡?

這是一種很靈活的數據結構,它囊括了很多其他的數據結構。例如,如果沒有邊,那麼它就會變成一個集合;如果....
的頭像 倩倩 發表於 04-17 10:18 682次 閲讀
是什麼使神經網絡變成圖神經網絡?

哈希表是什麼?為什麼需要使用哈希表

我們在這篇文章將要學習最有用的數據結構之一—哈希表,哈希表的英文叫 Hash Table,也可以稱為....
的頭像 Wildesbeast 發表於 04-06 13:50 2080次 閲讀
哈希表是什麼?為什麼需要使用哈希表

這些程序員必須知道的數據結構你知道多少

數據結構是一種特殊的組織和存儲數據的方式,可以使我們可以更高效地對存儲的數據執行操作。數據結構在計算....
的頭像 Wildesbeast 發表於 04-06 12:09 845次 閲讀
這些程序員必須知道的數據結構你知道多少

程序設計與數據結構PDF電子書免費下載

1. C語言學習中的痛點:針對當前工程師在C語言學習中的痛點,如指針函數與函數指針,如何靈活應用結構....
發表於 03-24 08:00 189次 閲讀
程序設計與數據結構PDF電子書免費下載

環形緩衝區的實現原理

在通信程序中,經常使用環形緩衝區作為數據結構來存放通信中發送和接收的數據。環形緩衝區是一個先進先出的....
的頭像 西西 發表於 03-22 10:03 1390次 閲讀
環形緩衝區的實現原理

C51的數據結構詳細課件詳細説明

 在C51語言中,除了整型(int)、浮點型(float)、字符型(char)、無值型(void)幾....
發表於 03-17 16:41 114次 閲讀
C51的數據結構詳細課件詳細説明

unix基本概念彙總

unix是一種搶佔式多任務系統,我們常説的多人多任務系統,就是一台主機可以允許多個人多個任務共同運行....
發表於 03-11 16:19 69次 閲讀
unix基本概念彙總

數據結構有哪些知識重點

不管你現在是不是需要用到數據結構的相關知識,在工作的過程中理解、掌握好數據結構,對現在的工作和以後的....
發表於 03-06 10:05 194次 閲讀
數據結構有哪些知識重點

淺談STM32CubeMX的理解心得與運用

用心去學習STM32CubeMX,你會有不一樣的收穫
的頭像 黃工的嵌入式技術圈 發表於 03-03 14:17 5501次 閲讀
淺談STM32CubeMX的理解心得與運用

數據結構與算法知識點有哪些?

數據結構與算法的知識點有哪些?
的頭像 黃工的嵌入式技術圈 發表於 01-10 15:22 2548次 閲讀
數據結構與算法知識點有哪些?

數據結構的簡介和線性表及棧隊列和數組的詳細説明

兩項基本任務:數據表示,數據處理 軟件系統生存期:軟件計劃,需求分析,軟件設計,軟件編碼,軟件測試....
發表於 01-06 08:00 158次 閲讀
數據結構的簡介和線性表及棧隊列和數組的詳細説明

仿人機器人PDF電子書免費下載

《仿人機器人》是2007年清華大學出版社出版的圖書,作者是梶田秀司。本書內容包括仿人機器人學的運動學....
發表於 01-03 18:03 545次 閲讀
仿人機器人PDF電子書免費下載

數據結構的代碼和工程文件合集免費下載

本文檔的主要內容詳細介紹的是數據結構的C語言代碼和工程文件合集免費下載包括了:按元素類型將單鏈表改為....
發表於 01-02 08:00 174次 閲讀
數據結構的代碼和工程文件合集免費下載

Python Cookbook中文第三版PDF電子書免費下載

《Python Cookbook(第3版)中文版》介紹了Python應用在各個領域中的一些使用技巧和....
發表於 11-15 08:00 264次 閲讀
Python Cookbook中文第三版PDF電子書免費下載

使用索引對子圖查詢技術研究有怎麼樣的進展了

圖作為表示實體間的數據結構,在社區發現、生物化學分析、社會安全分析等數據關聯性要求較高的領域有着廣泛....
發表於 11-13 17:43 144次 閲讀
使用索引對子圖查詢技術研究有怎麼樣的進展了

數據結構C語言版PDF電子書免費下載

《數據結構》(C語言版)是為“數據結構”課程編寫的教材,也可作為學習數據結構及其算法的C程序設計的參....
發表於 11-13 15:16 236次 閲讀
數據結構C語言版PDF電子書免費下載

為什麼Labview程序增加一部分,波形不顯示了

如圖程序,去掉紅框,波形採集正常,加上紅框部分,波形就不採集不顯示了,這個可能是什麼原因呢,謝謝。 ...
發表於 10-22 20:21 457次 閲讀
為什麼Labview程序增加一部分,波形不顯示了

腳本語言的概述和與其他編程語言的關係及特點以及程序舉例的詳細説明

腳本語言,腳本語言或擴建的語言,又叫動態語言。是一種編程語言控制軟件應用程序。腳本通常以文本(如AS....
發表於 10-15 15:26 268次 閲讀
腳本語言的概述和與其他編程語言的關係及特點以及程序舉例的詳細説明

數據結構與算法分析—C語言描述

《數據結構與算法分析:C語言描述》曾被評為20世紀頂尖的30部計算機著作之一,作者在數據結構和算法分....
發表於 10-14 08:00 300次 閲讀
數據結構與算法分析—C語言描述

什麼是數據結構?數據結構的詳細資料概述

隨着計算機軟、硬件的發展,計算機的應用範圍在不斷擴大,計算機所處理的數據的數量也在不斷擴大,計算機所....
發表於 10-14 08:00 279次 閲讀
什麼是數據結構?數據結構的詳細資料概述

求推薦一本好用的數據結構的書!

RT
發表於 08-27 22:18 376次 閲讀
求推薦一本好用的數據結構的書!

請問數據結構對弄單片機重要嗎?

數據結構的知識對弄單片機的人重不重要啊 大家都學得怎麼樣啊?...
發表於 04-12 02:43 583次 閲讀
請問數據結構對弄單片機重要嗎?

數據結構試題庫,含答案

學習IT技術最多的就是練習題了,讓理論與實踐相結合,這樣學習才是有效的,下面是一美女學霸,在一次次測試中,總結的常見的數...
發表於 03-07 16:19 1672次 閲讀
數據結構試題庫,含答案