本文分享自華為云社區(qū)《樹(shù)、二叉樹(shù)和森林的表示及相互轉(zhuǎn)換-云社區(qū)-華為云》,作者:1+1=王。
樹(shù)的基本概念(1)樹(shù)的根沒(méi)有前驅(qū),除根外的其他節(jié)點(diǎn)有且僅有一個(gè)前驅(qū);
(2)每個(gè)節(jié)點(diǎn)都可以有零個(gè)或多個(gè)后繼。
(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ù)的基本概念
(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ù)。
(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)
typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;
樹(shù)的存儲(chǔ)結(jié)構(gòu)
#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;
#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;
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ù)
點(diǎn)擊下方,第一時(shí)間了解華為云新鮮技術(shù)~
華為云博客_大數(shù)據(jù)博客_AI博客_云計(jì)算博客_開(kāi)發(fā)者中心-華為云
#華為云開(kāi)發(fā)者聯(lián)盟#