第 7章 二叉树
二叉树的基本概念
二叉树的存储结构
二叉树的基本运算
二叉树其它运算的实现
穿线二叉树
树、森林和二叉树的转换
二叉树的遍历
7.1 二叉树的基本概念二叉树的定义为,二叉树 是一个由结点构成的有限集合,这个集合或者为空,或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。当二叉树的结点集合为空时,
称为 空二叉树 。
a
b
ed
c
h
f g
二叉树有以下 五种基本形态,
(a) 空二叉树 (b) 根和空的左、右子树 (c) 根和非空左子树、空右子树
(d) 根和空左子树、非空右子树 (e) 根和非空的左、右子树树型结构中使用的术语如父母(双亲或前件)、
子女(后件)、祖先、子孙、兄弟和路径等在二叉树中仍然可以沿用,但值得注意的是,二叉树并非一般树型结构的特殊形式,它们为两种不同的数据结构。
二叉树与一般树型结构的主要 区别 在于:
( 1)二叉树中每个非空结点最多只有两个子女,而一般的树型结构中每个非空结点可以有 0到多个子女;
( 2)二叉树中结点的子树要区分左子树和右子树,
即使在结点只有一棵子树的情况下也要明确指出是左子树还是右子树。
二叉树具有以下重要性质:
性质 1 一棵非空二叉树的第 i层上至多有 2i-1个结点
( i≥1)。
证明:当 i=1时,只有根结点,此时 21-1=20=1,显然上述性质成立;又由于在二叉树中每个结点最多只能具有两个子女,因而第 i层上结点的最大个数是第
i-1层上结点的最大个数的两倍。于是第 2层上结点的最大个数为 2,第 3层上结点的最大个数为 4,……,
则第 i层上结点的最大个数即为 2i-1。
性质 2 深度为 h的二叉树至多有 2h-1个结点( h>1)。
根据性质 1,深度为 h的二叉树最多具有的结点的个数为 20+21+22+… +2h-1=2h-1。
性质 3 对于任何一棵二叉树 T,如果其终端结点数为
n0,度为 2的结点数为 n2,则 n0=n2+1。
证明:假设二叉树中总的结点个数为 n,度为 1的结点个数为 n1,则有:
n=n0+n1+n2
又由于在二叉树中除根结点外,其它结点均通过一条树枝且仅通过一条树枝与其父母结点相连,即除根结点外,其它结点与树中的树枝存在一一对应的关系;
而二叉树中树枝的总条数为 n1+2*n2,因而二叉树总结点的个数为:
n=n1+2*n2+1
于是有:
n0+n1+n2=n1+2*n2+1
显然 n0=n2+1成立。
如果一棵二叉树中所有终端结点均位于同一层次,
而其它非终端结点的度数均为 2,则称此二叉树为 满二叉树 。在满二叉树中,若其深度为 h,则其所包含的结点个数必为 2h-1。下图中的二叉树即为一棵深度为 3的满二叉树,其结点的个数为 23-1=7。
1
4
2
5
3
6 7
如果一棵二叉树扣除其最大层次那层后即成为一棵满二叉树,且层次最大那层的所有结点均向左靠齐,
则称该二叉树为 完全二叉树 。通俗地说,完全二叉树中只有最下面的两层结点的度数可以小于 2,且最下面一层的结点都集中在该层最左边的若干位置上。下图所示的二叉树即为一棵深度为 3的完全二叉树。
若对深度相同的满二叉树和完全二叉树中的所有结点按自上而下、同一层次按自左向右的顺序依次编号,则两者对应位置上的结点编号应该相同。
1
4
2
5
3
6
对于完全二叉树,具有以下性质:
性质 4 对于具有 n个结点的完全二叉树,如果按照从上到下、同一层次上的结点按从左到右的顺序对二叉树中的所有结点从 1开始顺序编号,则对于序号为 i的结点,有:
( 1)如果 i>1,则序号为 i的结点其双亲结点的序号为?i/2? (?i/2?表示对 i/2的值取整);如果
i=1,则结点 i为根结点,没有双亲;
( 2)如果 2i>n,则结点 i无左子女(此时结点 i为终端结点);否则其左子女为结点 2i;
( 3)如果 2i+1>n,则结点 i无右子女;否则其右子女为结点 2i+1。
7.2 二叉树的基本运算
ADT bintree {
数据对象 D,D是具有相同性质的数据元素构成的集合。
数据关系 R:如果 D为空或 D仅含一个元素,则 R为空;
否则 D中存在一个特殊的结点 root,称之为根结点,
其无前驱;其它结点被分成互不相交的两个集合,
分别构成 root的左子树 l和右子树 r;若 l和 r非空,
则它们的根结点 lroot和 rroot分别称为整棵二叉树根结点 root的后继结点;左子树 l和右子树 r也是二叉树,因而它们中数据元素间的关系也同样满足 R的定义。
二叉树的基本操作如下:
(1)createbitree(t)
(2)destroybitree(t)
(3)root(t)
(4)leftchild(t)
(5)rightchild(t)
(6)locate(t,x)
(7)parent(t,x)
(8)isempty(t)
(9)depth(t)
(10)numofnode(t)
(11)addchild(t,x,t1,b)
(12)deletechild(t,x,b)
(13)setnull(t)
(14)isequal(t1,t2)
(15)preorder(t)
(16)inorder(t)
(17)postorder(t)
(18)transform(t1,t2)
} ADT bintree.
7.3 二叉树的存储结构二叉树常用的存储结构有两种:顺序存储结构和链式存储结构。
7.3.1 顺序存储结构顺序存储结构是使用一组连续的空间存储二叉树的数据元素和数据元素之间的关系。因此必须将二叉树中所有的结点排成一个适当的线性序列,在这个线性序列中应采用有效的方式体现结点之间的逻辑关系。
1,完全二叉树的顺序存储对于一棵具有 n个结点的完全二叉树,我们可以按从上到下、同一层次按从左到右的顺序依次将结点存入一个一维数组中。根据上述性质 4,无须附加任何其它信息就能根据每个结点的下标找到它的子女结点和双亲结点。
a
b
d e
c
f
a b c d e f
0 1 2 3 4 5 6 7
(a) 完全二叉树 (b)完全二叉树的顺序存储
2 一般二叉树的顺序存储由于二叉树中每个结点最多只有两个子女,于是存储一个结点时,除了包含结点本身的属性值外,
另外增加两个域,分别用来指向该结点的两个子女在数组中的下标。
a
b
d
c
gf
e
(a) 一棵二叉树 (b) 二叉树的顺序存储
1 3 -1 -1 5 -1 -1
a b c d e f g
2 4 -1 -1 6 -1 -1
0 1 2 3 4 5 6
lchild
data
rchild
root=0 n=7
一般二叉树顺序存储数据结构的定义如下:
#define MAXSIZE 20
typedef char datatype; /*结点值的类型 */
typedef struct {
datatype data;
int lchild,rchild;
} node; /*二叉树结点的类型 */
node tree[MAXSIZE];
int n; /*树中实际所含结点的个数 */
int root; /*存放根结点的下标 */
带双亲指示的 二叉树顺序存储数据结构的定义如下:
#define MAXSIZE 20
typedef char datatype; /*结点值的类型 */
typedef struct {
datatype data;
int lchild,rchild;
int parent; /*存放双亲结点的下标 */
} node; /*二叉树结点的类型 */
node tree[MAXSIZE];
int n; /*树中实际所含结点的个数 */
int root; /*存放根结点的下标 */
7.3.2 链式存储结构二叉树的链式存储方式下每个结点也包含三个域,
分别记录该结点的属性值及左、右子树的位置。与顺序存储结构不同的是,其左、右子树的位置不是通过数组的下标,而是通过指针方式体现,如下图所示:
lchild data rchild
指针域 属性值 指针域
a
b
d
c
gf
e
a
gf
ed
b c
root
(a)一棵二叉树
(b) 二叉树的链式存储链式存储方式下二叉树结点数据结构的定义如下:
typedef char datatype; /*结点属性值的类型 */
typedef struct node{ /*二叉树结点的类型 */
datatype data;
struct node *lchild,*rchild;
} bintnode;
typedef bintnode *bintree;
bintree root;
链式存储方式下带双亲指针的二叉树结点数据结构的定义如下:
typedef char datatype; /*结点属性值的类型 */
typedef struct node{ /*二叉树结点的类型 */
datatype data;
struct node *lchild,*rchild;
struct node *parent;/*指向双亲的指针 */
} bintnode;
typedef bintnode *bintree;
bintree root; /*指向二叉树根结点的指针 */
7.4 二叉树的遍历
7.4.1 二叉树遍历的定义所谓 二叉树的遍历,是指按一定的顺序对二叉树中的每个结点均访问一次,且仅访问一次。按照根结点访问位置的不同,通常把二叉树的遍历分为三种,前序遍历,中序遍历 和 后序遍历 。
( 1)二叉树的前序遍历首先访问根结点;
然后按照前序遍历的顺序访问根结点的左子树;
再按照前序遍历的顺序访问根结点的右子树。
( 2)二叉树的中序遍历首先按照中序遍历的顺序访问根结点的左子树;
然后访问根结点;
最后按照中序遍历的顺序访问根结点的右子树。
( 3)二叉树的后序遍历首先按照后序遍历的顺序访问根结点的左子树;
然后按照后序遍历的顺序访问根结点的右子树;
最后访问根结点。
a
b
d f
e g
c 前序遍历,abdefgc
中序遍历,debgfac
后序遍历,edgfbca
7.4.2 二叉树遍历的递归实现由于二叉树的遍历是递归定义的,因此采用递归方式实现二叉树遍历的算法十分方便,只要按照各种遍历规定的次序,访问根结点时就输出根结点的值,
访问左子树和右子树时进行递归调用即可。
1,前序遍历二叉树的递归算法
void preorder(bintree t)
{ if (t) { printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
2,中序遍历二叉树的递归算法
void inorder(bintree t)
{ if (t) {
inorder(t->lchild);
printf(“%c”,t->data);
inorder(t->rchild); }
}
3,后序遍历二叉树的递归算法
void postorder(bintree t)
{ if (t) {
postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data); }
}
4,二叉树的创建算法利用二叉树前序遍历的结果可以非常方便地生成给定的二叉树,具体做法是:将第一个输入的结点作为二叉树的根结点,后继输入的结点序列是二叉树左子树前序遍历的结果,由它们生成二叉树的左子树;再接下来输入的结点序列为二叉树右子树前序遍历的结果,应该由它们生成二叉树的右子树;而由二叉树左子树前序遍历的结果生成二叉树的左子树和由二叉树右子树前序遍历的结果生成二叉树的右子树的过程均与由整棵二叉树的前序遍历结果生成该二叉树的过程完全相同,只是所处理的对象范围不同,于是完全可以使用递归方式加以实现。
void createbintree(bintree *t)
{ char ch;
if ((ch=getchar())==' ') *t=NULL;
else {
*t=(bintnode *)malloc(sizeof(bintnode));
/*生成二叉树的根结点 */
(*t)->data=ch;
createbintree(&(*t)->lchild);
/*递归实现左子树的建立 */
createbintree(&(*t)->rchild);
/*递归实现右子树的建立 */
}
}
7.4.3 二叉树遍历的非递归实现在第 5章,已经介绍了由递归程序转换成非递归程序的两种方法:简单递归程序的转换和复杂递归程序的转换;二叉树的遍历问题应该属于后者,即在采用非递归方式实现二叉树遍历时,必须使用一个堆栈记录回溯点,以便将来进行回溯。以下为一个顺序栈的定义及其部分操作的实现。
typedef struct stack /*栈结构定义 */
{ bintree data[100];
int tag[100]; /*为栈中每个元素设置的标记,用于后序遍历 */
int top; /*栈顶指针 */
} seqstack;
void push(seqstack *s,bintree t) /*进栈 */
{ s->data[++s->top]=t;
}
bintree pop(seqstack *s) /*出栈 */
{
if (s->top!=-1)
{ s->top--;
return(s->data[s->top+1]); }
else
return NULL;
}
1,二叉树前序遍历的非递归实现前序遍历一棵非空树 t 时,访问完 t的根结点后,
就应该进入 t的左子树,但此时必须将 t保存起来,
以便访问完其左子树后,进入其右子树的访问,即在 t处必须设置一个回溯点;对 t的左子树和右子树的遍历也是如此。仔细观察不难发现,这些回溯点应该使用栈来进行管理。在整个二叉树前序遍历的过程中,程序要做的工作始终分成两个部分:当前正在处理的树(子树)和保存在栈中待处理的部分,
只有这两部分的工作均完成后,程序方能结束。
void preorder1(bintree t) /*非递归实现二叉树的前序遍历 */
{ seqstack s;
s.top=-1;
while ((t) || (s.top!=-1))
/*当前处理的子树不为空或栈不为空则循环 */
{ while (t)
{ printf("%c ",t->data); s.top++;
s.data[s.top]=t; t=t->lchild;
}
if (s.top>-1)
{ t=pop(&s);
t=t->rchild;
}
}
}
2,二叉树中序遍历的非递归实现中序遍历一棵非空树 t时,首先应该进入 t的左子树访问,此时由于 t的根结点及右子树尚未访问,
因此必须将 t保存起来,放入栈中,以便访问完其左子树后,从栈中取出 t,进行其根结点及右子树的访问;对 t的左子树和右子树的遍历也是如此。在整个二叉树中序遍历的过程中,程序要做的工作始终分成两个部分:当前正在处理的树(子树)和保存在栈中待处理的部分,只有这两部分的工作均完成后,
程序方能结束。
void inorder1(bintree t)
{ seqstack s;
s.top=-1;
while((t!=NULL) || (s.top!=-1))
{ while (t)
{ push(&s,t); t=t->lchild; }
if (s.top!=-1)
{ t=pop(&s);
printf("%c ",t->data);
t=t->rchild;
}
}
}
3,二叉树后序遍历的非递归实现后序遍历一棵非空树 t时,首先应该进入 t的左子树访问,此时由于 t的右子树及根结点尚未访问,因此必须将 t保存在栈中,以便访问完其左子树后,从栈中取出 t,进行其右子树及根结点的访问。值得注意的是,
当一个元素位于栈顶即将被处理时,其左子树的访问一定已经完成,如果其右子树尚未遍历,接下来应该进入其右子树的访问,而此时该栈顶元素是不能出栈的,因为其根结点还未被访问;只有等到其右子树也访问完成后,该栈顶元素才能出栈,并输出其根结点的值。因此一个元素位于栈顶时,必须设法识别其右子树是否已被访问。
解决的方法为:使用 seqstack类型中的数组 tag,
用于标识栈中每个元素的状态:
每个元素刚进栈时,其 tag值初始化为 0;
当某一元素位于栈顶即将被处理时:
( 1)如果其 tag值为 0,意味着其右子树尚未访问,
于是将其右子树作为当前处理的对象,此时该栈顶元素仍应该保留在栈中,并将其 tag的值改为 1;
( 2)如果其 tag值为 1,意味着其右子树已被访问,
接下来应该访问其根结点,并将其出栈。
在整个二叉树后序遍历的过程中,程序要做的工作始终分成两个部分:当前正在处理的树(子树)和保存在栈中待处理的部分。只有这两部分的工作均完成后,程序方能结束。
void postorder1(bintree t)
{ seqstack s;
s.top=-1;
while ((t)||(s.top!=-1))
{ while (t)
{ s.top++;
s.data[s.top]=t;
s.tag[s.top]=0;
t=t->lchild;
}
while ((s.top>-1)&& (s.tag[s.top]==1))
{ t=s.data[s.top];
printf("%c ",t->data);
s.top--;
}
if (s.top>-1)
{ t=s.data[s.top];
s.tag[s.top]=1;
t=t->rchild;
}
else t=NULL;
}
}
7,5 二叉树其它运算的实现由于二叉树本身的定义是递归的,因此关于二叉树的许多问题或运算采用递归方式实现非常地简单和自然。
1、二叉树的查找 locate(t,x)
bintree locate(bintree t,datatype x)
{ bintree p;
if (t==NULL) return NULL;
else if (t->data==x) return t;
else
{ p=locate(t->lchild,x);
if (p) return p;
else return locate(t->rchild,x);
}
}
2 统计二叉树中结点的个数 numofnode(t)
int numofnode(bintree t)
{ if (t==NULL) return 0;
else
return(numofnode(t->lchild)+numofnode(t->rchild)+1);
}
3,判断二叉树是否等价 isequal(t1,t2)
int isequal(bintree t1,bintree t2)
{ int t;
t=0;
if (t1==NULL && t2==NULL) t=1;
else if (t1!=NULL && t2!=NULL)
if (t1->data==t2->data)
if (isequal(t1->lchild,t2->lchild))
t=isequal(t1->rchild,t2->rchild);
return(t);
}
4,求二叉树的高 (深 )度 depth(t)
int depth(bintree t)
{ int h,lh,rh;
if (t==NULL) h=0;
else {
lh=depth(t->lchild);
rh=depth(t->rchild);
if (lh>=rh) h=lh+1;
else h=rh+1;
}
return h;
}
7.6 穿线二叉树
7.6.1 穿线二叉树的定义所谓 穿线二叉树,即在一般二叉树的基础上,
对每个结点进行考察。若其左子树非空,则其左指针不变,仍指向左子女;若其左子树为空,则让其左指针指向某种遍历顺序下该结点的前驱;若其右子树非空,则其右指针不变,仍指向右子女;若其右子树为空,则让其右指针指向某种遍历顺序下该结点的后继。如果规定遍历顺序为前序,则称为 前序穿线二叉树 ;如果规定遍历顺序为中序,则称为中序穿线二叉树 ;如果规定遍历顺序为后序,则称为 后序穿线二叉树 。本小节主要介绍中序穿线二叉树。
在穿线二叉树的每个结点中,增加两个标志位:
ltag和 rtag,其含义为:
ltag=0 表示结点的左指针指向其左子女;
ltag=1 表示结点的左指针指向其中序遍历的前驱;
rtag=0 表示结点的右指针指向其右子女;
rtag=1 表示结点的右指针指向其中序遍历的后继 。
每个结点的结构如下图所示:
ltag lchild data rchild rtag
a
b
c d
f
e
g
a
b
c d
f
e
g
(a)一棵二叉树 (b)中序穿线二叉树
(b)图中 实线表示指针,虚线表示线索。
7.6.2中序穿线二叉树的基本运算
ADT binthrtree {
数据对象 D:具有相同性质的数据元素构成的有限集合;
数据关系 R:如果 D为空或 D仅含一个元素,则 R为空;否则
D中存在一个特殊的结点 root,称之为根结点,其无前驱;其它结点被分成互不相交的两个集合,分别构成
root的左子树 l和右子树 r;若 l和 r非空,则它们的根结点 lroot和 rroot分别称为整棵二叉树根结点 root的后继结点;左子树 l和右子树 r也是二叉树,因而它们中数据元素之间也同样满足上述关系。对于二叉树中的任何结点,如其左子树非空,则其 lchild指向其左子树,否则指向其中序遍历顺序下的前驱结点;如其右子树非空,则其 rchild指向其右子树,否则指向其中序遍历顺序下的后继结点。
基本操作集为,
(1) createthrtree(p)
(2) inthreading(p)
(3) locate(p,x)
(4) infirstnode(p)
(5) inlastnode(p)
(6) inprednode(p)
(7) insuccnode(p)
(8) preinsert(p,x,y)
(9) succinsert(p,x,y)
(10) delete(p,x)
(11) inthrtree(p)
(12) prethrtree(p)
(13) postthrtree(p)
} ADT binthrtree
7.6.3 中序穿线二叉树的存储结构及其实现
1,中序穿线二叉树在链接方式下的数据类型定义
typedef char datatype;
typedef struct node
{
datatype data;
int ltag,rtag; /*左、右标志位 */
struct node *lchild,*rchild;
}binthrnode;
typedef binthrnode *binthrtree;
2,创建中序穿线二叉树 createthrtree(p)
创建一棵中序穿线二叉树的办法之一为:首先建立一棵一般的二叉树,然后对其进行中序线索化。实现二叉树中序线索化可以借助于二叉树中序遍历的算法,只需将二叉树中序遍历算法中对当前结点的输出操作改为对该结点进行穿线;为了实现对当前结点的穿线,必须设置一个指针 pre,用于记录当前结点中序遍历的前驱结点。
binthrtree pre=NULL; /*初始化前驱结点 */
void createbintree(binthrtree *t)
{ char ch;
if ((ch=getchar())==) *t=NULL;
else { *t=(binthrnode *)malloc(sizeof(binthrnode));
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}
void inthreading(binthrtree *p)
{ /*对二叉树进行中序线索化 */
if (*p)
{ inthreading(&((*p)->lchild));
(*p)->ltag=((*p)->lchild)?0:1;
(*p)->rtag=((*p)->rchild)?0:1;
if (pre)
{ if(pre->rtag==1) pre->rchild=*p;
if((*p)->ltag==1) (*p)->lchild=pre;
}
pre=*p;
inthreading(&((*p)->rchild));
}
}
void createthrtree(binthrtree *p)
{ createbintree(p);
inthreading(p); }
3,中序遍历中序穿线二叉树 inthrtree(p)
基本思想:首先找到中序遍历下的第一个结点(从根结点出发,沿着左指针不断往左下走,直到左指针为空,到达,最左下,的结点即可),访问它后,然后不断寻找结点在中序下的后继结点并输出,直至所有的结点均被输出为止。
binthrtree insuccnode(binthrtree p)
{ /*寻找结点 p在中序遍历下的后继结点 */
binthrtree q;
if (p->rtag==1) return p->rchild;
else { q=p->rchild;
while (q->ltag==0) q=q->lchild;
return q;
}
}
void inthrtree(binthrtree p)
{ /*中序遍历中序穿线二叉树 p*/
if (p)
{ /*求二叉树 p中序遍历下的第一个结点 */
while (p->ltag==0)
p=p->lchild;
do
{ printf(“%c,,p->data);
p=insuccnode(p); }
while (p);
}
}
7.7 树、森林和二叉树的转换
7.7.1 树、森林到二叉树的转换将树或森林转换成其对应二叉树的方法为:
(1) 在所有兄弟结点之间添加一条连线,如果是森林,则在其所有树的树根之间同样也添加一条连线;
(2) 对于树、森林中的每个结点,除保留其到第一个子女的连线外,撤消其到其它子女的连线;
(3) 将以上得到的树按照顺时针方向旋转 45度。
a
b c d
e f g
a
b c d
e f g
a
b c d
e f g
a
b c
d
e f
g
(a) (b)
(c) (d)
树到二叉树的转换
a
b c d
e f
g
h i
a
b
c
de
f
g
h
i
a
b c d
e f
g
h i
a
b c d
e f
g
h i
(a) (b)
(c) (d)
森林到二叉树的转换
7.7.2 二叉树到树、森林的转换二叉树到树、森林也有一种对应的转换关系,
其过程恰巧为上述过程的逆过程,具体方法如下:
(1) 首先将二叉树按照逆时针方向旋转 45度;
(2) 若某结点是其双亲的左子女,则把该结点的右子女,右子女的右子女,…… 都与该结点的双亲用线连起来;
(3) 最后去掉原二叉树中所有双亲到其右子女的连线。
a
b
d e
c
f g
h i
a
b
d
e
c
f
g
h
i
a
b
d
e
c
f
g
h
i
a
b
d
e
c
f
g
h
i
(a) (b)
(c) (d)
二叉树到树、森林的转换
二叉树的基本概念
二叉树的存储结构
二叉树的基本运算
二叉树其它运算的实现
穿线二叉树
树、森林和二叉树的转换
二叉树的遍历
7.1 二叉树的基本概念二叉树的定义为,二叉树 是一个由结点构成的有限集合,这个集合或者为空,或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。当二叉树的结点集合为空时,
称为 空二叉树 。
a
b
ed
c
h
f g
二叉树有以下 五种基本形态,
(a) 空二叉树 (b) 根和空的左、右子树 (c) 根和非空左子树、空右子树
(d) 根和空左子树、非空右子树 (e) 根和非空的左、右子树树型结构中使用的术语如父母(双亲或前件)、
子女(后件)、祖先、子孙、兄弟和路径等在二叉树中仍然可以沿用,但值得注意的是,二叉树并非一般树型结构的特殊形式,它们为两种不同的数据结构。
二叉树与一般树型结构的主要 区别 在于:
( 1)二叉树中每个非空结点最多只有两个子女,而一般的树型结构中每个非空结点可以有 0到多个子女;
( 2)二叉树中结点的子树要区分左子树和右子树,
即使在结点只有一棵子树的情况下也要明确指出是左子树还是右子树。
二叉树具有以下重要性质:
性质 1 一棵非空二叉树的第 i层上至多有 2i-1个结点
( i≥1)。
证明:当 i=1时,只有根结点,此时 21-1=20=1,显然上述性质成立;又由于在二叉树中每个结点最多只能具有两个子女,因而第 i层上结点的最大个数是第
i-1层上结点的最大个数的两倍。于是第 2层上结点的最大个数为 2,第 3层上结点的最大个数为 4,……,
则第 i层上结点的最大个数即为 2i-1。
性质 2 深度为 h的二叉树至多有 2h-1个结点( h>1)。
根据性质 1,深度为 h的二叉树最多具有的结点的个数为 20+21+22+… +2h-1=2h-1。
性质 3 对于任何一棵二叉树 T,如果其终端结点数为
n0,度为 2的结点数为 n2,则 n0=n2+1。
证明:假设二叉树中总的结点个数为 n,度为 1的结点个数为 n1,则有:
n=n0+n1+n2
又由于在二叉树中除根结点外,其它结点均通过一条树枝且仅通过一条树枝与其父母结点相连,即除根结点外,其它结点与树中的树枝存在一一对应的关系;
而二叉树中树枝的总条数为 n1+2*n2,因而二叉树总结点的个数为:
n=n1+2*n2+1
于是有:
n0+n1+n2=n1+2*n2+1
显然 n0=n2+1成立。
如果一棵二叉树中所有终端结点均位于同一层次,
而其它非终端结点的度数均为 2,则称此二叉树为 满二叉树 。在满二叉树中,若其深度为 h,则其所包含的结点个数必为 2h-1。下图中的二叉树即为一棵深度为 3的满二叉树,其结点的个数为 23-1=7。
1
4
2
5
3
6 7
如果一棵二叉树扣除其最大层次那层后即成为一棵满二叉树,且层次最大那层的所有结点均向左靠齐,
则称该二叉树为 完全二叉树 。通俗地说,完全二叉树中只有最下面的两层结点的度数可以小于 2,且最下面一层的结点都集中在该层最左边的若干位置上。下图所示的二叉树即为一棵深度为 3的完全二叉树。
若对深度相同的满二叉树和完全二叉树中的所有结点按自上而下、同一层次按自左向右的顺序依次编号,则两者对应位置上的结点编号应该相同。
1
4
2
5
3
6
对于完全二叉树,具有以下性质:
性质 4 对于具有 n个结点的完全二叉树,如果按照从上到下、同一层次上的结点按从左到右的顺序对二叉树中的所有结点从 1开始顺序编号,则对于序号为 i的结点,有:
( 1)如果 i>1,则序号为 i的结点其双亲结点的序号为?i/2? (?i/2?表示对 i/2的值取整);如果
i=1,则结点 i为根结点,没有双亲;
( 2)如果 2i>n,则结点 i无左子女(此时结点 i为终端结点);否则其左子女为结点 2i;
( 3)如果 2i+1>n,则结点 i无右子女;否则其右子女为结点 2i+1。
7.2 二叉树的基本运算
ADT bintree {
数据对象 D,D是具有相同性质的数据元素构成的集合。
数据关系 R:如果 D为空或 D仅含一个元素,则 R为空;
否则 D中存在一个特殊的结点 root,称之为根结点,
其无前驱;其它结点被分成互不相交的两个集合,
分别构成 root的左子树 l和右子树 r;若 l和 r非空,
则它们的根结点 lroot和 rroot分别称为整棵二叉树根结点 root的后继结点;左子树 l和右子树 r也是二叉树,因而它们中数据元素间的关系也同样满足 R的定义。
二叉树的基本操作如下:
(1)createbitree(t)
(2)destroybitree(t)
(3)root(t)
(4)leftchild(t)
(5)rightchild(t)
(6)locate(t,x)
(7)parent(t,x)
(8)isempty(t)
(9)depth(t)
(10)numofnode(t)
(11)addchild(t,x,t1,b)
(12)deletechild(t,x,b)
(13)setnull(t)
(14)isequal(t1,t2)
(15)preorder(t)
(16)inorder(t)
(17)postorder(t)
(18)transform(t1,t2)
} ADT bintree.
7.3 二叉树的存储结构二叉树常用的存储结构有两种:顺序存储结构和链式存储结构。
7.3.1 顺序存储结构顺序存储结构是使用一组连续的空间存储二叉树的数据元素和数据元素之间的关系。因此必须将二叉树中所有的结点排成一个适当的线性序列,在这个线性序列中应采用有效的方式体现结点之间的逻辑关系。
1,完全二叉树的顺序存储对于一棵具有 n个结点的完全二叉树,我们可以按从上到下、同一层次按从左到右的顺序依次将结点存入一个一维数组中。根据上述性质 4,无须附加任何其它信息就能根据每个结点的下标找到它的子女结点和双亲结点。
a
b
d e
c
f
a b c d e f
0 1 2 3 4 5 6 7
(a) 完全二叉树 (b)完全二叉树的顺序存储
2 一般二叉树的顺序存储由于二叉树中每个结点最多只有两个子女,于是存储一个结点时,除了包含结点本身的属性值外,
另外增加两个域,分别用来指向该结点的两个子女在数组中的下标。
a
b
d
c
gf
e
(a) 一棵二叉树 (b) 二叉树的顺序存储
1 3 -1 -1 5 -1 -1
a b c d e f g
2 4 -1 -1 6 -1 -1
0 1 2 3 4 5 6
lchild
data
rchild
root=0 n=7
一般二叉树顺序存储数据结构的定义如下:
#define MAXSIZE 20
typedef char datatype; /*结点值的类型 */
typedef struct {
datatype data;
int lchild,rchild;
} node; /*二叉树结点的类型 */
node tree[MAXSIZE];
int n; /*树中实际所含结点的个数 */
int root; /*存放根结点的下标 */
带双亲指示的 二叉树顺序存储数据结构的定义如下:
#define MAXSIZE 20
typedef char datatype; /*结点值的类型 */
typedef struct {
datatype data;
int lchild,rchild;
int parent; /*存放双亲结点的下标 */
} node; /*二叉树结点的类型 */
node tree[MAXSIZE];
int n; /*树中实际所含结点的个数 */
int root; /*存放根结点的下标 */
7.3.2 链式存储结构二叉树的链式存储方式下每个结点也包含三个域,
分别记录该结点的属性值及左、右子树的位置。与顺序存储结构不同的是,其左、右子树的位置不是通过数组的下标,而是通过指针方式体现,如下图所示:
lchild data rchild
指针域 属性值 指针域
a
b
d
c
gf
e
a
gf
ed
b c
root
(a)一棵二叉树
(b) 二叉树的链式存储链式存储方式下二叉树结点数据结构的定义如下:
typedef char datatype; /*结点属性值的类型 */
typedef struct node{ /*二叉树结点的类型 */
datatype data;
struct node *lchild,*rchild;
} bintnode;
typedef bintnode *bintree;
bintree root;
链式存储方式下带双亲指针的二叉树结点数据结构的定义如下:
typedef char datatype; /*结点属性值的类型 */
typedef struct node{ /*二叉树结点的类型 */
datatype data;
struct node *lchild,*rchild;
struct node *parent;/*指向双亲的指针 */
} bintnode;
typedef bintnode *bintree;
bintree root; /*指向二叉树根结点的指针 */
7.4 二叉树的遍历
7.4.1 二叉树遍历的定义所谓 二叉树的遍历,是指按一定的顺序对二叉树中的每个结点均访问一次,且仅访问一次。按照根结点访问位置的不同,通常把二叉树的遍历分为三种,前序遍历,中序遍历 和 后序遍历 。
( 1)二叉树的前序遍历首先访问根结点;
然后按照前序遍历的顺序访问根结点的左子树;
再按照前序遍历的顺序访问根结点的右子树。
( 2)二叉树的中序遍历首先按照中序遍历的顺序访问根结点的左子树;
然后访问根结点;
最后按照中序遍历的顺序访问根结点的右子树。
( 3)二叉树的后序遍历首先按照后序遍历的顺序访问根结点的左子树;
然后按照后序遍历的顺序访问根结点的右子树;
最后访问根结点。
a
b
d f
e g
c 前序遍历,abdefgc
中序遍历,debgfac
后序遍历,edgfbca
7.4.2 二叉树遍历的递归实现由于二叉树的遍历是递归定义的,因此采用递归方式实现二叉树遍历的算法十分方便,只要按照各种遍历规定的次序,访问根结点时就输出根结点的值,
访问左子树和右子树时进行递归调用即可。
1,前序遍历二叉树的递归算法
void preorder(bintree t)
{ if (t) { printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
2,中序遍历二叉树的递归算法
void inorder(bintree t)
{ if (t) {
inorder(t->lchild);
printf(“%c”,t->data);
inorder(t->rchild); }
}
3,后序遍历二叉树的递归算法
void postorder(bintree t)
{ if (t) {
postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data); }
}
4,二叉树的创建算法利用二叉树前序遍历的结果可以非常方便地生成给定的二叉树,具体做法是:将第一个输入的结点作为二叉树的根结点,后继输入的结点序列是二叉树左子树前序遍历的结果,由它们生成二叉树的左子树;再接下来输入的结点序列为二叉树右子树前序遍历的结果,应该由它们生成二叉树的右子树;而由二叉树左子树前序遍历的结果生成二叉树的左子树和由二叉树右子树前序遍历的结果生成二叉树的右子树的过程均与由整棵二叉树的前序遍历结果生成该二叉树的过程完全相同,只是所处理的对象范围不同,于是完全可以使用递归方式加以实现。
void createbintree(bintree *t)
{ char ch;
if ((ch=getchar())==' ') *t=NULL;
else {
*t=(bintnode *)malloc(sizeof(bintnode));
/*生成二叉树的根结点 */
(*t)->data=ch;
createbintree(&(*t)->lchild);
/*递归实现左子树的建立 */
createbintree(&(*t)->rchild);
/*递归实现右子树的建立 */
}
}
7.4.3 二叉树遍历的非递归实现在第 5章,已经介绍了由递归程序转换成非递归程序的两种方法:简单递归程序的转换和复杂递归程序的转换;二叉树的遍历问题应该属于后者,即在采用非递归方式实现二叉树遍历时,必须使用一个堆栈记录回溯点,以便将来进行回溯。以下为一个顺序栈的定义及其部分操作的实现。
typedef struct stack /*栈结构定义 */
{ bintree data[100];
int tag[100]; /*为栈中每个元素设置的标记,用于后序遍历 */
int top; /*栈顶指针 */
} seqstack;
void push(seqstack *s,bintree t) /*进栈 */
{ s->data[++s->top]=t;
}
bintree pop(seqstack *s) /*出栈 */
{
if (s->top!=-1)
{ s->top--;
return(s->data[s->top+1]); }
else
return NULL;
}
1,二叉树前序遍历的非递归实现前序遍历一棵非空树 t 时,访问完 t的根结点后,
就应该进入 t的左子树,但此时必须将 t保存起来,
以便访问完其左子树后,进入其右子树的访问,即在 t处必须设置一个回溯点;对 t的左子树和右子树的遍历也是如此。仔细观察不难发现,这些回溯点应该使用栈来进行管理。在整个二叉树前序遍历的过程中,程序要做的工作始终分成两个部分:当前正在处理的树(子树)和保存在栈中待处理的部分,
只有这两部分的工作均完成后,程序方能结束。
void preorder1(bintree t) /*非递归实现二叉树的前序遍历 */
{ seqstack s;
s.top=-1;
while ((t) || (s.top!=-1))
/*当前处理的子树不为空或栈不为空则循环 */
{ while (t)
{ printf("%c ",t->data); s.top++;
s.data[s.top]=t; t=t->lchild;
}
if (s.top>-1)
{ t=pop(&s);
t=t->rchild;
}
}
}
2,二叉树中序遍历的非递归实现中序遍历一棵非空树 t时,首先应该进入 t的左子树访问,此时由于 t的根结点及右子树尚未访问,
因此必须将 t保存起来,放入栈中,以便访问完其左子树后,从栈中取出 t,进行其根结点及右子树的访问;对 t的左子树和右子树的遍历也是如此。在整个二叉树中序遍历的过程中,程序要做的工作始终分成两个部分:当前正在处理的树(子树)和保存在栈中待处理的部分,只有这两部分的工作均完成后,
程序方能结束。
void inorder1(bintree t)
{ seqstack s;
s.top=-1;
while((t!=NULL) || (s.top!=-1))
{ while (t)
{ push(&s,t); t=t->lchild; }
if (s.top!=-1)
{ t=pop(&s);
printf("%c ",t->data);
t=t->rchild;
}
}
}
3,二叉树后序遍历的非递归实现后序遍历一棵非空树 t时,首先应该进入 t的左子树访问,此时由于 t的右子树及根结点尚未访问,因此必须将 t保存在栈中,以便访问完其左子树后,从栈中取出 t,进行其右子树及根结点的访问。值得注意的是,
当一个元素位于栈顶即将被处理时,其左子树的访问一定已经完成,如果其右子树尚未遍历,接下来应该进入其右子树的访问,而此时该栈顶元素是不能出栈的,因为其根结点还未被访问;只有等到其右子树也访问完成后,该栈顶元素才能出栈,并输出其根结点的值。因此一个元素位于栈顶时,必须设法识别其右子树是否已被访问。
解决的方法为:使用 seqstack类型中的数组 tag,
用于标识栈中每个元素的状态:
每个元素刚进栈时,其 tag值初始化为 0;
当某一元素位于栈顶即将被处理时:
( 1)如果其 tag值为 0,意味着其右子树尚未访问,
于是将其右子树作为当前处理的对象,此时该栈顶元素仍应该保留在栈中,并将其 tag的值改为 1;
( 2)如果其 tag值为 1,意味着其右子树已被访问,
接下来应该访问其根结点,并将其出栈。
在整个二叉树后序遍历的过程中,程序要做的工作始终分成两个部分:当前正在处理的树(子树)和保存在栈中待处理的部分。只有这两部分的工作均完成后,程序方能结束。
void postorder1(bintree t)
{ seqstack s;
s.top=-1;
while ((t)||(s.top!=-1))
{ while (t)
{ s.top++;
s.data[s.top]=t;
s.tag[s.top]=0;
t=t->lchild;
}
while ((s.top>-1)&& (s.tag[s.top]==1))
{ t=s.data[s.top];
printf("%c ",t->data);
s.top--;
}
if (s.top>-1)
{ t=s.data[s.top];
s.tag[s.top]=1;
t=t->rchild;
}
else t=NULL;
}
}
7,5 二叉树其它运算的实现由于二叉树本身的定义是递归的,因此关于二叉树的许多问题或运算采用递归方式实现非常地简单和自然。
1、二叉树的查找 locate(t,x)
bintree locate(bintree t,datatype x)
{ bintree p;
if (t==NULL) return NULL;
else if (t->data==x) return t;
else
{ p=locate(t->lchild,x);
if (p) return p;
else return locate(t->rchild,x);
}
}
2 统计二叉树中结点的个数 numofnode(t)
int numofnode(bintree t)
{ if (t==NULL) return 0;
else
return(numofnode(t->lchild)+numofnode(t->rchild)+1);
}
3,判断二叉树是否等价 isequal(t1,t2)
int isequal(bintree t1,bintree t2)
{ int t;
t=0;
if (t1==NULL && t2==NULL) t=1;
else if (t1!=NULL && t2!=NULL)
if (t1->data==t2->data)
if (isequal(t1->lchild,t2->lchild))
t=isequal(t1->rchild,t2->rchild);
return(t);
}
4,求二叉树的高 (深 )度 depth(t)
int depth(bintree t)
{ int h,lh,rh;
if (t==NULL) h=0;
else {
lh=depth(t->lchild);
rh=depth(t->rchild);
if (lh>=rh) h=lh+1;
else h=rh+1;
}
return h;
}
7.6 穿线二叉树
7.6.1 穿线二叉树的定义所谓 穿线二叉树,即在一般二叉树的基础上,
对每个结点进行考察。若其左子树非空,则其左指针不变,仍指向左子女;若其左子树为空,则让其左指针指向某种遍历顺序下该结点的前驱;若其右子树非空,则其右指针不变,仍指向右子女;若其右子树为空,则让其右指针指向某种遍历顺序下该结点的后继。如果规定遍历顺序为前序,则称为 前序穿线二叉树 ;如果规定遍历顺序为中序,则称为中序穿线二叉树 ;如果规定遍历顺序为后序,则称为 后序穿线二叉树 。本小节主要介绍中序穿线二叉树。
在穿线二叉树的每个结点中,增加两个标志位:
ltag和 rtag,其含义为:
ltag=0 表示结点的左指针指向其左子女;
ltag=1 表示结点的左指针指向其中序遍历的前驱;
rtag=0 表示结点的右指针指向其右子女;
rtag=1 表示结点的右指针指向其中序遍历的后继 。
每个结点的结构如下图所示:
ltag lchild data rchild rtag
a
b
c d
f
e
g
a
b
c d
f
e
g
(a)一棵二叉树 (b)中序穿线二叉树
(b)图中 实线表示指针,虚线表示线索。
7.6.2中序穿线二叉树的基本运算
ADT binthrtree {
数据对象 D:具有相同性质的数据元素构成的有限集合;
数据关系 R:如果 D为空或 D仅含一个元素,则 R为空;否则
D中存在一个特殊的结点 root,称之为根结点,其无前驱;其它结点被分成互不相交的两个集合,分别构成
root的左子树 l和右子树 r;若 l和 r非空,则它们的根结点 lroot和 rroot分别称为整棵二叉树根结点 root的后继结点;左子树 l和右子树 r也是二叉树,因而它们中数据元素之间也同样满足上述关系。对于二叉树中的任何结点,如其左子树非空,则其 lchild指向其左子树,否则指向其中序遍历顺序下的前驱结点;如其右子树非空,则其 rchild指向其右子树,否则指向其中序遍历顺序下的后继结点。
基本操作集为,
(1) createthrtree(p)
(2) inthreading(p)
(3) locate(p,x)
(4) infirstnode(p)
(5) inlastnode(p)
(6) inprednode(p)
(7) insuccnode(p)
(8) preinsert(p,x,y)
(9) succinsert(p,x,y)
(10) delete(p,x)
(11) inthrtree(p)
(12) prethrtree(p)
(13) postthrtree(p)
} ADT binthrtree
7.6.3 中序穿线二叉树的存储结构及其实现
1,中序穿线二叉树在链接方式下的数据类型定义
typedef char datatype;
typedef struct node
{
datatype data;
int ltag,rtag; /*左、右标志位 */
struct node *lchild,*rchild;
}binthrnode;
typedef binthrnode *binthrtree;
2,创建中序穿线二叉树 createthrtree(p)
创建一棵中序穿线二叉树的办法之一为:首先建立一棵一般的二叉树,然后对其进行中序线索化。实现二叉树中序线索化可以借助于二叉树中序遍历的算法,只需将二叉树中序遍历算法中对当前结点的输出操作改为对该结点进行穿线;为了实现对当前结点的穿线,必须设置一个指针 pre,用于记录当前结点中序遍历的前驱结点。
binthrtree pre=NULL; /*初始化前驱结点 */
void createbintree(binthrtree *t)
{ char ch;
if ((ch=getchar())==) *t=NULL;
else { *t=(binthrnode *)malloc(sizeof(binthrnode));
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}
void inthreading(binthrtree *p)
{ /*对二叉树进行中序线索化 */
if (*p)
{ inthreading(&((*p)->lchild));
(*p)->ltag=((*p)->lchild)?0:1;
(*p)->rtag=((*p)->rchild)?0:1;
if (pre)
{ if(pre->rtag==1) pre->rchild=*p;
if((*p)->ltag==1) (*p)->lchild=pre;
}
pre=*p;
inthreading(&((*p)->rchild));
}
}
void createthrtree(binthrtree *p)
{ createbintree(p);
inthreading(p); }
3,中序遍历中序穿线二叉树 inthrtree(p)
基本思想:首先找到中序遍历下的第一个结点(从根结点出发,沿着左指针不断往左下走,直到左指针为空,到达,最左下,的结点即可),访问它后,然后不断寻找结点在中序下的后继结点并输出,直至所有的结点均被输出为止。
binthrtree insuccnode(binthrtree p)
{ /*寻找结点 p在中序遍历下的后继结点 */
binthrtree q;
if (p->rtag==1) return p->rchild;
else { q=p->rchild;
while (q->ltag==0) q=q->lchild;
return q;
}
}
void inthrtree(binthrtree p)
{ /*中序遍历中序穿线二叉树 p*/
if (p)
{ /*求二叉树 p中序遍历下的第一个结点 */
while (p->ltag==0)
p=p->lchild;
do
{ printf(“%c,,p->data);
p=insuccnode(p); }
while (p);
}
}
7.7 树、森林和二叉树的转换
7.7.1 树、森林到二叉树的转换将树或森林转换成其对应二叉树的方法为:
(1) 在所有兄弟结点之间添加一条连线,如果是森林,则在其所有树的树根之间同样也添加一条连线;
(2) 对于树、森林中的每个结点,除保留其到第一个子女的连线外,撤消其到其它子女的连线;
(3) 将以上得到的树按照顺时针方向旋转 45度。
a
b c d
e f g
a
b c d
e f g
a
b c d
e f g
a
b c
d
e f
g
(a) (b)
(c) (d)
树到二叉树的转换
a
b c d
e f
g
h i
a
b
c
de
f
g
h
i
a
b c d
e f
g
h i
a
b c d
e f
g
h i
(a) (b)
(c) (d)
森林到二叉树的转换
7.7.2 二叉树到树、森林的转换二叉树到树、森林也有一种对应的转换关系,
其过程恰巧为上述过程的逆过程,具体方法如下:
(1) 首先将二叉树按照逆时针方向旋转 45度;
(2) 若某结点是其双亲的左子女,则把该结点的右子女,右子女的右子女,…… 都与该结点的双亲用线连起来;
(3) 最后去掉原二叉树中所有双亲到其右子女的连线。
a
b
d e
c
f g
h i
a
b
d
e
c
f
g
h
i
a
b
d
e
c
f
g
h
i
a
b
d
e
c
f
g
h
i
(a) (b)
(c) (d)
二叉树到树、森林的转换