本文分享自華為云社區(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)盟#
