摘要：本文为大家带来树、二叉树和森林的表示及如何进行相互转换。
本文分享自华为云社区《树、二叉树和森林的表示及相互转换》，作者：1+1=王。
树的定义：树是n（n >= 0）个节点的==有限==集。当n=0是，称为空树。
树的特点：
（1）树的根没有前驱，除根外的其他节点有且仅有一个前驱；
（2）每个节点都可以有零个或多个后继。
术语：
（1）节点的度：树中一个节点的孩子个数。
（2）树的度：树中节点的最大度。
（3）分支节点：度大于0的节点。
（4）叶子结点：度为0的节点。
（5）节点的深度：从根节点开始自顶向下逐层累加。
（6）节点的高度：从叶子节点开始自底向上逐层累加。
（7）树的高度：树中节点的最大层数。
（8）路径：两个节点之间所经过的节点序列。
（9）路径长度：路径上所经过的边的个数。
（10）森林：m（m >= 0）棵互不相交的树的集合。
二叉树的定义：一种特殊的树形结构，它的特点是每个节点至多有两颗子树（即二叉树中不存在度大于2的节点），并且二叉树的子树有左右之分，不能随意颠倒。
几种特殊的二叉树：
（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（向下取整）。
顺序存储结构：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在某个数组下标为i-1的分量中。（适合完全二叉树和满二叉树）
链式存储结构：使用链表节点来存储二叉树中的每个节点。二叉链表包括数据域data、左指针域lchild和右指针域rchild三个域。
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;
孩子表示法：将没得节点的孩子节点都用单链表链接起来形成一个线性结构，此时n个节点就有n个孩子链表。
#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;
