小白科普丨何为树、二叉树和森林

作者：华为云开发者联盟

2023-02-03
中国香港
本文字数：1961 字
阅读完需：约 6 分钟

本文分享自华为云社区《树、二叉树和森林的表示及相互转换》，作者：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;

复制代码

树、二叉树和森林的相互转换

树转换为二叉树

规则：每个节点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟。由于根节点没有兄弟，所以对应的二叉树没有右子树。
画法：（1）在兄弟节点之间加一条线；（2）在每棵树根之间加一条线；（3）以第一棵根为轴心，顺时针旋转 45 度。

森林转换为二叉树

规则：先将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树为空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当做第一棵二叉树根的右子树，将第三棵树对应的二叉树当做第二棵二叉树根的右子树…以此类推，即可将森林转换为二叉树。
画法：（1）将森林中的每棵树转换为二叉树；（2）对每个节点，只保留它与第一个孩子的连线；（3）以根为轴心，顺时针旋转 45 度。