🙊🙊作者主页：🔗求不脱发的博客
📔📔 精选专栏：🔗数据结构与算法
📋📋 精彩摘要：树结构是一类重要的非线性数据结构。树在计算机领域中也得到广泛应用，尤以二叉树最为常用。本章将重点介绍树的结构定义及二叉树的相关操作。
💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
📚目录
📖【数据结构与算法】第十章：树和二叉树
📝1️⃣树
✨树的定义
树是n（n>=0）个结点的有限集，或为空树，或为非空树。
对于非空树T：
- 有且仅有一个称之为根的结点。
- 除根结点外，其余结点可分为m个互不相交的有限集T1，T2，...，Tm，其中每个集合本身又是一棵树，称为根结点的子树。
编辑
树的其他表示形式：
编辑
✨树的基本术语
编辑
- 结点：数中的一个独立单元。包含一个数据元素及指向其子树的分支。如上图中的A、B、C、D等。
- 结点的度：结点拥有的子树树称为结点的度。
- 树的度：结点拥有的子树树称为结点的度。
- 叶子：度为0的结点称为叶子或终端结点。结点K、L、F、G、M、I、J都是树的叶子。
- 森林：指m颗不想交的树的集合（例如删除A后的子树个数）。
- 有序树：结点各子树从左至右有序，不能互换（左为第一）。
- 无序树：结点各子树可互换位置。
- 非终端结点：度不为0的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。
- 双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，B的双亲为A,B的孩子有E和F。
- 兄弟：同一个双亲的孩子之间互称兄弟。例如，H、I和J互为兄弟。
- 祖先：从根到该结点所经分支上的所有结点。例如，M的祖先为A、D和H。
- 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、K、L和F。
- 层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等千其双亲结点的层次加l。
- 堂兄弟：双亲在同一层的结点互为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。
✨树的抽象数据类型定义
根据树的结构定义，加上树的一组基本操作就构成了树的抽象数据类型定义：
ADT Tree{ 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R:若D为空集，则称为空树； } ADT Tree;
基本操作：
InitTree(&T)
操作结果：构造空树T。
DestroyTree (&T)
初始条件：树T存在。
操作结果：销毁树T。
CreateTree(&T,definition)
初始条件：defini巨on给出树T的定义。
操作结果：按defini巨on构造树T。
ClearTree(&T)
初始条件：树T存在。
操作结果：将树T清为空树。TreeEmpty(T)
TreeEmpty(T)
初始条件：树T存在。
操作结果：若T为空树，则返回true,否则false。
TreeDepth(T)
初始条件：树T存在。
操作结果：返回T的深度。
Root(T)
初始条件：树T存在。
操作结果：返回T的根。
Value(T,cur_e)
初始条件：树T存在，cur_e是T中某个结点。
操作结果：返回cur_e的值。
Assign(T,cur_e,value)
初始条件：树T存在，cur_e是T中某个结点。
操作结果：结点cur_e赋值为value。
Parent(T,cur_e);
初始条件：树T存在，cur_e是T中某个结点。
操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。
LeftChild(T,cur_e)
初始条件：树T存在，cur_e是T中某个结点。
操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。
RightSibling(T,cur_e)
初始条件：树T存在，cur_e是T中某个结点。
操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。
InsertChild(&T,p,i,c)
初始条件：树T存在，p指向T中某个结点，1,;;i所指结点的度+1, 非空树c与T不相交。
操作结果：插入c为T中p指结点的第l.棵子树
DeleteChild(&T,p,i)
初始条件：树T存在，p指向T中某个结点，1,;;i指结点的度。
操作结果：删除T中p所指结点的第l.棵子树
TraverseTree(T)
初始条件：树T存在。
操作结果：按某种次序对T的每个结点访问一次。
📝2️⃣二叉树
✨二叉树的定义
二叉树树是n（n>=0）个结点的有限集，或为空树，或为非空树。
基本特点：
- 结点的度小于等于2。
- 有序树（子树有序，不能颠倒）。
对于非空二叉树T：
- 有且仅有一个称之为根的结点；
- 除根结点以外的其余结点分为两个互不相交的子集T1和T2,分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：
- 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）；
- 二叉树的子树有左右之分，其次序不能任意颠倒。
编辑
✨二叉树的抽象数据类型定义
ADT BinaryTree{ 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R: } ADT BinaryTree;
基本操作P:
InitBiTree(&T)
操作结果：构造空二叉树T。
DestroyBiTree(&T)
初始条件：二叉树T存在。
操作结果：销毁二叉树T。
Crea七eBiTree(&T,definition)
初始条件；definition给出二叉树T的定义。
操作结果：按definition构造二叉树T。
ClearBiTree(&T)
初始条件：二叉树T存在。
操作结果：将二叉树T清为空树。
BiTreeEmpty(T)
初始条件：二叉树T存在。
操作结果：若T为空二叉树，则返回true,否则false。
BiTreeDepth (T)
初始条件：二叉树T存在。
操作结果：返回T的深度。
Root(T)
初始条件：二叉树T存在。
操作结果：返回T的根。
Value(T,e)
初始条件：二叉树T存在，e是T中某个结点。
操作结果：返回e的值。
Assign(T,&e,value)
初始条件：二叉树T存在，e是T中某个结点。
操作结果：结点e赋值为value。
Parent(T,e)
初始条件：二叉树T存在，e是T中某个结点。
操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。
LeftChild(T,e)
初始条件：二叉树T存在，e是T中某个结点。
操作结果：返回e的左孩子。若e无左孩子，则返回“空”。
RightChild(T,e)
初始条件：二叉树T存在，e是T中某个结点。
操作结果：返回e的右孩子。若e无右孩子，则返回“空”。
LeftSibling (T, e)
初始条件：二叉树T存在，e是T中某个结点。
操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。
RightSibling(T,e)
初始条件：二叉树T存在，e是T中某个结点。
操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。
InsertChild(&T,p,LR,c)
初始条件：二叉树T存在，p指向T中某个结点，LR为0或1,非空二叉树c与T不相交且右子树为空。
操作结果：根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树成 为c的右子树。
DeleteChild (&T, p, LR)
初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。
操作结果：根据LR为0或1,删除T中p所指结点的左或右子树。
PreOrderTraverse(T}
初始条件：二叉树T存在。
操作结果：先序遍历T,对每个结点访问一次。
InOrderTraverse(T)
初始条件：二叉树T存在。
操作结果：中序遍历T,对每个结点访问一次。
PostOrderTraverse(T}
初始条件：二叉树T存在。
操作结果：后序遍历T,对每个结点访问一次5
LevelOrderTraverse(T)
初始条件：二叉树T存在。
操作结果：层序遍历T,对每个结点访问一次。
✨二叉树的性质
- 在二叉树的第i层上最多有2^(i-1)个结点。
- 深度为k的二叉树至多有2^k-1个结点。
- 对于任何一颗二叉树，若2度的结点数1有n2个则叶子数n0必定为n2+1。（即 n0 = n2 + 1）
- 具有n个结点的完全二叉树的深度必为[log2n]＋1。
- 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。
对此有如下定义：
编辑
编辑
（满二叉树 ） （完全二叉树）
满二叉树：一棵深度为k 且有2k -1个结点的二叉树。（特点：每层都“充满”了结点）
完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应
满二叉树与完全二叉树的区别：
满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。
