数据结构(五)——树与二叉树


树的基本概念

树是n个结点的有限集合,n=0时,称为空树,这是一种特殊情况。

在任意一棵非空树中应满足:

  1. 有且仅有一个特定的称为根的结点。
  2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集合T1、T2……Tm,其中每个集合本身又是一棵树,并且称为根结点的子树。

结点数为0的树就叫做“空树”

非空树的特性:

  1. 有且仅有一个根节点
  2. 没有后继的结点称为“叶子结点”(或终端结点)
  3. 有后继的结点称为“分支结点”(或非终端结点)
  4. 除了根结点外,任何一个结点都有且仅有一个前驱
  5. 每个结点可以有0个或多个后继

不难看出,树是一种递归定义的数据结构

树的一些属性

  • 结点的层次:结点从根节点出发从上往下数的深度。默认从1开始计数。
  • 结点的高度:从下往上数
  • 树的高度:总共有多少层
  • ☆结点的度:有几个孩子(分支)
  • ☆树的度:各结点的度的最大值

有序树与无序树

  • 有序树:逻辑上看,树中结点的各子树从左至右是有次序的,不能互换
  • 无序树:逻辑上看,树中结点的各子树从左至右是无次序的,可以互换

树与森林

  • 森林:森林是m棵互不相交的树的集合

当m为0,即为空森林

树的常考性质

  • 结点数=总度数+1
  • 度为m的树、m叉树的区别
  • 度为m的树第i层至多有mi-1个结点(i>=1)
  • 高度为h的m叉树至多有(mh-1)/(m-1)个结点
  • 高度为h的m叉树至少有h个结点
  • 高度为h、度为m的树至少有h+m-1个结点
  • 具有n个结点的m叉树的最小高度为 logm(n*(m-1)+1) 向上取整。

二叉树

基本概念

二叉树是n(n>=0)个结点的有限集合:

  1. 或者为空二叉树,即n=0
  2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

特点

二叉树的特点:

  1. 每个结点至多只有两棵子树
  2. 左右子树不能颠倒(二叉树是有序树)

特殊的二叉树

满二叉树

概念

一棵高度为h,且含有2h-1个结点的二叉树

特点

  1. 只有最后一层有叶子结点
  2. 不存在度为1的结点
  3. 按层序从1开始编号,结点i的左孩子为2*i;右孩子为2*i+1;结点i的父结点为i/2向下取整。

完全二叉树

概念

当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树。

满二叉树是一种特殊的完全二叉树,但是完全二叉树未必是满二叉树

特点

  1. 只有最后两层可能有叶子结点
  2. 最多只有一个度为1的结点
  3. 按层序从1开始编号,结点i的左孩子为2*i;右孩子为2*i+1;结点i的父结点为i/2向下取整。(同满二叉树的特点3)
  4. i<=(n/2向下取整)为分支结点,i>(n/2向下取整)为叶子结点
  5. 如果某一结点只有一个子结点,则必定是左结点

二叉排序树

概念

一棵空二叉树,或者是具有如下性质的二叉树

  1. 左子树上所有结点的关键字均小于根结点的关键字
  2. 右子树上所有结点的关键字均大于根结点的关键字

左子树和右子树又各是一棵二叉排序树

平衡二叉树

概念

树上任一结点的左子树和右子树的深度之差不超过1。

二叉树的常考性质

  • 设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2。则n0=n2+1(叶子结点比二分支结点多一个)
  • 设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2。假设树中结点总度数n,则:
    1. n=n0+n1+n2
    2. n=n1+2*n2+1(树的结点数=总度数+1)
  • 二叉树第i层至多有2i-1个结点(i>=1)
  • m叉树第i层至多有mi-1个结点(i>=1)
  • 高度为h的二叉树至多有2h-1个结点(满二叉树)
  • 高度为h的m叉树至多有(mh-1)/(m-1)个结点

完全二叉树的常考性质

  • 具有n个(n>0)结点的完全二叉树的高度h为 向上取整log2(n+1) 或者 (向下取整log2n)+1
  • 对于完全二叉树,可以由结点数n推出度为0、1、2的结点个数为n0、n1和n2
    • 若完全二叉树有2k个结点,则必有n0=k、n1=1和n2=k-1
    • 若完全二叉树有2k-1个结点,则必有n0=k、n1=0和n2=k-1

