一、二叉树的定义
二叉树（T）是一个有穷的结点集合，这个集合 可以为空，若不为空，则它是由 根节点 和称为其 左子树 \(T_{L}\) 和 右子树 \(T_{R}\) 的两个不相交的二叉树组成。
二叉树具体五种基本形态：
二叉树的子树有左右顺序之分；
几种特殊的二叉树：
二、二叉树的性质
- 一个二叉树第 i 层的最大结点数为 \(2^{i-1}, i ≥ 1\)
- 深度为 K 的二叉树有最大结点数总数为：\(2^{k}-1, k ≥ 1\)
- 对任何非空二叉树 T，若 \(n_{0}\) 表示叶结点的个数、\(n_{2}\) 是度为 2 的非叶结点个数，那么两者关系满足 \(n_{0} = n_{2} + 1\)
\[边的总数 = 总结点树 -1 = n_{0} + n_{1} + n_{2} -1 = 0*n_{0} + 1*n_{1} + 2*n_{2} ==> n_{1} = n_{2} + 1
\]
三、二叉树的抽象数据类型定义
- 类型名称：二叉树
- 数据对象集：一个有穷的结点集合，若不为空，则由 根节点 和 其左、右二叉子树 组成；
- 操作集：BT ∈ BinTree，Item ∈ ElementType
int IsEmpty(BinTree BT); // 判别BT是否为空
void PreOrderTraversal(BiinTree BT); // 先序遍历，根、左子树、右子树
void InOrderTraversal(BinTree BT); // 中序遍历，左子树、根、右子树
void PostOrderTraversal(BinTree BT); // 后序遍历，左子树、右子树、根
void LevelOrderTraversal(BinTree BT); // 层次遍历，从上到下，从左到右
BinTree CreatBinTree(); // 创建一个二叉树
四、二叉树的存储结构
4.1、顺序存储结构
完全二叉树：按从上到下，从左到右顺序存储 n 个结点的完全二叉树的结点父子关系：
- 非根结点（序号 i > 1）的父节点的序号是 [i/2]
- 结点（序号为 i）的左孩子结点的序号是 2i（若 2i > n，则没有左孩子）
- 结点（序号为 i）的左孩子结点的序号是 2i+1（若 2i+1 > n，则没有左孩子）
一般二叉树也可以采用这种结构，手动补全为完全二叉树，但是会造成空间浪费。
4.2、链表存储结构
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode
{
ElementType Data;
BinTree Left;
BinTree Right;
};
五、二叉树的遍历
5.1、先序遍历
遍历过程为：
- 访问 根结点
- 先序 遍历其 左子树
- 先序 遍历其 右子树
void PreOrderTraversal(BinTree BT)
{
if(BT)
{
printf("%d\t",BT->Data);
PreOrderTraversal(BT->Left);
PreOrderTraversal(BT->Right);
}
}
先序遍历结果：A B D F E C G H I
我们还可以使用 堆栈 的方式来实现非递归遍历。
- 遇到一个结点，就把它 压栈，并访问这个结点，然后 先序 遍历它的 左子树
- 当左子树遍历结束后，从栈顶弹出这个结点
- 然后按其右指针再去 先序 遍历该结点的右子树
void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreateStack(MaxSize); // 创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) // 一直向左并将沿途结点压入堆栈
{
Push(S,T); // 遇到结点压入栈中
printf("%d\t",T->Data); // 访问结点
T = T->Leftl; // 访问左边的子节点
}
if(!IsEmpty(S)) // 如果堆栈未空
{
T = Pop(S); // 结点弹出堆栈
T = T->Right; // 转向右子树
}
}
}
5.2、中序遍历
遍历过程为：
- 中序 遍历其 左子树
- 访问 根节点
- 中序 遍历其 右子树
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d\t",BT->Data);
InOrderTraversal(BT->Right);
}
}
中序遍历结果：D B E F A G H C I
我们还可以使用 堆栈 的方式来实现非递归遍历。
- 遇到一个结点，就把它 压栈，并 中序 遍历它的 左子树
- 当左子树遍历结束后，从栈顶弹出这个结点并访问它
- 然后按其右指针再去 中序 遍历该结点的右子树
void InOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreateStack(MaxSize); // 创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) // 一直向左并将沿途结点压入堆栈
{
Push(S,T); // 遇到结点压入栈中
T = T->Leftl; // 访问左边的子节点
}
if(!IsEmpty(S)) // 如果堆栈未空
{
T = Pop(S); // 结点弹出堆栈
printf("%d\t",T->Data); // 访问结点
T = T->Right; // 转向右子树
}
}
}
5.3、后序遍历
遍历过程：
- 后序 遍历其 左子树
- 后序 遍历其 右子树
- 访问 根节点
void PostOrderTraversal(BinTree BT)
{
if(BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d\t",BT->Data);
}
}
后序遍历结果：D E F B H G I C A
先序、中序 和 后序 遍历过程：遍历过程中经过结点的路径一样，只是 访问各结点的时机不同；
5.4、层序遍历
我们可以使用队列实现层序遍历，即遍历从根节点开始，首先将根节点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队。
层序遍历的基本流程如下：
- 先根节点入队
- 然后从队列中取出一个元素
- 访问该元素所指结点
- 若该元素所值结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队
void LevelOrderTraversal(BinTree BT)
{
Queue Q;
BinTree T;
if(!BT) // 若是空树则直接返回
{
return;
}
Q = CreatQueue(MaxSize); // 创建并初始化队列Q
AddQ(Q,BT); // 将根节点添加到队列
while(!IsEmptyQ(Q))
{
T = DeleteQ(Q); // 取出一个结点
printf("%d\t",T->Data); // 访问取出队列的结点
if(T->Left) // 如果取出的结点的左结点非空
{
AddQ(Q,T->Left); // 将其左节点添加到队列
}
if(T->Right) // 如果取出的结点的右结点非空
{
AddQ(Q,T->Right); // 将其右节点添加到队列
}
}
}
六、树的同构
给定两棵树 T1 和 T2。如果 T1 可以通过若干次 左右孩子互换 就变成 T2，则 我们成两个树是“同构”的。
6.1、二叉树的表示
这里我们采用 结构数组（静态链表） 来表示二叉树。
#define MaxTree 10
#define Elementtype char
#define Tree int
#define Null -1
struct TreeNode
{
Elementtype Element;
Tree Left;
Tree Right;
}T1[MaxTree],T2[MaxTree];
6.2、建立二叉树
Tree BuildTree(struct TreeNode T[])
{
Tree cl,cr,Root;
char N,i;
char check[MaxTree];
printf("请输入树的结点个数:\n");
scanf("%d",&N);
getchar();
if(N)
{
for(i = 0; i < N; i++)
{
check[i] = 0;
}
for(i = 0; i < N; i++)
{
printf("请输入第%d个结点信息：\n",(i+1));
scanf("%c %c %c",&T[i].Element,&cl,&cr); // 输入结点信息
getchar();
if(cl != '-') // 如果输入结点的左子树不为空
{
T[i].Left = cl-'0'; // 输入左子树
check[T[i].Left] = 1; // 标记位设置为1
}
else
{
T[i].Left = Null; // 如果输入结点的左子树为空
}
if(cr != '-') // 如果输入结点的右子树不为空
{
T[i].Right = cr-'0'; // 输入右子树
check[T[i].Right] = 1; // 标记位设置为1
}
else
{
T[i].Right = Null; // 如果输入结点的右子树为空
}
// printf("%c %d %d\n",T[i].Element,T[i].Left,T[i].Right);
}
for(i = 0; i < N; i++)
{
if(!check[i])
{
break;
}
}
Root = i; // 获取根节点对应的索引
// printf("%d\n",i);
}
return Root;
}
6.3、同构判别
int Isomorphic(Tree R1,Tree R2)
{
// both empty
if((R1 == Null) && (R2 = Null))
{
return 1;
}
// one of them is empty
if(((R1 == Null) && (R2 != Null)) || (R1 != Null) && (R2 == Null))
{
return 0;
}
// roots are different
if(T1[R1].Element != T2[R2].Element)
{
return 0;
}
// both have no left subtree
if((T1[R1].Left == Null) && (T2[R2].Left == Null))
{
return Isomorphic(T1[R1].Right,T2[R2].Right);
}
// no need to swap the left and the right
if(((T1[R1].Left != Null) && (T2[R2].Left != Null)) && ((T1[T1[R1].Left].Element) == (T2[T2[R2].Left].Element)))
{
return (Isomorphic(T1[R1].Left,T2[R2].Left) && Isomorphic(T1[R1].Right,T2[R2].Right));
}
// need to swap the left and the right
else
{
return (Isomorphic(T1[R1].Left,T2[R2].Right) && Isomorphic(T1[R1].Right,T2[R2].Left));
}
}
6.4、测试程序
先在一行中给该树的结点数，第 i 对应标号为第 i 个结点，给出该结点中存储的字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置给出 “-”。
#include <stdio.h>
int main()
{
Tree R1,R2;
R1 = BuildTree(T1);
R2 = BuildTree(T2);
if(Isomorphic(R1,R2)){
printf("Yes\n");
}
else
{
printf("No\n");
}
}
七、遍历的应用
【1】、遍历二叉树，输出二叉树的叶子结点
void PreOrderPrintLeaves(BinTree BT)
{
if(BT)
{
if(!BT->Left && !BT->Right)
{
printf("%d\t",BT->Data);
}
PreOrderPrintLeaves(BT->Left);
PreOrderPrintLeaves(BT->RIght);
}
}
【2】、求二叉树的高度
int PostOrderGerHeight(BinTree BT)
{
int HL,HR,MaxH;
if(BT)
{
HL = PostOrderGerHeight(BT->Left); // 求左子树的深度
HR = PostOrderGerHeight(BT->Right); // 求右子树的深度
MaxH = (HL > HR) ? HL : HR; // 取左右子树较大的深度
return (MaxH + 1); // 返回树的深度
}
else
{
return 0;
}
}
【3】、由两种遍历序列确定二叉树
①、先序和中序遍历序列来确定一颗二叉树
- 根据 先序 遍历序列的 第一个 结点确定 根节点
- 根据 根节点 在 中序 遍历序列中分割左右两个子序列
- 对 左子树 和 右子树 分别 递归 使用相同的方法继续求解
②、中序和后序遍历序列来确定一颗二叉树
- 根据 后序 遍历序列的 最后一个 结点确定 根节点
- 根据 根节点 在 中序 遍历序列中分割左右两个子序列
- 对 左子树 和 右子树 分别 递归 使用相同的方法继续求解
必须有 中序遍历 才行。