文档介绍：第6章二叉树和树
11/10/2017
1
计算机教研室
树型结构是一类重要的非线性结构。树型结构是结点之间有分支,并且具有层次关系的结构,它非常类似于自然界中的树。树结构在客观世界中是大量存在的。例如家谱、行政组织机构都可用树形象地表示。
树结构在计算机领域中也有着广泛的应用,例如在编译程序中,用树结构来表示源程序的语法结构;在数据库系统中,可用树结构来组织信息;在分析算法的行为时,可用树结构来描述其执行过程等等。
11/10/2017
2
计算机教研室
二叉树
二叉树在树结构的应用中起着非常重要的作用,因为对二叉树的许多操作算法简单,而任何树都可以与二叉树相互转换,这样就解决了树的存储结构及其运算中存在的复杂性。
11/10/2017
3
计算机教研室
二叉树的定义
二叉树(Binary Tree)是由n(n≥0)个结点的有限集合构成,此集合或者为空集,或者由一个根结点及两棵互不相交的左右子树组成,并且左右子树都是二叉树。
这是一个递归定义。二叉树可以是空集合,根可以有空的左子树或空的右子树。
11/10/2017
4
计算机教研室
基本术语
结点(node)——表示树中的元素,包括数据项及若干指向其子树的分支
结点的度(degree)——结点拥有的子树数
叶子(leaf)——度为0的结点
孩子(child)——结点子树的根称为该结点的孩子
双亲(parents)——孩子结点的上层结点叫该结点的~
1
2
3
11
4
5
8
9
12
6
7
10
兄弟(sibling)——同一双亲的孩子
树的度——一棵树中最大的结点度数
结点的层次(level)——从根结点算起,根为第一层,它的孩子为第二层……
深度(depth)——树中结点的最大层次数
11/10/2017
5
计算机教研室
二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也要进行区分,说明它是左子树,还是右子树。这是二叉树与树的最主要的差别。下图列出二差树的5种基本形态,图(C) 和图(d)是不同的两棵二叉树。
(a)
空二叉树
A
A
B
A
B
A
C
B
(b)
根和空的左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树
二叉树的5种形式示意
二叉树的5种形式
11/10/2017
6
计算机教研室
1、满二叉树(Full Binary Tree)
一棵深度为k且由2k-1个结点组成的二叉树称为满二叉树。下图就是一棵满二叉树,对结点进行了顺序编号。
2
4
5
3
6
7
1
满二叉树示例
特殊形态的二叉树:满二叉树、完全二叉树
11/10/2017
7
计算机教研室
2、plete Binary Tree)
如果一棵二叉树各层都是“满的”,只是最下一层从右边起连续缺少几个结点,称此二叉树为完全二叉树。
可见,满二叉树是完全二叉树的特例。
1
2
3
5
6
完全二叉树示例
4
1
2
3
4
5
7
1
2
3
6
7
非完全二叉树示例
11/10/2017
8
计算机教研室
满二叉树:
完全二叉树:
1
2
4
5
8
9
10
11
3
6
7
12
13
14
15
1
2
4
5
8
9
10
11
3
6
7
12
11/10/2017
9
计算机教研室
二叉树的操作
1、建立一棵空二叉树:InitialBTree(BT)
初始条件:无;
操作结果:构造一棵空树BT。
2、按某种规则建立一棵二叉树:CreateBTree(BT)
初始条件:无;
操作结果:按某种规则构造一棵二叉树BT。
3、求二叉树BT的树根结点:RootBTree(BT)
初始条件:二叉树BT已存在;
操作结果:返回二叉树BT的根结点。
4、求二叉树BT中结点p的双亲:ParentBTree(BT,p)
初始条件:二叉树BT已经存在,且p是二叉树BT中的一个结点;
操作结果:若结点p不是二叉树BT的根结点,则返回结点p的双亲结点;
否则,返回NULL。
11/10/2017
10
计算机教研室