二叉树存储结构

二叉树的顺序存储

定义与初始化工作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define MaxSize 100

typedef ElemType int;

struct TreeNode{
ElemType value; //结点中的数据元素
bool isEmpty; //结点是否为空
}

/*定义一个长度为MaxSize的数组t,按照从上
至下、从左至右的顺序依次存储完全二叉树中
的各个结点*/
TreeNode t[MaxSize];

//初始化二叉树
void init(TreeNode t[]){
for(int i=0;i<MaxSize;i++){
t[i].isEmpty=true;
}
}

对于一棵完全二叉树,我们可以通过2*i和2*i+1来寻找其对应的左结点和右结点;同样,对于一棵普通二叉树,我们可以将其元素按完全二叉树编号,也通过2*i和2*i+1来寻找其对应的左结点和右结点,用isEmpty属性来判断是否存在,不过这样的空间利用率可能会很差劲。

故一般对于树的存储,我们一般不会采用顺序存储

二叉树的链式存储

定义

每个二叉树结点都有左孩子指针域和右孩子指针域。

1
2
3
4
5
6
7
8
9
10
11
#include<stdlib.h>

struct ElemType{
int value;
}

//二叉树的结点(链式存储)
typedef struct{
ElemType data; //数据域
struct BiTNode *lchild,*rchild; //左、右孩子指针
}BiTNode,*BiTree;

n个结点的二叉链表共有n+1个空链域

二叉树的遍历算法

什么是遍历

遍历:按照某种次序把所有结点都访问一遍。

二叉树的经典遍历

三种经典遍历

二叉树的递归特性:

  1. 要么是个空二叉树
  2. 要么就是由“根节点+左子树+右子树”组成的二叉树

三种遍历:

  1. 先序遍历:根->左->右(NLR)
  2. 中序遍历:左->根->右(LNR)
  3. 后序遍历:左->右->根(LRN)

三种遍历的手算练习:

经典遍历的代码实现

我们以先序遍历为例:

先序遍历(PreOrder)的操作过程如下:

  1. 若二叉树为空,则什么也不做
  2. 若二叉树非空:
    1. 访问根结点
    2. 先序遍历左子树
    3. 先序遍历右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdlib.h>

typedef struct{
int value;
}ElemType;

//二叉树的结点(链式存储)
typedef struct{
ElemType data; //数据域
struct BiTNode *lchild,*rchild; //左、右孩子指针
}BiTNode,*BiTree;

void PreOrder(BiTree T){
if(T!=NULL){
visit(T); //访问根节点
PreOrder(T->lchild); //递归访问左子树
PreOrder(T->rchild); //递归访问右子树
}
}

空间复杂度:O(h)

对于中序、后序遍历,只需要调整先后次序即可:

1
2
3
visit(T);  //访问根节点
PreOrder(T->lchild); //递归访问左子树
PreOrder(T->rchild); //递归访问右子树

二叉树的层序遍历

层序遍历

算法思想:

  1. 初始化一个辅助队列
  2. 根结点入队
  3. 若队列非空,则队列结点出队,访问该结点,并将其左、右(如果有的话)孩子插入队尾
  4. 重复上一步,知道队列为空

层序遍历的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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); //右孩子入队
}
}

通过遍历序列唯一确定二叉树

若只给出一棵二叉树的 前/中/后 序遍历序列中的一种,不能唯一确定一棵二叉树。
我们可以通过下面三种情况来唯一确定二叉树:

  1. 前序+中序遍历序列
  2. 后序+中序遍历序列
  3. 层序+中序遍历序列

前序+中序遍历序列

前序遍历序列:根结点+左子树的前遍历序列+右子树的前遍历序列

中序遍历序列:左子树的前遍历序列+根结点+右子树的前遍历序列

由如上结构逻辑我们可以知道,前序遍历序列的第一个元素即为根元素,然后我们在中序遍历序列中可找到该元素,该元素左边即是根元素的左子树,右边则是根元素的右子树。

