本文数据结构讲解参考书目：
通过网盘分享的文件：数据结构 C语言版.pdf
链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码: ze8e
数据结构基础讲解（七）——数组和广义表专项练习-CSDN博客
个人主页：樱娆π-CSDN博客
目录
树
树的定义
树的基本术语
树的基本操作
二叉树
二叉树的定义
二叉树的基本操作
二叉树的性质
理解满二叉树，完全二叉树，非完全二叉树
二叉树的存储结构
1.顺序存储
2.链式存储
由于这节内容较多，我将分两节来讲解
树
树的定义
树(Tree)是n(n>=0)个结点的有限集，它或为空树(n= 0); 或为非空树，对千非空树T
(1)有且仅有一个称之为根的结点；
(2)除根结点以外的其余结点可分为 m(m>0）个互不相交的有限集 Ti , T2 , …，几，其中每 一个集合本身又是一棵树，并且称为根的子树(SubTree)。
树的结构定义是一个递归的定义，即在树的定义中又用到树的定义，它道出了树的固有特性
树的基本术语
(1) 结点：树中的一个独立单元。包含一个数据元素及若于指向其子树的分支.
(2)结点的度：结点拥有的子树数称为结点的度。
(3)树的度：树的度是树内各结点度的最大值。
(4) 叶子： 度为 0 的结点称为叶子或终端结点。
(5) 非终端结点：度不为 0 的结点称为非终端结点或分支结点。除根结点之外，非终端结点 也称为内部结点。
(6)双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
(7) 兄弟：同一个双亲的孩子之间互称兄弟。
(8) 祖先：从根到该结点所经分支上的所有结点。
(9) 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
(10) 层次：结点的层次从根开始定义起，根为 第一层，根的孩子为第二层。树中任一结点的 层次等千其双亲结点的层次加 1。
(11)堂兄弟：双亲在同 一层的结点互为堂兄弟
(12)树的深度：树中结点的最大层次称为树的深度或高度。
(13)有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换）， 则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的 称为最后一个孩子
(14)森林：是 m (m>0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即 为森林。由此，也可以用森林和树相互递归的定义来描述树
树的基本操作
| 基本操作 | 初始条件 | 操作结果 |
| InitTree(&T) | / | 构造空树T |
| DestroyTree (&T) | 树T存在 | 销毁树T |
| CreateTree(&T,definition) | definition 给出树 T 的定义 | 按 definition 构造树 T |
| ClearTree(&T) | 树T存在 | 将树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<=p 所指结点的度+ 1, 非空树 c 与 T 不相交 | 插入c为T中 p 指结点的第1棵子树 |
| DeleteChild(&T,p,i) | 树 T 存在， p 指向 T 中某个结点， 1<=i<=p 指结点的度 | 删除T中 p 所指结点的第1棵子树 |
| TraverseTree(T) | 树T存在 | 按某种次序对T的每个结点访问一次 |
二叉树
二叉树的定义
二叉树(Binary Tree)是n(n>0)个结点所构成的集合，它或为空树(n= 0); 或为非空树， 对于非空树T
(1) 有且仅有一个称之为根的结点；
(2)除根结点以外的其余结点分为两个互不相交的子集T1和T2, 分别称为T的左子树和右子 树，且兀和乃本身又都是二叉树。 二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：
- 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）；
- 二叉树的子树有左右之分，其次序不能任意颠倒。 二叉树的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树 的、互不相交的二叉树组成。由千这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空 树
二叉树的基本操作
| 基本操作 | 初始条件 | 操作结果 |
| InitBiTree(&T) | 构造空二叉树T | |
| DestroyBiTree(&T) | 二叉树T存在 | 销毁二叉树T |
| CreateBiTree(&T,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, 对每个结点访问一次 |
| LevelOrderTraverse(T) | 二叉树T存在 | 层序遍历T, 对每个结点访问一次 |
二叉树的性质
性质1 ： 在二叉树的 第i层上至多有2的（i-1）次方个结点（i>=1)
性质2 ：深度为K的 二叉树至多有2的k次方 -1 个结点 (k>=1)
性质3 ：对任何一棵二叉树T, 如果其终端结点数为n。度为2的结点数为n2,则n0 = n2+1
理解满二叉树，完全二叉树，非完全二叉树
满二叉树
定义: 所有节点都有两个子节点，除了最后一层节点。最后一层节点要么全都有两个子节点，要么全都没有子节点。
特点: 高度为 h 的满二叉树有 2^h - 1 个节点。
例子: 高度为 3 的满二叉树，有 7 个节点。
完全二叉树
定义: 除了最后一层节点外，其他层节点都具有两个子节点。最后一层节点可以从左到右依次排列，但不必是满的。
特点: 高度为 h 的完全二叉树，节点数量介于 2^(h-1) 和 2^h - 1 之间。
例子: 高度为 3 的完全二叉树，可以有 7 个节点，也可以有 6 个节点。
非完全二叉树
定义: 既不是满二叉树，也不是完全二叉树。
特点: 节点的排列没有规律，可能存在节点只有一个子节点，或者最后一层节点没有按顺序排列。
二叉树的存储结构
1.顺序存储
顺序存储结构使用一组地址连续的存储单元来存储数据元素，为了能够在存储结构中反 映出结点之间的逻辑关系，必须将二叉树中的结点依照一定的规律安排在这组单元中。
对于完全二叉树，只要从根起按层序存储即可，依次自上而下、自左至右存储结点元素，即 将完全二叉树上编号为i 的结点元素存储在如 上定义的一维数组中下标为i-1的分量中。
对于一般二叉树，则应将其每个结点与完全二叉树上的结点 相对照，存储在一维数组的相应分量 中。
//-----二叉树的顺序存储表示－－－－－
#define MAXTSIZE 100
typedef TElemType SqBiTree [MAXTSIZE];
SqBi Tree bt;2.链式存储
二叉树的结点由一个数据元素和分别指向其左、 右子树的两个分支构成，则表示二叉树的链表 中的结点至少包含 3 个域：数据域和左、 右指针域。
利用这两 种结点结构所得二叉树的存储结构分别称之为二叉链表和三叉链表。
//- - - - -二叉树的二叉链表存储表示－ －－－－
typedef struct BiTNode{
ll
,
TElemType data;
struct BiTNode *lchild,*rchild;
) BiTNode,*BiTree;————由于博主还是大三的在读生，时间有限，每天会不定时更新一些学习经验和一些32的项目，如果喜欢就点点关注吧，大佬们！！！！————
