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