免费人成动漫在线播放r18-免费人成观看在线网-免费人成黄页在线观看日本-免费人成激情视频在线观看冫-jlzzjlzz亚洲大全-jlzzjlzz亚洲日本

二維碼
企資網(wǎng)

掃一掃關(guān)注

當(dāng)前位置: 首頁 » 企資頭條 » 綜藝 » 正文

小白科普丨何為樹_二叉樹和森林

放大字體  縮小字體 發(fā)布日期:2023-03-08 21:19:12    作者:江明杰    瀏覽次數(shù):72
導(dǎo)讀

本文分享自華為云社區(qū)《樹、二叉樹和森林的表示及相互轉(zhuǎn)換-云社區(qū)-華為云》,作者:1+1=王。樹的基本概念樹的定義:樹是n(n = 0)個(gè)節(jié)點(diǎn)的==有限==集。當(dāng)n=0是,稱為空樹。樹的特點(diǎn):(1)樹的根沒有前驅(qū),除根外的

本文分享自華為云社區(qū)《樹、二叉樹和森林的表示及相互轉(zhuǎn)換-云社區(qū)-華為云》,作者:1+1=王。

樹的基本概念
  • 樹的定義:樹是n(n >= 0)個(gè)節(jié)點(diǎn)的==有限==集。當(dāng)n=0是,稱為空樹。
  • 樹的特點(diǎn):
    (1)樹的根沒有前驅(qū),除根外的其他節(jié)點(diǎn)有且僅有一個(gè)前驅(qū);
    (2)每個(gè)節(jié)點(diǎn)都可以有零個(gè)或多個(gè)后繼。
  • 術(shù)語:
    (1)節(jié)點(diǎn)的度:樹中一個(gè)節(jié)點(diǎn)的孩子個(gè)數(shù)。
    (2)樹的度:樹中節(jié)點(diǎn)的最大度。
    (3)分支節(jié)點(diǎn):度大于0的節(jié)點(diǎn)。
    (4)葉子結(jié)點(diǎn):度為0的節(jié)點(diǎn)。
    (5)節(jié)點(diǎn)的深度:從根節(jié)點(diǎn)開始自頂向下逐層累加。
    (6)節(jié)點(diǎn)的高度:從葉子節(jié)點(diǎn)開始自底向上逐層累加。
    (7)樹的高度:樹中節(jié)點(diǎn)的最大層數(shù)。
    (8)路徑:兩個(gè)節(jié)點(diǎn)之間所經(jīng)過的節(jié)點(diǎn)序列。
    (9)路徑長(zhǎng)度:路徑上所經(jīng)過的邊的個(gè)數(shù)。
    (10)森林:m(m >= 0)棵互不相交的樹的集合。二叉樹的基本概念
  • 二叉樹的定義:一種特殊的樹形結(jié)構(gòu),它的特點(diǎn)是每個(gè)節(jié)點(diǎn)至多有兩顆子樹(即二叉樹中不存在度大于2的節(jié)點(diǎn)),并且二叉樹的子樹有左右之分,不能隨意顛倒。
  • 幾種特殊的二叉樹:
    (1)滿二叉樹:一棵高度為h,且含有2^h - 1個(gè)節(jié)點(diǎn)的二叉樹。
    (2)完全二叉樹:對(duì)應(yīng)相同高度的滿二叉樹缺失最下層最右邊的一些連續(xù)葉子結(jié)點(diǎn)。
    (3)二叉排序樹:左子樹上所有節(jié)點(diǎn)的關(guān)鍵字都小于根節(jié)點(diǎn)的關(guān)鍵字;右子樹上所有節(jié)點(diǎn)的關(guān)鍵字都大于根節(jié)點(diǎn)的關(guān)鍵字;左子樹和右子樹又各是一棵二叉排序樹。(左 < 根 < 右)
    (4)平衡二叉樹:任一節(jié)點(diǎn)的左子樹和右子樹的深度之差不超過1的二叉排序樹。
  • 二叉樹的性質(zhì):
    (1)二叉樹的第i層上至多有2^i-1^個(gè)節(jié)點(diǎn);
    (2)深度為h的二叉樹至多有2^k^ - 1個(gè)節(jié)點(diǎn);
    (3)對(duì)任何一個(gè)二叉樹,若其終端節(jié)點(diǎn)樹為n0,度為2的節(jié)點(diǎn)樹為n2,則n0 = n2 + 1;
    (4)具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為log~2~(n + 1)向上取整。
    (5)對(duì)完全二叉樹按從上到下、從左到右的順序依次編號(hào)1,2,3,…,則有以下關(guān)系:
    a. 當(dāng)i>1時(shí),節(jié)點(diǎn)i的雙親的編號(hào)為i / 2;
    b. 當(dāng)2i<=n時(shí),節(jié)點(diǎn)i的左孩子編號(hào)為2i,否則無左孩子;
    c. 當(dāng)2i+1<=n時(shí),節(jié)點(diǎn)i的右孩子編號(hào)為2i+1,否則無右孩子;
    d.節(jié)點(diǎn)i所在層次為log~2~i + 1(向下取整)。存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)
  • 順序存儲(chǔ)結(jié)構(gòu):用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素,即將完全二叉樹上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在某個(gè)數(shù)組下標(biāo)為i-1的分量中。(適合完全二叉樹和滿二叉樹)
  • 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):使用鏈表節(jié)點(diǎn)來存儲(chǔ)二叉樹中的每個(gè)節(jié)點(diǎn)。二叉鏈表包括數(shù)據(jù)域data、左指針域lchild和右指針域rchild三個(gè)域。

    typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;樹的存儲(chǔ)結(jié)構(gòu)

  • 雙親表示法:用一組連續(xù)空間來存儲(chǔ)樹的每個(gè)結(jié)點(diǎn),同時(shí)在每個(gè)結(jié)點(diǎn)中,附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)到鏈表中的位置。

    #define MAX_TREE_SIZE 100//節(jié)點(diǎn)最大個(gè)數(shù)typedef struct PTNode{//節(jié)點(diǎn)結(jié)構(gòu)TElemType data;int parent;//雙親位置域}PTNode;typedef struct{//樹結(jié)構(gòu)PTNode nodes[MAX_TREE_SIZE ];int root,n;//根的位置和節(jié)點(diǎn)數(shù)}PTree;

  • 孩子表示法:將沒得節(jié)點(diǎn)的孩子節(jié)點(diǎn)都用單鏈表鏈接起來形成一個(gè)線性結(jié)構(gòu),此時(shí)n個(gè)節(jié)點(diǎn)就有n個(gè)孩子鏈表。

    #define MAX_TREE_SIZE 100//節(jié)點(diǎn)最大個(gè)數(shù)typedef struct CTNode{//孩子節(jié)點(diǎn)int child;struct CTNode *next;}*ChildPtr;typedef struct{TElemType data;ChildPtr firstChild;//孩子鏈表頭指針}CTBox;typedef struct{//樹結(jié)構(gòu)CTBox nodes[MAX_TREE_SIZE ];int root,n;//根的位置和節(jié)點(diǎn)數(shù)}CTree;

  • 孩子兄弟表示法(二叉樹表示法):以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)包括三部分內(nèi)容:節(jié)點(diǎn)值、指向第一個(gè)孩子結(jié)點(diǎn)的指針和指向下一個(gè)兄弟節(jié)點(diǎn)的指針。

    typedef struct CSNode{//節(jié)點(diǎn)結(jié)構(gòu)TElemType data;struct CSNode *firstChild,*nextSibling;}CSNode,*CSTree;樹、二叉樹和森林的相互轉(zhuǎn)換樹轉(zhuǎn)換為二叉樹

  • 規(guī)則:每個(gè)節(jié)點(diǎn)左指針指向它的第一個(gè)孩子,右指針指向它在樹中的相鄰右兄弟。由于根節(jié)點(diǎn)沒有兄弟,所以對(duì)應(yīng)的二叉樹沒有右子樹。
  • 畫法:(1)在兄弟節(jié)點(diǎn)之間加一條線;(2)在每棵樹根之間加一條線;(3)以第一棵根為軸心,順時(shí)針旋轉(zhuǎn)45度。森林轉(zhuǎn)換為二叉樹
  • 規(guī)則:先將森林中的每棵樹轉(zhuǎn)換為二叉樹,由于任何一棵和樹對(duì)應(yīng)的二叉樹的右子樹為空,若把森林中第二棵樹根視為第一棵樹根的右兄弟,即將第二棵樹對(duì)應(yīng)的二叉樹當(dāng)做第一棵二叉樹根的右子樹,將第三棵樹對(duì)應(yīng)的二叉樹當(dāng)做第二棵二叉樹根的右子樹…以此類推,即可將森林轉(zhuǎn)換為二叉樹。
  • 畫法:(1)將森林中的每棵樹轉(zhuǎn)換為二叉樹;(2)對(duì)每個(gè)節(jié)點(diǎn),只保留它與第一個(gè)孩子的連線;(3)以根為軸心,順時(shí)針旋轉(zhuǎn)45度。二叉樹轉(zhuǎn)換為森林
  • 若二叉樹非空,則二叉樹的根及其左子樹為第一棵樹的二叉樹形式,將根與右子樹斷開
  • 將右子樹視為一棵新的二叉樹,重復(fù)第一步。

    點(diǎn)擊下方,第一時(shí)間了解華為云新鮮技術(shù)~

    華為云博客_大數(shù)據(jù)博客_AI博客_云計(jì)算博客_開發(fā)者中心-華為云

    #華為云開發(fā)者聯(lián)盟#

  •  
    (文/江明杰)
    打賞
    免責(zé)聲明
    本文為江明杰推薦作品?作者: 江明杰。歡迎轉(zhuǎn)載,轉(zhuǎn)載請(qǐng)注明原文出處:http://www.bangpiao.com.cn/news/show-325434.html 。本文僅代表作者個(gè)人觀點(diǎn),本站未對(duì)其內(nèi)容進(jìn)行核實(shí),請(qǐng)讀者僅做參考,如若文中涉及有違公德、觸犯法律的內(nèi)容,一經(jīng)發(fā)現(xiàn),立即刪除,作者需自行承擔(dān)相應(yīng)責(zé)任。涉及到版權(quán)或其他問題,請(qǐng)及時(shí)聯(lián)系我們郵件:weilaitui@qq.com。
     

    Copyright ? 2016 - 2023 - 企資網(wǎng) 48903.COM All Rights Reserved 粵公網(wǎng)安備 44030702000589號(hào)

    粵ICP備16078936號(hào)

    微信

    關(guān)注
    微信

    微信二維碼

    WAP二維碼

    客服

    聯(lián)系
    客服

    聯(lián)系客服:

    在線QQ: 303377504

    客服電話: 020-82301567

    E_mail郵箱: weilaitui@qq.com

    微信公眾號(hào): weishitui

    客服001 客服002 客服003

    工作時(shí)間:

    周一至周五: 09:00 - 18:00

    反饋

    用戶
    反饋

    主站蜘蛛池模板: 午夜精品久久久久久久 | 欧美成a人片在线观看久 | va亚洲va欧美va国产综合 | 免费精品一区二区三区在线观看 | 国产精品香蕉在线一区 | 制服丝袜视频在线观看 | 最近2019中文免费字幕 | 久久笫一福利免费导航 | 国产精品福利午夜h视频 | 中文字幕日韩一区二区三区不卡 | 欧洲男女啪啪免费观看 | 黄色骚视频 | 无遮羞成人的动漫在线观看 | 中国一及黄色片 | 在线观看亚洲欧美 | 免费的涩涩视频 | 在线观看嗯啊成人动作片 | 日本一区二区三区久久 | 日本欧洲亚洲一区在线观看 | 日本天堂在线播放 | 久久多多屋影院三级 | www日韩免费高清视频 | 欧美二区在线观看 | 天天天天做夜夜夜做 | 欧美一区2区三区3区公司 | 欧美性极品hd高清视频 | 小黄视频免费观看 | 日韩在线aⅴ免费视频 | 亚洲va精品中文字幕动漫 | 日本韩国一区二区 | 99pao在线视频成精品 | 麻豆成人传媒一区二区 | 在线观看免费播放网址成人 | 久久99久久99精品免观看麻豆 | 99久久免费国产特黄 | 97在线免费视频 | 日本一本一道久久香蕉免费 | 国产区网址 | 成年男女免费大片在线观看 | 怡红院免费全部视频在线视频 | 国产最新精品2020好看的 |