本文分享自華為云社區(qū)《樹、二叉樹和森林的表示及相互轉換-云社區(qū)-華為云》，作者：1+1=王。
樹的基本概念（1）樹的根沒有前驅，除根外的其他節(jié)點有且僅有一個前驅；
（2）每個節(jié)點都可以有零個或多個后繼。
（1）節(jié)點的度：樹中一個節(jié)點的孩子個數。
（2）樹的度：樹中節(jié)點的最大度。
（3）分支節(jié)點：度大于0的節(jié)點。
（4）葉子結點：度為0的節(jié)點。
（5）節(jié)點的深度：從根節(jié)點開始自頂向下逐層累加。
（6）節(jié)點的高度：從葉子節(jié)點開始自底向上逐層累加。
（7）樹的高度：樹中節(jié)點的最大層數。
（8）路徑：兩個節(jié)點之間所經過的節(jié)點序列。
（9）路徑長度：路徑上所經過的邊的個數。
（10）森林：m（m >= 0）棵互不相交的樹的集合。二叉樹的基本概念
（1）滿二叉樹：一棵高度為h，且含有2^h - 1個節(jié)點的二叉樹。
（2）完全二叉樹：對應相同高度的滿二叉樹缺失最下層最右邊的一些連續(xù)葉子結點。
（3）二叉排序樹：左子樹上所有節(jié)點的關鍵字都小于根節(jié)點的關鍵字；右子樹上所有節(jié)點的關鍵字都大于根節(jié)點的關鍵字；左子樹和右子樹又各是一棵二叉排序樹。（左 < 根 < 右）
（4）平衡二叉樹：任一節(jié)點的左子樹和右子樹的深度之差不超過1的二叉排序樹。
（1）二叉樹的第i層上至多有2^i-1^個節(jié)點；
（2）深度為h的二叉樹至多有2^k^ - 1個節(jié)點；
（3）對任何一個二叉樹，若其終端節(jié)點樹為n0，度為2的節(jié)點樹為n2，則n0 = n2 + 1;
（4）具有n個節(jié)點的完全二叉樹的深度為log~2~(n + 1)向上取整。
（5）對完全二叉樹按從上到下、從左到右的順序依次編號1,2,3，…，則有以下關系：
a. 當i>1時，節(jié)點i的雙親的編號為i / 2；
b. 當2i<=n時，節(jié)點i的左孩子編號為2i，否則無左孩子；
c. 當2i+1<=n時，節(jié)點i的右孩子編號為2i+1，否則無右孩子；
d.節(jié)點i所在層次為log~2~i + 1（向下取整）。存儲結構二叉樹的存儲結構
typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;樹的存儲結構
#define MAX_TREE_SIZE 100//節(jié)點最大個數typedef struct PTNode{//節(jié)點結構TElemType data;int parent;//雙親位置域}PTNode;typedef struct{//樹結構PTNode nodes[MAX_TREE_SIZE ];int root,n;//根的位置和節(jié)點數}PTree;
#define MAX_TREE_SIZE 100//節(jié)點最大個數typedef struct CTNode{//孩子節(jié)點int child;struct CTNode *next;}*ChildPtr;typedef struct{TElemType data;ChildPtr firstChild;//孩子鏈表頭指針}CTBox;typedef struct{//樹結構CTBox nodes[MAX_TREE_SIZE ];int root,n;//根的位置和節(jié)點數}CTree;
typedef struct CSNode{//節(jié)點結構TElemType data;struct CSNode *firstChild,*nextSibling;}CSNode,*CSTree;樹、二叉樹和森林的相互轉換樹轉換為二叉樹
點擊下方，第一時間了解華為云新鮮技術~
華為云博客_大數據博客_AI博客_云計算博客_開發(fā)者中心-華為云
#華為云開發(fā)者聯盟#
