二叉树
二叉树的概念
二叉树是n(n≥0)个结点的有限集
或者是空集(n= O)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成
- 二叉树结构最简单、规律性最强
- 所有树都能转为唯一对应的二叉树，具有一般性，解决了树的存储结构及其运算中存在的复杂性
特点：
- 每个结点最多含有两个孩子（二叉树中不存在度大于2的结点）
- 子树有左右之分，次序不能颠倒
- 二叉树可以是空集合，根可以有空的左子树或空的右子树
二叉树不是树的特殊情况，是两个概念 ：
二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分
（二叉树的每个结点位置或者说次序都是固定的，可以是空，但不可以说没位置）
树当结点只有一个孩子时，就无需区分是左还是右的次序
（树的结点位置相对于其他结点来说的，没有别的结点时就无所谓左右）
例：具有三个结点的二叉树可能有几种不同形态？普通树呢？
-
二叉树具有五种形态：2*2+1
-
树有两种形态：1+1
二叉树的五种基本形态：
- 空二叉树
- 根和空的左右子树
- 根和左子树
- 根和右子树
- 根和左右子树
二叉树的性质
-
在二叉树的第i层最多有2^(i-1)个结点；最少有1个结点
-
深度为k的二叉树最多有2^k-1个结点；最少有k个结点
-
对于任何一个二叉树T，如果其叶子树为n0，度为2的结点数为n2，则n0=n2+1
总边数为总结点数-1（根结点往上没有边）
例：
特殊形式二叉树
顺序存储方式下可以复原
满二叉树
深度为k的二叉树仅有2^k-1个结点
编号规则：从上到下，从左至右
-
每层都满
-
叶子结点在最底层
完全二叉树
深度为k具有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号1~n结点位置一一对应
例：
在满二叉树中，从最后一个结点开始，连续去掉任意个结点即是一个完全二叉树
因此，满二叉树一定是完全二叉树
特点:
- 叶子结点只可能分布在层次最大的两层上
- 对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1
- 具有n个结点的完全二叉树深度为⌊log2 n⌋+1
- 对任一结点i，双亲结点编号是⌊i/2⌋，左孩子结点编号是2i，右孩子结点编号是2i+1
二叉树的抽象数据类型定义
ADT Binary Tree{
数据对象D：具有相同特性的数据元素集合
数据关系R：若D=∅，则R=∅ ;
若D≠∅，则R={H};H是如下二元关系:
root唯一 //关于根的说明
Dj∩Dk= ∅ //关于子树不相交的说明
...... //关于数据元素的说明
...... //关于左子树和右子树的说明
基本操作P：
CreateBiTree(&T,definition)
初始条件:definition给出二叉树T的定义
操作结果:按definition构造二叉树T
PreOrderTraverse(T)
初始条件:二叉树T存在
结果:先序遍历T，对每个结点访问一次
lnOrderTraverse(T)
初始条件:二叉树T存在
操作结果:中序遍历T，对每个结点访问一次
PostOrderTraverse(T)
初始条件:二叉树T存在
操作结果:后序遍历T，对每个结点访问一次
}ADT Binary Tree
二叉树的应用：
- 数据压缩：将数据文件转化为二进制形式
- 求解表达式的值
二叉树的顺序存储结构
按满二叉树的结点编号作为数组下标；适合于存储满二叉树和完全二叉树
缺点：深度为k且仅有k个结点的单支树需要长度为2^k-1的一维数组
定义
#define MAXSIZE 100
typedef int SqBiTree[MAXSIZE];
SqBiTree bt;
二叉树的链式存储结构
二叉链表
lchild+data+rchild
在n个结点的二叉链表中，有n+1个空指针域（2n-（n-1））
定义
typedef struct Binode{
int data;
struct Binode *lchild,*rchild;
}BiNode,*BiTree;
三叉链表
lchild+data+parent+rchild
定义
typedef struct Tritnode{
int data;
struct Tritnode *lchild,*parent,*rchild;
}TritNode,*TriTree;
标签：左子,结点,struct,右子,二叉树,编号 From： https://www.cnblogs.com/yuanyu610/p/17091158.html