一、概念
1.1 树的定义
树是 n （n ≥ 0）个结点的有限集。n=0时称为空树。
在任意一棵非空树中：（1）有且仅有一个特定的成为根（Root）的结点；（2）当 n > 1 时，其余结点可分为m（m > 0）个互不相交的有限集 T1、 T2、…… Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree），如下图所示：
子树如下图所示：
1.2 树的其他特性
- 度（Degree）：结点拥有的子树数成为结点的度。
- 度为0的结点成为叶子结点（Leaf）或终端结点
- 度不为0的结点成为非终端结点或分枝结点。
- 层次（Level）：指从根开始定义起，结点所在的楼层。（按照根结点为1开始依次算起）
- 深度（Depth）：树中结点的最大层次成为树的深度或高度。
- 子结点、双亲结点：结点的子树的根成为该结点的孩子（Child），相应地，该结点成为孩子的双亲结点（Parent）
1.3 二叉树的定义
二叉树（Binary Tree） 是 n （n ≥ 0）个结点的有限集合，该集合或为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
因为二叉树最多只能由左结点和右结点，一个普遍的二叉树如图
1.4 二叉树的基本特点
1.4.1 特点
- 每个结点最多有两棵子树，所以二叉树中不存在度大于2度结点。
- 左子树和右子树顺序不可颠倒。
- 即使树中某结点只有一棵子树，也要区分他是左子树还是右子树。
1.4.2 基本形态
- 空二叉树
- 只有一个根结点
- 根结点只有左子树
- 根结点只有右子树
- 根结点既有左子树也有右子树
1.5 特殊的二叉树
1.5.1 斜树
顾名思义，所有的结点都只有左子树或右子树。所有结点只有左子树的叫左斜树，只有右子树的成为右斜树，两者统称为斜树。
1.5.2 满二叉树
在一棵树中，如果所有的分支结点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树称为满二叉树。
1.5.3 完全二叉树
对一颗具有n个结点的二叉树按层序编号，如果编号为i（1≤ i ≤ n）的结点与同样深度的满二叉树中编号为i 的结点在二叉树中的位置完全相同，这棵二叉树称为完全二叉树。
如下图所示，完全二叉树并不要求所有子结点全部填满，只需要子树树按顺序排列。
换句通俗的话说，哥哥一家没生满二胎，弟弟一家不允许要孩子……🐶，否则就不是完全二叉树。
如下图中，11节点丢失的情况下，不可以称为完全二叉树
二、二叉树的存储结构
2.1 顺序存储结构
通常用数组来存储二叉树，先看看存储完全二叉树的情况
可以看到，二叉树中的元素按照顺序依次放入开辟好的数组内存空间里。
但是，凡事都有但是，在某些极端情况下，某一棵树，缺胳膊少腿儿，导致空间大大浪费，比如下图：
这棵树只有4个有效的结点，但是却不得不开辟从A～M一共13个结点的内存空间，这种情况的树，使用数组结构来存储，对内存空间是一种浪费。
2.2 二叉链表
鉴于上文中数组结构无法更高效的表述二叉树，引入了链表的结构进行表述。
由于二叉树结构最多有两个孩子，所以引入的链表结点，结构分别为数据域、左孩子指针、右孩子指针
结点结构如下
| 左孩子 | 数据 | 右孩子 |
|---|---|---|
| lChild | data | rChild |
用代码来表述可以是这样的
struct BiTreeNode{ |
把上文中较特殊的二叉树，用这样的结点表述的二叉树结构如下：
三、二叉树的遍历
二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历方法，主要有四种：
3.1 前序遍历
遍历的规则是若二叉树为空，空操作返回；否则先访问根结点，然后前序遍历左子树，再前序遍历右子树
如图示：
3.2 中序遍历
遍历的规则是若二叉树为空，空操作返回；否则从根结点开始（但此时并不遍历根结点），先前序遍历左子树，先遍历访问根结点，再前序遍历右子树。
如图示：
3.3 后序遍历
遍历的规则是若二叉树为空，空操作返回；否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。
如图示
3.4 层序遍历
遍历的规则是若二叉树为空，空操作返回；否则从树的第一层——也就是根结点开始访问，从上往下，在同一层时从左至右对结点逐个访问。
访问顺序如图示：
三、顺序存储下的实现
3.1 顺序存储的实现
3.1.1 二叉树基本操作
初始化环境
创建结点结构
typedef struct {
int level; //结点层
int order; //本层的序号(按照满二叉树给定序号规则)
}Position;以及其他辅助条件
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int CElemType; /* 树结点的数据类型，目前暂定为整型 */
typedef CElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点 */
CElemType Nil = 0; /*设整型以0为空 或者以 INT_MAX(65535)*/初始化一个二叉树T
Status InitBiTree(SqBiTree T){
for (int i = 0; i < MAX_TREE_SIZE; i++) {
//将二叉树初始化值置空
T[i] = Nil;
}
return OK;
}创建二叉树（放入数据）
Status CreateBiTree(SqBiTree T){
int i = 0;
//printf("按层序输入结点的值(整型),0表示空结点, 输入999结束.结点数<=%d\n",MAX_TREE_SIZE);
/*
1 -->1
2 3 -->2
4 5 6 7 -->3
8 9 10 -->4
1 2 3 4 5 6 7 8 9 10 Nil Nil Nil
*/
while (i < 10) {
T[i] = i+1;
printf("%d ",T[i]);
//结点不为空,且无双亲结点
if (i != 0 && T[(i+1)/2-1] == Nil && T[i] != Nil) {
printf("出现无双亲的非根结点%d\n",T[i]);
exit(ERROR);
}
i++;
}
//将空赋值给T的后面的结点
while (i < MAX_TREE_SIZE) {
T[i] = Nil;
i++;
}
return OK;
}清空二叉树
清空一棵二叉树，与构造一棵二傻树一样，只需将每个结点值置空即可。
可以直接定义一个新函数，将两个函数对等。
判断二叉树是否为空
只需判断根结点是否为空
Status BiTreeEmpty(SqBiTree T){
//根结点为空,则二叉树为空
return T[0] == Nil;
}获取二叉树的深度
计算深度，需要看从当前结点，到根结点经历的路径条数
int BiTreeDepth(SqBiTree T){
int j = -1;
int i;
//找到最后一个结点
//MAX_TREE_SIZE -> 100 -> 10 目的找到最后一个结点10的位置
for (i = MAX_TREE_SIZE-1 ; i>=0; i--) {
if (T[i] != Nil)
break;
}
do {
j++;
} while ( powl(2, j) <= i); //计算2的次幂
return j;
}
3.1.2 结点操作
获取二叉树根结点的值
只需计算数组T 首结点的值即可
Status Root(SqBiTree T,CElemType *e){
if (BiTreeEmpty(T)) {
return ERROR;
}
*e = T[0];
return OK;
}返回结点位置为e 的值
CElemType Value(SqBiTree T,Position e){
/*
Position.level -> 结点层.表示第几层;
Position.order -> 本层的序号(按照满二叉树给定序号规则)
*/
//pow(2,e.level-1) 找到层序
printf("%d\n",(int)pow(2,e.level-1));
//e.order
printf("%d\n",e.order);
//4+2-2;
return T[(int)pow(2, e.level-1)+e.order-2];
}修改结点位置e 的值
Status Assign(SqBiTree T,Position e,CElemType value){
//找到当前e在数组中的具体位置索引
int i = (int)powl(2, e.level-1)+e.order -2;
//叶子结点的双亲为空
if (value != Nil && T[(i+1)/2-1] == Nil) {
return ERROR;
}
//给双亲赋空值但是有叶子结点
if (value == Nil && (T[i*2+1] != Nil || T[i*2+2] != Nil)) {
return ERROR;
}
T[i] = value;
return OK;
}获取结点位置e 的双亲
CElemType Parent(SqBiTree T, CElemType e){
//空树
if (T[0] == Nil) {
return Nil;
}
for (int i = 1 ; i < MAX_TREE_SIZE; i++) {
//找到e
if (T[i] == e) {
return T[(i+1)/2 - 1];
}
}
//没有找到
return Nil;
}获取某结点的左孩子
步骤为当前结点的
CElemType LeftChild(SqBiTree T,CElemType e){
//空树
if (T[0] == Nil) {
return Nil;
}
for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
//找到e
if (T[i] == e) {
return T[i*2+1];
}
}
//没有找到
return Nil;
}获取某结点的右孩子
CElemType RightChild(SqBiTree T,CElemType e){
//空树
if (T[0] == Nil) {
return Nil;
}
for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
//找到e
if (T[i] == e) {
return T[i*2+2];
}
}
//没有找到
return Nil;
}获取某结点的左兄弟
CElemType LeftSibling(SqBiTree T,CElemType e)
{
/* 空树 */
if(T[0]==Nil)
return Nil;
for(int i=1;i<=MAX_TREE_SIZE-1;i++)
/* 找到e且其序号为偶数(是右孩子) */
if(T[i]==e&&i%2==0)
return T[i-1];
return Nil; /* 没找到e */
}获取某结点的右兄弟
CElemType RightSibling(SqBiTree T,CElemType e)
{
/* 空树 */
if(T[0]==Nil)
return Nil;
for(int i=1;i<=MAX_TREE_SIZE-1;i++)
/* 找到e且其序号为奇数(是左孩子) */
if(T[i]==e&&i%2==1)
return T[i+1];
return Nil; /* 没找到e */
}
3.1.3 遍历二叉树
前序遍历
void PreTraverse(SqBiTree T,int e){
//打印结点数据
visit(T[e]);
//先序遍历左子树
if (T[2 * e + 1] != Nil) {
PreTraverse(T, 2*e+1);
}
//最后先序遍历右子树
if (T[2 * e + 2] != Nil) {
PreTraverse(T, 2*e+2);
}
}
Status PreOrderTraverse(SqBiTree T){
//树不为空
if (!BiTreeEmpty(T)) {
PreTraverse(T, 0);
}
printf("\n");
return OK;
}中序遍历
void InTraverse(SqBiTree T, int e){
/* 左子树不空 */
if (T[2*e+1] != Nil)
InTraverse(T, 2*e+1);
visit(T[e]);
/* 右子树不空 */
if (T[2*e+2] != Nil)
InTraverse(T, 2*e+2);
}
Status InOrderTraverse(SqBiTree T){
/* 树不空 */
if (!BiTreeEmpty(T)) {
InTraverse(T, 0);
}
printf("\n");
return OK;
}后序遍历
void PostTraverse(SqBiTree T,int e)
{ /* 左子树不空 */
if(T[2*e+1]!=Nil)
PostTraverse(T,2*e+1);
/* 右子树不空 */
if(T[2*e+2]!=Nil)
PostTraverse(T,2*e+2);
visit(T[e]);
}
Status PostOrderTraverse(SqBiTree T)
{
if(!BiTreeEmpty(T)) /* 树不空 */
PostTraverse(T,0);
printf("\n");
return OK;
}层序遍历
void LevelOrderTraverse(SqBiTree T){
int i = MAX_TREE_SIZE-1;
//找到最后一个非空结点的序号
while (T[i] == Nil) i--;
//从根结点起,按层序遍历二叉树
for (int j = 0; j <= i; j++)
//只遍历非空结点
if (T[j] != Nil)
visit(T[j]);
printf("\n");
}
3.2 链式存储的实现
3.2.1 二叉树的基本操作
数据类型及结点结构如下：
typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符为空 */
typedef struct BiTNode /* 结点结构 */
{
CElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;初始化二叉树
只需对当前二叉树赋值为空即可。
Status InitBiTree(BiTree *T)
{
*T=NULL;
return OK;
}创建二叉树
void CreateBiTree(BiTree *T){
CElemType ch;
//获取字符
ch = str[indexs++];
//判断当前字符是否为'#'
if (ch == '#') {
*T = NULL;
}else
{
//创建新的结点
*T = (BiTree)malloc(sizeof(BiTNode));
//是否创建成功
if (!*T) {
exit(OVERFLOW);
}
/* 生成根结点 */
(*T)->data = ch;
/* 构造左子树 */
CreateBiTree(&(*T)->lchild);
/* 构造右子树 */
CreateBiTree(&(*T)->rchild);
}
}清空二叉树
这里的逻辑与数组存储树一样的，逻辑等于初始化二叉树，用新函数来等同于它。
销毁二叉树
void DestroyBiTree(BiTree *T)
{
if(*T)
{
/* 有左孩子 */
if((*T)->lchild)
DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
/* 有右孩子 */
if((*T)->rchild)
DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
free(*T); /* 释放根结点 */
*T=NULL; /* 空指针赋0 */
}
}判断二叉树是否为空
Status BiTreeEmpty(BiTree T)
{
if(T)
return FALSE;
else
return TRUE;
}获取二叉树的深度
int BiTreeDepth(BiTree T){
int i,j;
if(!T)
return 0;
//计算左孩子的深度
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
//计算右孩子的深度
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
//比较i和j
return i>j?i+1:j+1;
}
3.2.2 结点操作
获取二叉树根结点的值
CElemType Root(BiTree T){
if (BiTreeEmpty(T))
return Nil;
return T->data;
}获取指针p 指向的结点的值
CElemType Value(BiTree p){
return p->data;
}给p 指向的结点赋值
void Assign(BiTree p,CElemType value)
{
p->data=value;
}
3.2.3 遍历操作
前序遍历
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}中序遍历
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}后序遍历
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}
