自考数据结构导论__02142_第4章

1、第四章第四章14.1 树的基本概念树的基本概念4.2 二叉树二叉树4.3 二叉树的存储结构二叉树的存储结构4.4 二叉树的遍历二叉树的遍历4.5 树和森林树和森林4.6 哈夫曼树哈夫曼树第四章第四章2 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，

2、例如在编译程序中，用树来表示树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。的行为时，可用树来描述其执行过程等等。4.1 树的定义和基本术语树的定义和基本术语树树是是n(n=0)n(n=0)个结点的有限集个结点的有限集T T，满足：，满足： (1)(1)有且仅有一个特定的称为有且仅有一个特定的称为根根的结点；的结点； (2)(2)其余的结点可分为其余的结点可分为m(m=0)m(m=0)个个互不相交互不相交的子集的子集 T

3、 T1 1,T,T2 2,T,T3 3TTm m，其中每个子集，其中每个子集T Ti i又是一棵树，又是一棵树， 并称其为并称其为子树子树。一、树的定义一、树的定义递归是树的固有特性递归是树的固有特性第四章第四章3 二、树的逻辑表示二、树的逻辑表示 一般表示法一般表示法(直观表示法直观表示法)： FCEGBDA b、嵌套括号法：嵌套括号法： (根根(子树子树,子树子树子树子树) ( A ( B ( E, F ), C , D ( G ) ) 根根 ABFCDGEc、凹入法表示：凹入法表示： 另三种表示法另三种表示法a、文氏图法：文氏图法：BACDEFG第一层第一层第二层第二层第三层第三层第四章

4、第四章4三、树的基本术语三、树的基本术语度度结点的度结点的度：该结点的子树数（即分支数）。：该结点的子树数（即分支数）。树的度树的度：树中结点的度最大值。：树中结点的度最大值。结点结点由一个数据元素及若干指向其它结点的分支所组成。由一个数据元素及若干指向其它结点的分支所组成。叶子（终端结点）叶子（终端结点）度为零的结点。度为零的结点。孩子（子结点）孩子（子结点）结点的子树的根称为该结点的孩子。结点的子树的根称为该结点的孩子。双亲（父结点）双亲（父结点）一个结点称为该结点所有子树根的双亲。一个结点称为该结点所有子树根的双亲。非终端结点非终端结点度不为零的结点。度不为零的结点。祖先祖先结点祖先指根

5、到此结点的一条路径上的所有结点。结点祖先指根到此结点的一条路径上的所有结点。子孙子孙从某结点到叶结点的分支上的所有结点称为该结从某结点到叶结点的分支上的所有结点称为该结 点的子孙。点的子孙。兄弟兄弟同一双亲的孩子之间互称兄弟。同一双亲的孩子之间互称兄弟。第四章第四章5结点的层次结点的层次从根算起，根为第一层，其孩子在第二层从根算起，根为第一层，其孩子在第二层, .， L层上任何结点的孩子都在层上任何结点的孩子都在L+1层上。层上。堂兄弟堂兄弟其双亲在同一层的结点。其双亲在同一层的结点。树的深度树的深度树中结点的最大层次。树中结点的最大层次。森林森林是是m（0）棵树的集合。）棵树的集合。有序树有

6、序树若树中各结点的子树从左到右是有次序的，若树中各结点的子树从左到右是有次序的， 不能互换，称为有序树。不能互换，称为有序树。无序树无序树若树中各结点的子树是无次序的，若树中各结点的子树是无次序的， 可以互换，则成为无序树。可以互换，则成为无序树。第四章第四章6求根求根Root(T):求树求树T的根结点；的根结点；求双亲求双亲Parent(T,X):求结点求结点X在树在树T上的双亲；上的双亲；若若X是树是树T的根或的根或X不在不在T上，则结果为一特殊上，则结果为一特殊标志；标志；求孩子求孩子Child(T,X,i):求树求树T上结点上结点X的第的第i个孩子个孩子结点；若结点；若X不在不在T上或

7、上或X没有第没有第i个孩子，则结个孩子，则结果为一特殊标志；果为一特殊标志；建树建树Create(X,T1,Tk),k1:建立一棵以建立一棵以X为根，为根，以以T1,Tk为第为第1,k棵子树的树；棵子树的树；剪枝剪枝Delete(T,X,i):删除树删除树T上结点上结点X的第的第i棵子棵子树；若树；若T无第无第i棵子树，则为空操作；棵子树，则为空操作；遍历遍历Traverse Tree(T):遍历树，即访问树中每遍历树，即访问树中每个结点，且每个结点仅被访问一次个结点，且每个结点仅被访问一次。四、树的基本操作四、树的基本操作第四章第四章7 二叉树在树结构的应用中起着非常重要的作用，因为二叉树有

8、许多二叉树在树结构的应用中起着非常重要的作用，因为二叉树有许多良好的性质和简单的物理表示，而任何树都可以与二叉树相互转换，这良好的性质和简单的物理表示，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。样就解决了树的存储结构及其运算中存在的复杂性。4.2 二叉树二叉树1 1、定义：、定义： 二叉树二叉树是是n(n=0)n(n=0)个结点的有限集合，它或为空个结点的有限集合，它或为空(n=0)(n=0)，或是由一个或是由一个根结点根结点及及两棵两棵互不相交的互不相交的左、右左、右子树子树组成，且每棵子树都是二叉树。组成，且每棵子树都是二叉树。4.2.1 4.2.1

9、二叉树的基本概念二叉树的基本概念 这是一个这是一个递归递归定义。定义。二叉树可以是空集合，二叉树可以是空集合，根可以有空的左子树根可以有空的左子树或空的右子树。或空的右子树。ABDCFGHE第四章第四章8 2、特点：、特点： 二叉树可以是空的，称二叉树可以是空的，称空二叉树空二叉树； 每个结点每个结点最多最多只能有两个孩子；只能有两个孩子； 子树有左、右之分且子树有左、右之分且次序不能颠倒次序不能颠倒。、二叉树与树的比较：、二叉树与树的比较： 结结 点点 子子 树树 结点顺序结点顺序 树树 n 0 不定不定(有限有限) 无无二叉树二叉树 n0 2 有有(左、右左、右) 第四章第四章9 二叉树结

10、点的子树要区分左子树和右子树，即使只有一棵子树二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出最主要的差别。下图列出二叉树的二叉树的5 5种基本形态种基本形态，图，图(C) (C) 和（和（d d）是）是不同的两棵二叉树。不同的两棵二叉树。 (a) 空二叉树空二叉树A (b) 根和空的根和空的 左右子树左右子树A (c) 根和左子树根和左子树A (d)根和右子树根和右子树A (e)根和左右子树根和左右子树二叉树的二叉树的5种形式种形式4.2.1 4.2

11、.1 二叉树的定义二叉树的定义第四章第四章10 初始化初始化Initiate(BT):建立一棵空二叉树，建立一棵空二叉树，BT= 。 求双亲求双亲Parent(BT,X):求出二叉树求出二叉树BT上结点上结点X的双亲结点，的双亲结点，若若X是是BT的根或的根或X根本不是根本不是BT上的结点，运算结果为上的结点，运算结果为NULL。 求左孩子求左孩子Lchild(BT,X)和求右孩子和求右孩子Rchild(BT,X)：分别求分别求出二叉树出二叉树BT上结点上结点X的左、右孩子；若的左、右孩子；若X为为BT的叶子或的叶子或X补在补在BT上，运算结果为上，运算结果为NULL。 建二叉树建二叉树Cre

12、ate(BT):建立一棵二叉树建立一棵二叉树BT。 先序遍历先序遍历PreOrder(BT):按先序对二叉树按先序对二叉树BT进行遍历，每进行遍历，每个结点被访问一次且仅被访问一次，若个结点被访问一次且仅被访问一次，若BT为空，则运算为空，则运算为空操作。为空操作。4、二叉树的基本操作（见、二叉树的基本操作（见P77）第四章第四章11中序遍历中序遍历InOrder(BT):按中序对二叉树按中序对二叉树BT进行进行遍历，每个结点被访问一次且仅被访问一次，遍历，每个结点被访问一次且仅被访问一次，若若BT为空，则运算为空操作。为空，则运算为空操作。后序遍历后序遍历PreOrder(BT):按后序对二

13、叉树按后序对二叉树BT进进行遍历，每个结点被访问一次且仅被访问一次，行遍历，每个结点被访问一次且仅被访问一次，若若BT为空，则运算为空操作。为空，则运算为空操作。层次遍历层次遍历LevelOrder(BT):按层从上往下，同按层从上往下，同一层中结点按从左往右的顺序，对二叉树进行一层中结点按从左往右的顺序，对二叉树进行遍历，每个结点被访问一次且仅被访问一次，遍历，每个结点被访问一次且仅被访问一次，若若BT为空，则运算为空操作。为空，则运算为空操作。第四章第四章121 1、性质、性质1 1： 在二叉树的第在二叉树的第i(i=1)i(i=1)层上至多有层上至多有2 2i-1i-1个结点。个结点。二

14、叉树具有下列重要性质：二叉树具有下列重要性质：4.2.2 4.2.2 二叉树的性质二叉树的性质（）2 2、性质、性质2 2：深度为深度为k(k=1)k(k=1)的二叉树至多有的二叉树至多有2 2k k1 1个结点。个结点。3 3、性质、性质3 3：对任何一棵二叉树，如果其终端结点对任何一棵二叉树，如果其终端结点 数为数为n n0 0，度为，度为2 2的结点数为的结点数为n n2 2，则，则n n0 0n n2 21 1。 即：即：叶结点数叶结点数n n0 0= =度为度为2 2的结点数的结点数n n2 2+1+1第四章第四章13 满二叉树（满二叉树（结点数结点数=2=23 3-1=7-1=7）

15、满二叉树中满二叉树中结点顺序编号结点顺序编号：即从第一层结点开始自上：即从第一层结点开始自上 而下，从左到右进行连续编号。而下，从左到右进行连续编号。满二叉树满二叉树深度为深度为k(k=1)且有且有2 2k k-1-1个结点的二个结点的二叉树。叉树。4.2.2 4.2.2 二叉树的性质二叉树的性质1234567第四章第四章1412345612345712367注：注：满二叉树是完全二叉树的特例。满二叉树是完全二叉树的特例。完全二叉树完全二叉树深度为深度为K K的二叉树中，的二叉树中，K-1K-1层层结点数是满的结点数是满的(2(2k-2k-2 ) )，K K层结点是左连续的层结点是左连续的(

16、(即即结点编号是连续的结点编号是连续的) )。如下图（如下图（a a）4.2.2 4.2.2 二叉树的性质二叉树的性质(a)完全二叉树完全二叉树YES!(b)非完全二叉树非完全二叉树NO!( c)非完全二叉树非完全二叉树NO!第四章第四章15 符号【符号【x x】表示不大于】表示不大于x x的最大整数。的最大整数。 假设此二叉树的深度为假设此二叉树的深度为k k，则根据性质，则根据性质2 2及完全二叉及完全二叉树的定义得到：树的定义得到：2 2k-1k-11n=21n=2k k-1 -1 或或 2 2k-1k-1=n2=n2k k取对数得到：取对数得到：k k1log1log2 2nk n1i

17、1，则，则i i的双亲的双亲Parent(A)Parent(A)是结点是结点i/2i/2; ;（2 2）如果如果2 2* *inin，则其，则其左孩子是结点左孩子是结点2 2* *i i, , 否则，结点否则，结点i i无左孩子且为叶子结点；无左孩子且为叶子结点；（3 3）如果如果2 2* *i i1n1n，则其，则其右孩子是结点右孩子是结点2 2* *i i1 1， 否则，结点否则，结点i i无右孩子。无右孩子。A 1B 2C 3D 4E F 6H 8IJ 10G 759第四章第四章17思考题思考题: :一棵完全二叉树一棵完全二叉树, ,结点总数结点总数n=980,n=980,问问: :该二

18、叉树的深度该二叉树的深度=?=?最下层结点个数最下层结点个数=?=?度为度为1 1的结点个数的结点个数n n1 1=?=?叶结点个数叶结点个数n n0 0=?=?性质性质4 4性质性质2 2完全二叉树定义完全二叉树定义性质性质3 3结点数最少结点数最少 个个? ?深度为深度为5 5的二叉树的二叉树结点数最多结点数最多 个个? ?结点数最少结点数最少 个个? ?深度为深度为5 5的完全二叉树的完全二叉树结点数最多结点数最多 个个? ?5 5313116163131第四章第四章181. 树最适合用来表示树最适合用来表示( ) A.有序数据元素有序数据元素 B.无序数据元素无序数据元素 C.元素之间

19、具有分支层次关系的数据元素之间具有分支层次关系的数据 D.元素之间无联系的数据元素之间无联系的数据 2. 根据定义，树的叶子结点其度数（）根据定义，树的叶子结点其度数（） A. 必大于必大于0 B. 必等于必等于0 C.必等于必等于1 D.必等于必等于2 3. 对一棵有对一棵有100个结点的完全二叉树按层序编号，则编号为个结点的完全二叉树按层序编号，则编号为49的结的结 点，它的左孩子的编号为（点，它的左孩子的编号为（ ） A. 99 B. 98 C. 97 D. 50 4. 树形结构中，若结点有个兄弟，是的双亲，则的度为树形结构中，若结点有个兄弟，是的双亲，则的度为 _。 5. 深度为深度为

20、15的满二叉树上，第的满二叉树上，第11层有层有 个结点。个结点。6. 三个结点可构成三个结点可构成 种不同形态的二叉树。种不同形态的二叉树。 请你给出答案请你给出答案想一想想一想CAB4210=10245第四章第四章19 它是用一组连续的存储单元存储二叉树的数据元素。因此，必须它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，可用编号的方法。相互位置能反映出结点之间的逻辑关系，可用编号的方法。二叉树的顺序存储结构二叉树的顺序存储结构

21、即对二叉树按完全二即对二叉树按完全二叉树进行编号，然后用一维数组存储，其中叉树进行编号，然后用一维数组存储，其中编号编号为为i i的结点存储在数组中的结点存储在数组中下标为下标为i i的分量中。的分量中。 该方法称为该方法称为“以编号为地址以编号为地址”策略策略4.3.1 4.3.1 二叉树的顺序存储结构二叉树的顺序存储结构4.3 二叉树的存储结构二叉树的存储结构 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为

22、H H且只有且只有H H个结点的右单支树却需要个结点的右单支树却需要2 2h h-1-1个结点存储空间。而且，若经个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！常需要插入与删除树中结点时，顺序存储方式不是很好！第四章第四章20对于完全二叉树来说，采用以编号作为数组的下边的方法将结点存入一位数组中，也就是将编号为i的结点存入一维数组的以i为下标的数组元素中。对于非完全二叉树，则用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点。 l k j i h g f e d c b a 1 2 3 4 5 6 7 8 9 10 11 12 abcdefghijkl123

23、456789 1011120Btree：第四章第四章21 l k j i h g f e d c b a 1 2 3 4 5 6 7 8 9 10 11 12 此方法用于完全二叉树，则：此方法用于完全二叉树，则： 节省内存节省内存 结点位置确定方便结点位置确定方便abcdefghijkl第四章第四章22AB CDEFG 表示该处没有元素存在表示该处没有元素存在ABCDEFG用于一般二叉树：用于一般二叉树：（浪费空间）（浪费空间） 1 2 3 4 5 6 7 8 9 10 111234567891011第四章第四章23 lchild data rchild结点形式：结点形式：左孩指针左孩指针指向

24、其左孩结点；指向其左孩结点； 右孩指针右孩指针指向其右孩结点；指向其右孩结点；二叉链表类型定义二叉链表类型定义typedef struct btnode typedef struct btnode Datatype data; Datatype data; struct btnode struct btnode * *lchild,lchild,* *rchild;rchild; * *Bintree;Bintree; ;二二叉链表类型叉链表类型4.3.2 4.3.2 二叉树的链式存储结构二叉树的链式存储结构二叉链表表示法：二叉链表表示法：第四章第四章24例：例：CABDEFGH三叉链表表示法

25、：三叉链表表示法： lchild dataparent rchild结点形式：结点形式：指向双亲指向双亲4.3 4.3 二叉树的存储结二叉树的存储结构构ABDCFGHE二叉链表二叉链表T注：注：在含在含n个结点的二叉链表中有个结点的二叉链表中有2n个指针域，其中个指针域，其中n-1个用来指向结点的左右孩子，其余个用来指向结点的左右孩子，其余n+1个空链域个空链域.第四章第四章25一、遍历含义一、遍历含义 在二叉树的一些应用中，常常要求在树中查找具有某种特征的在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二结点，或者对树中全部结点逐

26、一进行某种处理。这就引入了遍历二叉树的问题。叉树的问题。遍历二叉树遍历二叉树是指按是指按一定规律一定规律对二叉树中的每对二叉树中的每个结点个结点访问访问且仅访问一次且仅访问一次即访遍树中每一结即访遍树中每一结点（只一次），打印或处理结点。点（只一次），打印或处理结点。 遍历对线性结构是容易解决的，而二叉树是非线性的，因而需遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律（或次序），能把二叉树上的各结点都访问一次且要寻找一种规律（或次序），能把二叉树上的各结点都访问一次且只访问一次。只访问一次。二、遍历规则二、遍历规则bc(根结点根结点D)(右子树右子树R)R)(左子树左子树

27、L) 由二叉树的递归定义知，二叉树由二叉树的递归定义知，二叉树的三个基本组成单元是：根结点、的三个基本组成单元是：根结点、左子树和右子树。左子树和右子树。a4.4 二叉树的遍历二叉树的遍历第四章第四章26令：令：L L 遍历左子树遍历左子树 D D 访问根结点访问根结点 R R 遍历右子树遍历右子树组合组合LDRLDR、LRDLRD、DLRDLR、RDLRDL、RLDRLD、DRLDRL先左先左 后右后右DLRDLR先（根）序遍历，先（根）序遍历， LDRLDR中（根）序遍历，中（根）序遍历， LRDLRD后（根）序遍历。后（根）序遍历。1、先序遍历先序遍历DLR 首首先先访问访问根根结点，结

28、点，其次其次遍历遍历根的根的左子树左子树，最后最后遍历根遍历根右子树右子树，对每棵子树同样按，对每棵子树同样按这三步（这三步（先根、后左、再右先根、后左、再右）进行。）进行。2、中序遍历中序遍历LDR 首首先先遍历根的遍历根的左子树左子树，其次其次访问访问根根结点，结点，最后最后遍历根遍历根右子树右子树，对每棵子树同样按，对每棵子树同样按这三步（这三步（先左、后根、再右先左、后根、再右）进行。）进行。3、后序遍历后序遍历LRD 首首先先遍历根的遍历根的左子树左子树，其次其次遍历根的遍历根的右子树右子树，最后最后访问访问根根结点，对每棵子树同样结点，对每棵子树同样按这三步（按这三步（先左、后右、

29、最后根先左、后右、最后根）进行。）进行。4.4 4.4 二叉树的遍历二叉树的遍历第四章第四章27三、遍历算法三、遍历算法1、先序遍历（递归算法、先序遍历（递归算法）：）： 步骤：步骤：若二叉树为空，则退出；若二叉树为空，则退出； 否则否则: （1）访问根结点；）访问根结点； （2）先序遍历根的左子树；）先序遍历根的左子树； （3）先序遍历根的右子树。）先序遍历根的右子树。 算法：算法： void preorder ( bitreptr r ) /*先先序序遍历以遍历以r为根的二叉树为根的二叉树*/ if (r=NULL) return; printf ( r-data ) ; /*访问根结点访

30、问根结点*/ preorder ( r-lchild ) ； preorder ( r-rchild ) ; /*先先序序遍历以遍历以r的右孩子为根的右子树的右孩子为根的右子树*/ ；4.4 4.4 二叉树的遍历二叉树的遍历第四章第四章28preorder(A)参数为根参数为根A 输出输出Apreorder(A-lchild)preorder(A-rchild)调用调用参数为根参数为根return调用调用递归调用函数递归调用函数preorderABDCE参数为根参数为根B 输出输出Bpreorder(B-lchild)Preorder(B-rchild)参数为根参数为根D 输出输出Dpreor

31、der(D-lchild)preorder(D-rchild)调用调用函数函数preorder函数函数preorder调用调用参数为根参数为根return函数函数preorder调用调用参数为根参数为根return函数函数preorder调用调用参数为根参数为根C 输出输出Cpreorder(C-lchild)preorder(C-rchild)函数函数preorder返回返回返回返回参数为根参数为根E 输出输出Epreorder(E-lchild)preorder(E-rchild)调用调用返回返回调用调用参数为根参数为根return函数函数preorder调用调用参数为根参数为根retur

32、n函数函数preorder参数为根参数为根return调用调用第四章第四章292 2、中序遍历运算、中序遍历运算（递归算法（递归算法） 步骤：步骤：若二叉树为空，则退出；若二叉树为空，则退出； 否则否则: （1）中序遍历根的左子树；）中序遍历根的左子树； （2）访问根结点；）访问根结点； （3）中序遍历根的右子树。）中序遍历根的右子树。 算法：算法： void inorder (bitreptr r) /*中序遍历以中序遍历以r为根的二叉树为根的二叉树*/ if (r=NULL) return; inorder ( r-lchild ) ； /*中序遍历以中序遍历以r的左孩子为根的左子树的左孩

33、子为根的左子树*/ printf ( r-data ) ; /*访问根结点访问根结点*/ inorder (r-rchild ) ; /*.*/ 第四章第四章303、后序遍历运算（递归算法、后序遍历运算（递归算法） 步骤：步骤：若二叉树为空，则退出；若二叉树为空，则退出； 否则否则: （1）后序遍历根的左子树；）后序遍历根的左子树； （2）后序遍历根的右子树。）后序遍历根的右子树。 （3）访问根结点；）访问根结点； 算法：算法： void postorder (bitreptr r) /*后序遍历以后序遍历以r为根的二叉树为根的二叉树*/ if (r=NULL) return; postord

34、er ( r-lchild ) ； /*后序遍历以后序遍历以r的左孩子为根的左子树的左孩子为根的左子树*/ postorder ( r-rchild ) ； printf ( r-data ) ; /*访问根结点访问根结点*/ 第四章第四章31 对于如下图的二叉树，其先序、中序、后序遍对于如下图的二叉树，其先序、中序、后序遍历的序列为：历的序列为：ABCDFGEHA、B、D、F、G、C、E、H 。 B、F、D、G、A、C、E、H 。F、G、D、B、H、E、C、A 。先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：第四章第四章32以中序遍历为例来说明中序遍历二叉树的递归过程以中序遍历

35、为例来说明中序遍历二叉树的递归过程ABDCEBD第一次经过第一次经过第二次经过第二次经过第三次经过第三次经过第四章第四章33 二叉树的层次遍历：二叉树的层次遍历：从二叉树的根结点的这一层开始，逐层向下从二叉树的根结点的这一层开始，逐层向下遍历，在每一层上按从左到右的顺序对结点逐个访问。遍历，在每一层上按从左到右的顺序对结点逐个访问。四、二叉树的层次遍历四、二叉树的层次遍历ABCDFGEH右图按照层次遍历，所得到的右图按照层次遍历，所得到的的结点序列为：的结点序列为：ABCDEFGH设立一个队列设立一个队列Q，用于存放结点，以保证二叉树结点，用于存放结点，以保证二叉树结点按照层次顺序从左往右进入

36、队列。若二叉树按照层次顺序从左往右进入队列。若二叉树bt非空：非空：将根结点插入队列；将根结点插入队列；从队列中删除一个结点，访问该结点，并将该结点从队列中删除一个结点，访问该结点，并将该结点的孩子（若有的话）插入队列。的孩子（若有的话）插入队列。若此时队列非空，再从队列中删除一个结点，访问若此时队列非空，再从队列中删除一个结点，访问该结点，并将它的孩子结点插入队列。依次重复进行，该结点，并将它的孩子结点插入队列。依次重复进行，直到队列为空。直到队列为空。Void levelorder(BinTree bt) LkQue Q; InitQueue(&Q); if (bt!=NULL)

37、EnQueue(&Q,bt); while (!EmptyQueue(Q) p=Gethead(&Q); outQueue(&Q); visit(p); if (p-lchild!NULL) EnQueue(&Q,p-lchild); if (p-rchild!NULL) EnQueue(&Q,p-rchild); 第四章第四章34注：注：“遍历遍历”是二叉树各种操作的基础，可以在遍历是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对于一棵已知二叉树过程中对结点进行各种操作，如：对于一棵已知二叉树 求二叉树中结点的个数求二叉树中结点的个数

38、；求二叉树中叶子结点的个数求二叉树中叶子结点的个数；求二叉树中度为求二叉树中度为1的结点个数的结点个数；求二叉树中度为求二叉树中度为2 2的结点个数的结点个数；求二叉树中非终端结点个数求二叉树中非终端结点个数；交换结点左右孩子；交换结点左右孩子；判定结点所在层次；判定结点所在层次；6.3 6.3 遍历二叉树遍历二叉树五、遍历二叉树的应用五、遍历二叉树的应用第四章第四章35例例1：编写求二叉树中叶结点个数的算法编写求二叉树中叶结点个数的算法(设二设二叉树的二叉链表的根指针为叉树的二叉链表的根指针为bt)。 int leafcount (bitreptr bt ) /*求二叉树求二叉树bt中叶结点

39、的数目中叶结点的数目*/ if ( bt = NULL ) return (0) ; else if ( bt-lchild = NULL & bt-rchild = NULL ) return (1) ; else n = leafcount( bt-lchild ) ; /* 求左子树的叶子数目求左子树的叶子数目*/ m = leafcount(bt-rchild) ; /* 求右子树的叶子数目求右子树的叶子数目*/ return (m+n) ; 第四章第四章36例例2：编写输出二叉树中所有度为编写输出二叉树中所有度为1 1的结点的数据域的的结点的数据域的值，并统计其数目的算法值，

40、并统计其数目的算法( (设二叉树的二叉链表的根指设二叉树的二叉链表的根指针为针为t)t)。 int onesoncount(bitreptr t)/*输出二叉树输出二叉树t中度为中度为1的结点值，并求其个数的结点值，并求其个数*/ if (t=NULL) return(0); else if (t-lchild=NULL & t-rchild!=NULL) | (t-lchild!=NULL & t-rchild=NULL) printf(t-data); return(onesoncount(t-lchild)+ onesoncount(t-rchild)+1); else

41、return(onesoncount(t-lchild)+ onesoncount(t-rchild);第四章第四章37例例3：编写输出二叉树中所有度为编写输出二叉树中所有度为2 2的结点的数据域的的结点的数据域的值，并统计其数目的算法值，并统计其数目的算法( (设二叉树的二叉链表的根指设二叉树的二叉链表的根指针为针为BT)BT)。 int twoson(bitreptr BT)/*输出二叉树输出二叉树BT中所有度为中所有度为2的结点的数据域值，并统计其数目的结点的数据域值，并统计其数目*/ if (BT=NULL) return(0); else if (BT-lchild=NULL | B

42、T-rchild=NULL) return(twoson(BT-lchild)+ twoson (BT-rchild); else if (BT-lchild!=NULL & BT-rchild!=NULL) printf(BT-data); return(twoson(BT-lchild)+ twoson(BT-rchild)+1); 第四章第四章38例例4：编写一算法，打印出一棵二叉树中所有非终端编写一算法，打印出一棵二叉树中所有非终端结点的值，并统计非终端结点的个数。结点的值，并统计非终端结点的个数。( (二叉树以二叉二叉树以二叉链表存储，根指针为链表存储，根指针为bt)bt)

43、int notleafcount (bitreptr bt ) /*求二叉树求二叉树bt中非叶结点的数目中非叶结点的数目*/ if ( bt = NULL ) return (0) ; else if ( bt-lchild = NULL & bt-rchild = NULL ) return (0) ; /*无左右子树无左右子树*/ else printf(bt-data); /* 输出非终端结点值输出非终端结点值*/ n = notleafcount( bt-lchild ) ; /* 求左子树的非终端结点数目求左子树的非终端结点数目*/ m = notleafcount(bt-r

44、child) ; return (m+n+1) ; /* 返回总的非终端结点数返回总的非终端结点数*/ 第四章第四章39例例5： 编写一算法，打印出一棵二叉树中所有结点的编写一算法，打印出一棵二叉树中所有结点的值，并统计结点的个数。值，并统计结点的个数。( (二叉树以二叉链表存储，根二叉树以二叉链表存储，根指针为指针为bt)bt) int f5 (int f5 (bitreptr bt ) bt )/ /* * 打印出二叉树打印出二叉树t t中所有结点的值，并统计结点的个数中所有结点的值，并统计结点的个数 * */ / if ( bt = NULL ) if ( bt = NULL ) ret

45、urn (0) ; return (0) ; else else printf(bt-data); / printf(bt-data); /* * 输出结点值输出结点值* */ / n = f5( bt-lchild); n = f5( bt-lchild); / /* * 求左子树的结点数目求左子树的结点数目* */ / m = f5( bt-rchild); m = f5( bt-rchild); / /* * 求右子树的结点数目求右子树的结点数目* */ / return (m+n+1) ; / return (m+n+1) ; /* * 返回总的结点数返回总的结点数* */ / 第四章

46、第四章40例例6：设二叉树存储结构采用二叉链表表示，每个结设二叉树存储结构采用二叉链表表示，每个结点的数据域中存放一个整数。试编写一个算法，求此点的数据域中存放一个整数。试编写一个算法，求此二叉树上数据域的值为的结点个数。二叉树上数据域的值为的结点个数。 int f6 (bitreptr bt ) /*求二叉树求二叉树bt结点数据域值为的结点的数目结点数据域值为的结点的数目*/ if ( bt = NULL ) return (0) ; else if (bt-data=) return(f6(bt-lchild)+f6(bt-rchild)+1); else return(f6(bt-lch

47、ild)+f6(bt-rchild); 第四章第四章41一、双亲表示法一、双亲表示法 以一组连续空间存储树的结点，即一个一维数组构成，以一组连续空间存储树的结点，即一个一维数组构成，数组每个分量包含两个域：数据域和双亲域。数据域用数组每个分量包含两个域：数据域和双亲域。数据域用于存储树上一个结点的数据元素值，双亲域用于存储本于存储树上一个结点的数据元素值，双亲域用于存储本结点的双亲结点在数组中的序号（下标值）。结点的双亲结点在数组中的序号（下标值）。4.5 4.5 树和森林树和森林例：例：双亲表示双亲表示 A - 1 B 0 C 0 D 1 E 1 F 2 G 2 H 4 I 4 G 4数组下

48、标数组下标0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9每个数组元素每个数组元素含两个成员，含两个成员，即：（结点值即：（结点值和其双亲在表和其双亲在表中的位置）中的位置）注：注：找父结点容易，找结点找父结点容易，找结点的孩子麻烦，需遍历整张表。的孩子麻烦，需遍历整张表。4.5.1 4.5.1 树的存储结构（三种）树的存储结构（三种）ABGCDEFHJI第四章第四章42 根结点没有双亲，双亲域的值为根结点没有双亲，双亲域的值为-1。双亲链表的类型。双亲链表的类型定义如下：定义如下： #define size 10typedef struct datatype d

49、ata; int parent; Node;Node slistsize;第四章第四章43二、孩子链表表示法二、孩子链表表示法树中每个结点的孩子串成一单链表树中每个结点的孩子串成一单链表孩子链表孩子链表n n个结点个结点nn个孩子链表个孩子链表n n个头指针用顺序表存储个头指针用顺序表存储表头数组：表头数组：数组元素存数组元素存储结点本身的信息和该结点的孩子链表的头指针。储结点本身的信息和该结点的孩子链表的头指针。孩子链表的结点为孩子链表的结点为:childnext存放孩子结点在表头数组中的序号存放孩子结点在表头数组中的序号指向下一个孩子结点指向下一个孩子结点第四章第四章44孩子链表表示法的类

50、型定义：孩子链表表示法的类型定义：# define MAXND 20typedef struct bnodeint child; struct bnode *next;node,*childlink;Typedef struct DataType data; childlink hp;headnode;Headnode ；linkMAXND；第四章第四章45 A B CDEFGHIJ数组下标数组下标0 01 12 2 3 3 4 4 5 5 6 6 7 7 8 8 9 912987注注: :在孩子链表表示中，找孩子方便，但在孩子链表表示中，找孩子方便，但 求结点的双亲困难，因此可在顺序表中再增

51、求结点的双亲困难，因此可在顺序表中再增加一个域，用于指明每个结点的双亲在表中加一个域，用于指明每个结点的双亲在表中位置，即将双亲表示法和孩子链表表示法结位置，即将双亲表示法和孩子链表表示法结合起来。合起来。3435ABGCDEFHJI第四章第四章46双亲孩子表示法双亲孩子表示法树中每个结点的孩子串成一单链表树中每个结点的孩子串成一单链表孩子链表孩子链表n n个结点个结点nn个孩子链表个孩子链表 同时用一维数组顺序存储树中的各结点，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的数组元素除了包括结点本身的信息和该结点的孩子链表的头指针之外，还增设一个域，用来孩子链表的

52、头指针之外，还增设一个域，用来存储结点双亲结点在数组中的序号。存储结点双亲结点在数组中的序号。第四章第四章47 A -1B 0 C 0 D 1 E 1F 2 G 2 H 4 I 4 J 4 数组下标数组下标0 01 12 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9ABGCDEFHJI129873435parent hp# define MAXND 20typedef struct bnodeint child; struct bnode *next;node,*childlink;Typedef struct DataType data; int parent; childli

53、nk hp;headnode;Headnode ；linkMAXND；第四章第四章48三、孩子兄弟链表表示法三、孩子兄弟链表表示法（二叉链表表示）（二叉链表表示） sondatabrother结点形式：结点形式：指向结点的第一个孩子结点指向结点的第一个孩子结点指向该结点的下一个兄弟结点指向该结点的下一个兄弟结点例：例：123456798 1 孩子兄弟孩子兄弟表表 示示 2 3 4 5 6 7 8 9 第四章第四章49孩子兄弟链表表示法类型定义：孩子兄弟链表表示法类型定义：Typedef struct tnode DataType data; struct tnode *son,*brother

54、;*Tree;第四章第四章504.5.2 4.5.2 树、森林与二叉树的转换树、森林与二叉树的转换例：例：ABCGEFDHJI二叉树二叉树1 1、一般树、一般树方法：方法： 各兄弟之间加连线；各兄弟之间加连线； 对任一结点，除最左孩子外，抹掉该对任一结点，除最左孩子外，抹掉该结点与其余孩子的各枝；结点与其余孩子的各枝； 以根为轴心，将连线顺时针转以根为轴心，将连线顺时针转45450 0。加连线加连线ABCGEFDHJI留最左孩留最左孩ABCGEFDHJI转转45450 0ABCGEFDHJI第四章第四章51例：例：DABEC树树二叉树二叉树DABEC孩子兄孩子兄 弟表示弟表示二叉链二叉链 表表

55、示表表示 A B C E D A B C D E完全一样完全一样一棵树唯一对应一棵二叉树一棵树唯一对应一棵二叉树第四章第四章52二叉树二叉树2 2、森林、森林森林森林F转换成二叉树的方法如下：转换成二叉树的方法如下：l（1）将每棵树转换成相应的二叉树；）将每棵树转换成相应的二叉树；l（2）将（）将（1）中得到的各棵二叉树的根结点看做是）中得到的各棵二叉树的根结点看做是兄弟连接起来。兄弟连接起来。ABCD树树T1EF树树T2GHJI树树T3ABCDEFGHJIGHJIABCDEF森林森林F对应的二叉树对应的二叉树第四章第四章53例：例：方法：方法： 从根结点起；从根结点起； 该结点左孩和左孩右枝

56、上的结点依次该结点左孩和左孩右枝上的结点依次 作为该结点孩子；作为该结点孩子； 重复重复 。还原还原ABCGEFD一般树一般树3 3、二叉树、二叉树还原还原ABCGEFD根无右孩的二叉树可以转变成一般树。根无右孩的二叉树可以转变成一般树。第四章第四章544.5.3 4.5.3 树和森林的遍历树和森林的遍历先序遍历：先序遍历：先访问根结点，然后先访问根结点，然后依次依次先序先序 遍历根的每棵子树；遍历根的每棵子树；后序遍历：后序遍历：先先依次依次后序遍历每棵子树，最后序遍历每棵子树，最 后访问根结点。后访问根结点。DABEC先序遍历次序：？先序遍历次序：？后序遍历次序：？后序遍历次序：？层次遍历

57、次序：？层次遍历次序：？注：注：二叉树二叉树树树转转先序遍历先序遍历先序遍历先序遍历对应对应后序遍历后序遍历中序遍历中序遍历对应对应层次遍历：层次遍历：ABCDEBDCEAABCED一、树的遍历一、树的遍历第四章第四章55二、森林的遍历二、森林的遍历l先序遍历森林：先序遍历森林：访问森林中每棵树的根结点；先序遍历森访问森林中每棵树的根结点；先序遍历森林中第一棵树的根结点的子树组成的森林；先序遍历除去林中第一棵树的根结点的子树组成的森林；先序遍历除去第一棵树之外其余的树组成的森林。第一棵树之外其余的树组成的森林。 对下图中森林进行先序遍历的序列为：对下图中森林进行先序遍历的序列为：ABCDEFG

58、HJIl中序遍历森林：中序遍历森林：中序访问森林中第一棵树的根结点的子树中序访问森林中第一棵树的根结点的子树组成的森林；访问第一棵树的根结点；中序遍历除去第一组成的森林；访问第一棵树的根结点；中序遍历除去第一棵树之外其余的树组成的森林；棵树之外其余的树组成的森林； 对下图中森林进行先序遍历的序列为：对下图中森林进行先序遍历的序列为：BCDAFEJHIG ABCDEFGHJI第四章第四章56问题问题：n n个学生成绩个学生成绩 a a1 1，a a2 2，,a,an n （百分制），现（百分制），现 要转换成五分制。要转换成五分制。 即即 a a1 1，a a2 2，,a,an n 分五类：分五

59、类： 一类：一类： 60 60 不及格不及格 二类：二类： 60 60， 70 70 ） 及格及格 三类：三类： 70 70， 80 80 ） 中等中等 四类：四类： 80 80， 90 90 ） 良好良好 五类：五类： 90 90 优秀优秀每类出现的概率：每类出现的概率： 分数分数 0 059 6059 6069 7069 7079 8079 8089 9089 90以上以上 概率概率 5% 15% 40% 30% 10%5% 15% 40% 30% 10%4.6 4.6 判定树和哈夫曼树判定树和哈夫曼树4.6.1 4.6.1 分类与判定树分类与判定树第四章第四章57若按顺序判，得下列判断过

60、程若按顺序判，得下列判断过程： 对对n n个数分类花费时间较多。个数分类花费时间较多。因为大多数元因为大多数元素属于中和良，这样大多数数据都得通过素属于中和良，这样大多数数据都得通过3 3至至4 4次判断，这样总的判断次数就多。次判断，这样总的判断次数就多。改改进进中中a 60a 70不及格不及格及格及格a 80a 90良良优优Y YN NN NY YN NY YY YN Na判定树判定树用于描用于描述分类过程的二叉述分类过程的二叉树，其中：每个非树，其中：每个非终端结点包含一个终端结点包含一个条件，对应一次比条件，对应一次比较；每个终端结点较；每个终端结点包含一个种类标记，包含一个种类标记，对应于一种分类结对应于一种分类结果。果。第四章第四章58510153040总的判