我们就进行了第一批分化,然后我们再对未确定的序列进行同样的逻辑分析即可。

后序+中序遍历序列

结构不同,原理相同。

层序+中序遍历序列

结构不同,原理相同。

总结图

线索二叉树

中序线索二叉树

在我们上面介绍的二叉树中,易知找前驱、找后继是很不方便的;遍历操作必须从根开始。为了避免这种繁琐,于是就有了线索二叉树。

以中序遍历为例,我们可以在叶子结点里面做手脚,将其左孩子指针指向其前驱;将其右孩子指针指向其后继(制定前驱后继的规则即通过中序遍历的规则来制定)。

指针前驱、后继的指针称为“线索”

线索二叉树的存储结构

为了明确区分我们的指针到底是指向了孩子,还是指向了“线索”,我们需要更改线索二叉树的存储结构:

1
2
3
4
5
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; //左右线索标志
}ThreadNode,*ThreadTree;

我们规定,当tag等于0时,表示指针指向孩子;当tag等于1时,表示指针指向“线索”。

其他线索二叉树

先序线索二叉树、后序线索二叉树,也是一样的道理。

线索化的具体实现

中序线索化

下面我们来将一个初步建成的二叉树(tag值都为0)来进行线索化,即对应指针将成为“线索”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//全局变量,指向当前访问结点的前驱
ThreadNode *pre=NULL;

//中序线索化二叉树T
void CreateInThread(ThreadTree T){
pre=NULL; //pre初始为NULL;
if(T!=NULL){ //非空二叉树才能线索化
InThread(T); //中序线索化二叉树
if(pre->rchild==NULL){ //尾端处理
pre->rtag=1; //处理遍历的最后一个结点
}
}
}
//中序遍历二叉树,一遍遍历一遍线索化
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->rtag=1;
}
pre=q;
}

得到一棵中序线索二叉树。

先序线索化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//全局变量,指向当前访问结点的前驱
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->lchild);
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;
}

得到一棵先序线索二叉树。

后序线索化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//全局变量,指向当前访问结点的前驱
ThreadNode *pre=NULL;

//后序线索化二叉树T
void CreatePostThread(ThreadTree T){
pre=NULL; //pre初始为NULL;
if(T!=NULL){ //非空二叉树才能线索化
PostThread(T); //后序线索化二叉树
if(pre->rchild==NULL){ //尾端处理
pre->rtag=1; //处理遍历的最后一个结点
}
}
}
//后序遍历二叉树,一遍遍历一遍线索化
void PostThread(ThreadTree T){
if(T!=NULL){ PreThread(T->lchild);
PreThread(T->rchild);
visit(T); //访问根节点
}
}

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;
}

得到一棵后序线索二叉树。

通过线索二叉树找到相应的前驱和后继

中序线索二叉树找中序后继

  1. 若p->rtag==1,则next=p->rchild
  2. 若p->rtag==0,则next就是p结点右子树的最左下的结点。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//找到以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);
}

中序线索二叉树找中序前驱

  1. 若p->ltag==pre=p->lchild
  2. 若p->ltag==0,则pre就是p结点左子树的最右下的结点。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//找到以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; //rtag==1直接返回前驱线索
}
//对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
void Inorder(ThreadNode *T){
for(ThreadNode *p=Lastnode(T);p!=null;p=Prenode(p))
visit(p);
}

先序线索二叉树找先序后继

在先序线索二叉树中找到指定结点*p的先序后继next:

  1. 若p->rtag==1,则next=p->rchild
  2. 若p->rtag==0:
    1. 假设根节点p有左孩子,则先序后继为左孩子
    2. 假设根节点p没有左孩子,则先序后继为右孩子

先序线索二叉树找先序前驱

在先序线索二叉树中找到指定结点*p的先序前驱pre:

  1. 若p->ltag==1,则pre=p->lchild
  2. 若p->ltag==0:

先序遍历中,左右子树中的结点只可能是根的后继,不可能是前驱





商业转载 请联系作者获得授权,非商业转载 请标明出处,谢谢