本文分享自華為云社區(qū)《樹、二叉樹和森林的表示及相互轉(zhuǎn)換-云社區(qū)-華為云》，作者：1+1=王。
樹的基本概念（1）樹的根沒有前驅(qū)，除根外的其他節(jié)點(diǎn)有且僅有一個(gè)前驅(qū)；
（2）每個(gè)節(jié)點(diǎn)都可以有零個(gè)或多個(gè)后繼。
（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）路徑長度：路徑上所經(jīng)過的邊的個(gè)數(shù)。
（10）森林：m（m >= 0）棵互不相交的樹的集合。二叉樹的基本概念
（1）滿二叉樹：一棵高度為h，且含有2^h - 1個(gè)節(jié)點(diǎn)的二叉樹。
（2）完全二叉樹：對應(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的二叉排序樹。
（1）二叉樹的第i層上至多有2^i-1^個(gè)節(jié)點(diǎn)；
（2）深度為h的二叉樹至多有2^k^ - 1個(gè)節(jié)點(diǎn)；
（3）對任何一個(gè)二叉樹，若其終端節(jié)點(diǎn)樹為n0，度為2的節(jié)點(diǎn)樹為n2，則n0 = n2 + 1;
（4）具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為log~2~(n + 1)向上取整。
（5）對完全二叉樹按從上到下、從左到右的順序依次編號(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)
typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;樹的存儲(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{//樹結(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{//樹結(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;樹、二叉樹和森林的相互轉(zhuǎn)換樹轉(zhuǎn)換為二叉樹
點(diǎn)擊下方，第一時(shí)間了解華為云新鮮技術(shù)~
華為云博客_大數(shù)據(jù)博客_AI博客_云計(jì)算博客_開發(fā)者中心-華為云
#華為云開發(fā)者聯(lián)盟#
