在线观看www成人影院-在线观看www日本免费网站-在线观看www视频-在线观看操-欧美18在线-欧美1级

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

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

454398 ? 來源:機器之心 ? 作者:小小 ? 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

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • 數據結構
    +關注

    關注

    3

    文章

    573

    瀏覽量

    40623
  • 存儲結構
    +關注

    關注

    0

    文章

    21

    瀏覽量

    9812
收藏 人收藏

    評論

    相關推薦
    熱點推薦

    白話理解RCC時鐘(可下載)

    時鐘就像是單片機的“心臟”,單片機正常工作離不開時鐘的支持,下圖是我們單片機的時鐘 ,它反映了單片機的時鐘關系。我們來詳細描述一下時鐘的工作原理。寄存器上電后有一個復位值,大家看我畫紅線的這個
    發表于 03-27 13:50 ?0次下載

    【技術分享】迅為RK3568開發板使用TFTP加載內核設備

    【技術分享】迅為RK3568開發板使用TFTP加載內核設備
    的頭像 發表于 02-21 14:04 ?600次閱讀
    【技術分享】迅為RK3568開發板使用TFTP加載內核設備<b class='flag-5'>樹</b>

    求解答,設備問題

    請問,rk3588j要再提取一個USB3.0接口設備怎么改
    發表于 02-20 11:22

    對象存儲是什么結構類型?

    對象存儲屬于非結構化數據存儲架構,采用扁平化命名空間結構。其核心通過唯一標識符(ObjectID)定位數據對象,突破傳統文件系統的層級目錄限制,形成"桶-對象"兩級邏輯模型。數據以獨立
    的頭像 發表于 02-10 11:14 ?273次閱讀

    科技在物聯網方面

    科技在物聯網領域有多方面的涉及和發展,以下是一些具體信息: 傳感器技術合作 與傳感器公司合作:宇科技與一些傳感器技術公司有合作,例如奧比中光為宇機器狗提供激光雷達及結構光傳感
    發表于 02-04 06:48

    使用TFTP加載內核設備

    在嵌入式項目開發中,為了適配新外設、調整硬件資源分配或修復驅動問題,需要頻繁修改設備和內核。修改完成后,通常需要重新編譯生成鏡像,并將其燒錄到開發板上進行測試。然而,傳統的燒錄方式不僅需要連接物理接口,還可能因為鏡像體積較大而耗費較長時間,這在開發周期緊張的情況下顯得尤為低效。
    的頭像 發表于 01-17 15:52 ?1320次閱讀
    使用TFTP加載內核設備<b class='flag-5'>樹</b>

    嵌入式學習-飛凌嵌入式ElfBoard ELF 1板卡-初識設備之設備組成和結構

    的一項技能。設備的起源設備(Device Tree)是一種描述硬件資源的數據結構,它由uboot傳遞給Linux內核,被內核解析,內核根據設備中的硬件描述信息加載利用相應驅動資源
    發表于 01-08 08:32

    飛凌嵌入式ElfBoard ELF 1板卡-初識設備之設備組成和結構

    的一項技能。設備的起源設備(Device Tree)是一種描述硬件資源的數據結構,它由uboot傳遞給Linux內核,被內核解析,內核根據設備中的硬件描述信息加載利用相應驅動資源
    發表于 01-07 09:16

    什么是默克爾(Merkle Tree)?如何計算默克爾根?

    01 默克爾的概念 默克爾(Merkle Tree)是一種特殊的二叉,它的每個節點都存儲了一個數據塊的哈希值。哈希值是一種可以將任意長度的數據轉換為固定長度的字符串的算法,它具有
    的頭像 發表于 09-30 18:22 ?2068次閱讀
    什么是默克爾<b class='flag-5'>樹</b>(Merkle Tree)?如何計算默克爾根?

    鐵電存儲器的結構特點

    鐵電存儲器(Ferroelectric RAM, FRAM)是一種結合了RAM的快速讀寫能力和非易失性存儲特性的存儲技術。其結構特點主要體現在其獨特的材料構成、工作原理、物理
    的頭像 發表于 09-29 15:18 ?1017次閱讀

    存儲器的層次結構包括哪些

    存儲器的層次結構是計算機系統中一個關鍵且復雜的部分,它決定了數據的存儲、訪問和處理效率。存儲器的層次結構主要包括多個層次,每個層次都有其特定
    的頭像 發表于 09-10 14:28 ?1396次閱讀

    遞歸神經網絡和循環神經網絡的模型結構

    遞歸神經網絡是一種旨在處理分層結構的神經網絡,使其特別適合涉及樹狀或嵌套數據的任務。這些網絡明確地模擬了層次結構中的關系和依賴關系,例如語言中的句法結構或圖像中的層次表示。它使用
    的頭像 發表于 07-10 17:21 ?1195次閱讀
    <b class='flag-5'>遞歸</b>神經網絡和循環神經網絡的模型<b class='flag-5'>結構</b>

    遞歸神經網絡的實現方法

    (Recurrent Neural Network,通常也簡稱為RNN,但在此處為區分,我們將循環神經網絡稱為Recurrent RNN)不同,遞歸神經網絡更側重于處理樹狀或圖結構的數據,如句法分析樹、自然語言的語法
    的頭像 發表于 07-10 17:02 ?710次閱讀

    遞歸神經網絡結構形式主要分為

    結構形式。 Elman網絡 Elman網絡是一種基本的遞歸神經網絡結構,由Elman于1990年提出。其結構主要包括輸入層、隱藏層和輸出層,其中隱藏層具有時間延遲單元,可以
    的頭像 發表于 07-05 09:32 ?885次閱讀

    遞歸神經網絡的結構、特點、優缺點及適用場景

    識別、時間序列分析等領域有著廣泛的應用。本文將詳細介紹遞歸神經網絡的結構、特點、優缺點以及適用場景。 一、遞歸神經網絡的結構 基本
    的頭像 發表于 07-04 14:52 ?2494次閱讀
    主站蜘蛛池模板: 欧美特黄视频在线观看 | 免费在线观看a视频 | 天天草夜夜骑 | 日本不卡高清免费 | 中文字幕在线播放一区 | 网站色 | 国产在线操 | 日本三级带日本三级带黄首页 | dvd碟片色爱 | 午夜逼逼| 国产成人精品日本亚洲语音1 | 天天影视亚洲 | 999毛片免费观看 | 亚色在线 | 亚洲视频一区在线 | 久久色婷婷 | 午夜精品国产 | bt天堂在线www种子搜索 | 国产色综合一区二区三区 | 俄罗斯小屁孩cao大人免费 | 亚洲aⅴ久久久噜噜噜噜 | 亚洲444444在线观看 | xxxx69日本hd| 免费看很黄很色裸乳视频 | 色综色| 亚洲成人国产 | v天堂网| 日本一卡二卡3卡四卡网站精品 | 唐人呦一呦xxxx视频 | 国产三级日本三级在线播放 | 日本高清免费一本视频在线观看 | 午夜欧美成人久久久久久 | 2021年最热新版天堂资源中文 | 久草男人天堂 | 亚洲偷偷 | 自拍你懂的 | 失禁h啪肉尿出来高h男男 | 深夜释放自己vlog糖心旧版本 | 成人窝窝午夜看片 | 四虎永久免费网站入口2020 | 97人人插 |