二維碼
        企資網(wǎng)

        掃一掃關(guān)注

        當(dāng)前位置: 首頁(yè) » 企業(yè)資訊 » 資訊 » 正文

        小白科普丨何為樹(shù)_二叉樹(shù)和森林

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

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

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

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

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

      9. 雙親表示法:用一組連續(xù)空間來(lái)存儲(chǔ)樹(shù)的每個(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{//樹(shù)結(jié)構(gòu)PTNode nodes[MAX_TREE_SIZE ];int root,n;//根的位置和節(jié)點(diǎn)數(shù)}PTree;

      10. 孩子表示法:將沒(méi)得節(jié)點(diǎn)的孩子節(jié)點(diǎn)都用單鏈表鏈接起來(lái)形成一個(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{//樹(shù)結(jié)構(gòu)CTBox nodes[MAX_TREE_SIZE ];int root,n;//根的位置和節(jié)點(diǎn)數(shù)}CTree;

      11. 孩子兄弟表示法(二叉樹(shù)表示法):以二叉鏈表作為樹(shù)的存儲(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;樹(shù)、二叉樹(shù)和森林的相互轉(zhuǎn)換樹(shù)轉(zhuǎn)換為二叉樹(shù)

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

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

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

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

      18.  
        (文/江明杰)
        免責(zé)聲明
        本文僅代表作發(fā)布者:江明杰個(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)或其他問(wèn)題,請(qǐng)及時(shí)聯(lián)系我們刪除處理郵件:weilaitui@qq.com。
         

        Copyright ? 2016 - 2025 - 企資網(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

        反饋

        用戶
        反饋

        主站蜘蛛池模板: 免费无码一区二区| 无码精品不卡一区二区三区| 日韩美女视频一区| 国产一区二区三区亚洲综合| 久久国产三级无码一区二区| 国产精品电影一区| 久久精品视频一区| 亚洲av无码天堂一区二区三区| 精品熟人妻一区二区三区四区不卡 | 日本高清一区二区三区| 日本免费电影一区二区| 中文字幕一区二区三区乱码| 国产精品一区二区三区高清在线| 亚洲日韩AV无码一区二区三区人| 久久一区二区三区精品| 国产午夜精品一区二区三区漫画 | 一区二区视频在线| 无码精品蜜桃一区二区三区WW | 亚洲欧美日韩中文字幕在线一区| 中文字幕在线一区二区三区| 日本免费电影一区| 国产一区美女视频| 无码一区二区三区在线| 亚洲精品一区二区三区四区乱码| 亚洲AV无一区二区三区久久| 久久久久成人精品一区二区| 日韩人妻无码一区二区三区| 亚洲AV无码一区二区三区国产| 无码喷水一区二区浪潮AV| 人妻aⅴ无码一区二区三区| 精品久久久久中文字幕一区| 国产乱码精品一区二区三| 日韩精品一区二区午夜成人版| 韩国一区二区三区视频| 亚洲综合av一区二区三区| 亚洲另类无码一区二区三区| 国产精品视频免费一区二区| 日韩视频在线一区| 国产无吗一区二区三区在线欢| 免费人妻精品一区二区三区| 久久se精品一区二区影院|