1.特殊的二叉树
(1)满二叉树
一棵树高度为h,且含有2^h-1个结点的二叉树。
特点:只有最后一层有叶子结点;
不存在度为1的结点;
按层序从1开始编号,结点i的左孩子为20i,右孩子为2i+1;结点i的父节点为[i/2](向下取整)。
(2)完全二叉树
当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树。
特点:只有最后两层可能有叶子结点;
最多只有一个度为1的结点;
按层序从1开始编号,结点i的左孩子为20i,右孩子为2i+1;结点i的父节点为[i/2](向下取整);
i<=[n/2](向下取整)为分支结点,i>[n/2](向下取整)为叶子结点。
(3)二叉排序树
一个二叉树或者是空二叉树,或者是具有如下性质的二叉树:
左子树上所有结点的关键字均小于根结点的关键字;
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又是一颗二叉排序树。
(4)平衡二叉树
树上任一结点的左子树和右子树的深度之差不超过1。
平衡二叉树能有更高的搜索效率。
2.二叉树的性质
(1)设非空二叉树中度为0、1和2的结点个数分别为n0、n1、n2,则n0=n1+1(叶子结点比二分支结点多一个)
(2)二叉树第i层至多有2^(i-1)个结点(i>=1)
m叉树第i层至多有m^(i-1)个结点(i>=1)
(3)高度为h的二叉树至多有2^h-1个结点(满二叉树)
高度为h的m叉树至多有(m^h-1)/(m-1)个结点
等比数列的求和公式:a(1-qn)/(1-q)
3.完全二叉树的性质
(1)具有n个(n>0)结点的完全二叉树的高度h为[log2(n+1)](向上取整)或[log2n]+1(向下取整)
(2)对于完全二叉树,可以由结点数n推出度为0、1和2的结点个数为n0、n1和n2。
完全二叉树最多只有一个度为1的结点,即n1=0或1
n0=n2+1->n0+n2一定是奇数
若完全二叉树有2k(偶数)个结点,则必有n1=1,n0=k,n2=k-1;
若完全二叉树有2k-1(奇数)个结点,则必有n1=0,n0=k,n2=k-1.
4.二叉树的存储结构
(1)顺序存储
#define MaxSize 100
struct TreeNode {
ElemType value; //结点中的数据元素
bool isEmpty; //结点是否为空
};
TreeNode t[MaxSize];
//初始化时所有结点标记为空
for(int i=0;i<MaxSize;i++){
t[i].isEmpty = true;
}
定义一个长度为MaxSize的数组t,按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。
(2)链式存储
struct ElemType{
int value;
};
//二叉树的结点(链式存储)
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lchild,*rchild; //左、右孩子指针
}BiTNode,*BiTree;
//定义一颗空树
BiTree root = NULL;
//插入根节点
root = (BiTree)malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;
//插入新结点
BiTNode * p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p; //作为根结点的左孩子
可以根据实际需要定义三叉链表,方便找父节点。
typedef struct BitNode{
ElemType data; //数据域
struct BiTNode *lchild,*rchild; //左、右孩子指针
struct BiTNode *parent; //父节点指针
}BiTNode,*BiTree;
5.二叉树的先中后序遍历
(1)先序遍历
//先序遍历
void PreOrder(BiTree T){
if(T!=NULL){
visit(T); //访问根结点
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}
(2)中序遍历
//中序遍历
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild); //递归遍历左子树
Visit(T); //访问根结点
InOrder(T->rchild); //递归遍历右子树
}
}
(3)后序遍历
//后序遍历
void PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
Visit(T); //访问根结点
}
}
6.求树的深度(应用)
int treeDepth(BiTree T){
if(T == NULL){
return 0;
}
else{
int l = treeDepth(T->lchild);
int r = treeDepth(T->rcjild);
//树的深度 = Max(左子树深度,右子树深度)+1
return l>r ? l+1 : r+1;
}
}
7.二叉树的层次遍历
算法思想:
①初始化一个辅助队列
②根结点入队
③若队列非空,则队头结点出队,访问该结点,并将左、右孩子插入队尾(如果有的话)
④重复③直至队列为空
//二叉树的结点(链式存储)
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//链式队列结点
typedef struct LinkNode{
BiTNode * data; //保存结点指针
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear; //队头队尾
}LinkQueue;
//层序遍历
void LevelOrder(BiTree T){
LinkQueue Q;
InitQueue(Q); //初始化辅助队列
BiTree p;
EnQueue(Q,T); //将根结点入队
while(!IsEmpty(Q)){ //队列不空则循环
DeQueue(Q,p); //队头结点出队
visit(p); //访问出队结点
if(p->lchild!=NULL)
EnQueue(Q,p->lchild); //左孩子入队
if(p->rchild!=NULL)
EnQueue(Q,p->rchild); //右孩子入队
}
}
8.由遍历序列构造二叉树
只给出一颗二叉树的前/中/后/层序遍历序列中的一种,不能唯一确定一颗二叉树。
若要构造二叉树必须得知中序遍历序列。
9.线索二叉树
(1)线索二叉树结构
//线索二叉树结点
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; //左、右线索标志
}ThreadNode,*ThreadTree;
对应tag位为0时,表示指针指向其孩子;
对应tag位为1时,表示指针是“线索”。
将n+1个空链域连上前驱、后继
(2)土方法找中序前驱
//辅助全局变量,用于查找结点p的前驱
BiTNode *p; //p指向目标结点
BiTNode * pre=NULL; //指向当前访问结点的前驱
BiTNode * final=NULL; //用于记录最终结果
//中序遍历
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild); //递归遍历左子树
visit(T); //访问根结点
InOrder(T->rchild); //递归遍历右子树
}
}
//访问结点q
void visit(BiTNode * q){
if(q==p) //当前访问结点刚好是结点p
final = pre; //找到p的前驱
else
pre = q; //pre指向当前访问的结点
}
(3)中序线索化
//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre = NULL;
//中序线索化二叉树T
void CreateInThread(ThreadTree T){
pre = NULL; //pre初始为NULL
if(T!=NULL){ //非空二叉树才能线索化
InThead(T); //中序线索化二叉树
if(pre->child==NULL)
pre->rtag=1; //处理遍历的最后一个结点
}
}
//线索二叉树结点
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; //左、右线索标志
}ThreadNode,*ThreadTree;
//中序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T){
if(T!=NULL){
InThread(T->lchild); //中序遍历左子树
visit(T); //访问根节点
InThread(T->rchild); //中序遍历右子树
}
}
void visit(ThreadNode *q){
if(q->lchild==NULL){ //左子树为空,建立前驱线索
q->lchild=pre;
q->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=q; //建立前驱结点的后继线索
pre=q;
}
}
(4)先序线索化
先序线索化有转圈问题,需要特别注意。
//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;
//先序线索化二叉树T
void CreatePreThread(ThreadTree T){
pre=NULL; //pre初始为NULL
if(T!=NULL){ //非空二叉树才能线索化
PreThread(T); //先序线索化二叉树
if(pre->rchild==NULL)
pre->rtag=1; //处理遍历的最后一个结点
}
}
//先序遍历二叉树,一边遍历一边线索化
void PreThread(ThreadTree T){
if(T!=NULL){
visit(T); //先处理根结点
if(T->ltag==0) //lchild不是前驱线索
PreThread(T->rchild);
PreThread(T->rchild);
}
}
void visit(ThreadNode *q){
if(q->lchild==NULL){ //左子树为空,建立前驱线索
q->lchild=pre;
q->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=q; //建立前驱结点的后续线索
pre->rtag=1;
}
pre=q;
}
(5)后序线索化
//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;
//后序线索化二叉树T
void CreatePostThread(ThradTree T){
pre=NULL; //pre初始化为NULL
if(T!=NULL){
PostThread(T); //后序线索化二叉树
if(pre->rchild==NULL)
pre->rtag=1; //处理遍历的最后一个结点
}
}
//后序遍历二叉树,一边遍历一边线索化
void PostThread(ThreadTree T){
if(T!=NULL){
PostThread(T->lchild); //后序遍历左子树
PostThread(T->rchild); //后序遍历右子树
visit(T); //访问根结点
}
}
void visit(ThreadNode *q){
if(q->lchild==NULL){ //左子树为空,建立前驱线索
q->lchild=pre;
q->ltag=1;
}
pre=q;
}
(6)中序线索二叉树找中序后继
在中序二叉树中找到指定结点*p的中序后继next
①若p->rtag==1,则next=p->rchild
②若p->rtag==0
next=p的右子树中最左下结点
//找到以P为根的字树中,第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
//循环找到最左下结点(不一定是叶节点)
while(p->ltag==0)
p=p->lchild;
return p;
}
//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
//右子树中最左下结点
if(p->rtag==0)
return Firstnode(p->rchild);
else
return p->rchild; //rtag==1直接返回后继线索
}
//对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
void Inorder(ThreadNode *T){
for(ThreadNode *p=Firstnode(T);P!=NULL;p=Nextnode(p))
visit(p);
}
(7)中序线索二叉树找中序前驱
在中序线索二叉树中找到指定结点*p的中序前驱pre
①若p->ltag==1,则pre = p->lchild
②若p->ltag==0
pre = p的左子树中最右下结点
//找到以p为根的子树中,最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
//循环找到最右下结点(不一定是叶结点)
while(p->rtag==0)
p=p->rchild;
return p;
}
//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
//左子树中最右下结点
if(p->ltag==0)
return Lastnode(p->lchild);
else return p->lchild; //ltag==1直接返回前驱线索
}
//对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){
for(ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p))
visit(p);
}
(7)先序线索二叉树
①找先序后继
若p有左孩子,则先序后继为左孩子,若p没有左孩子,则先序后继为右孩子。
②找先序前驱
先序遍历中,左右子树中的结点只可能是根的后继,不可能是前驱。
改用三叉链表可以找到父节点:
如果能找到p的父节点,且p是左孩子,p的父节点即为其前驱;
如果能找到p的父节点,且p是右孩子,其左兄弟为空,p的父结点即为其前驱;
如果能找到p的父节点,且p是右孩子,其左兄弟非空,p的前驱为左兄弟子树中最后一个被先序遍历的结点;
如果p是根结点,则p没有先序前驱。
(8)后序线索二叉树
①找后序前驱
若p有右孩子,则后序前驱为右孩子;
若p没有右孩子,则后序前驱为左孩子。
②找后序后继
后序遍历中,左右子树中的结点只可能是根的前驱,不可能是根的后继。
改用三叉链表可以找到父节点:
如果能找到p的父节点,且p是右孩子,p的父节点即为其后继;
如果能找到p的父节点,且p是左孩子,其右兄弟为空,p的父节点即为其后继;
如果能找到p的父节点,且p是左孩子,其右兄弟非空,p的后继为右兄弟子树中第一个被后序遍历的结点;
如果p是根结点,则p没有后序后继。