数据结构课件代码第4章树和二叉树-35-1

1、第4章 树和二叉树张成文张成文北京邮电大学计算机学院北京邮电大学计算机学院 树的定义与基本术语树的定义与基本术语1.1.定义定义: : 树树是是n(n0)n(n0)个结点的有限集合个结点的有限集合t t。当。当n=0n=0时时, ,称为空树称为空树; ;当当n0n0时时, ,该集合满足如下条件该集合满足如下条件: : (1) (1) 其中必有一个称为根其中必有一个称为根(root)(root)的特定结点的特定结点, ,它没它没有直接前驱有直接前驱, ,但有零个或多个直接后继。但有零个或多个直接后继。 (2) (2) 其余其余n-1n-1个结点可以划分成个结点可以划分成m(m0)m(m0)个互不

2、相个互不相交的有限集交的有限集t t1 1,t,t2 2,t,t3 3, ,t,tm m, ,其中其中t ti i又是一棵树又是一棵树, ,称为称为根根rootroot的子树。每棵子树的根结点有且仅有一个直的子树。每棵子树的根结点有且仅有一个直接前驱接前驱, ,但有零个或多个直接后继。但有零个或多个直接后继。 一、树一、树(tree)的基本概念的基本概念:abcdefghijmkla( b(e, f(k, l), c(g), d(h, i, j(m) )t1t3t2树根例如例如: : (1). 树型图示树型图示 (2).嵌套集合嵌套集合 (3).凹入凹入(书目书目) (4). 广义表广义表(用

3、根作为表的名字写在表的左边用根作为表的名字写在表的左边)abcdefghijklma - b - e - k - l - f - c - g - d - h - m - i - j -2. 树的表示法树的表示法:线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后最后一个一个数据元素数据元素 (无后继无后继)多个多个叶子结点叶子结点 ( (无后继无后继) )其它数据元素其它数据元素 ( (一个前驱、一个前驱、 一个一个后继后继) )其它数据元素其它数据元素 ( (一个前驱、一个前驱、 多个多个后继后继) )对比对比树

4、型结构树型结构和和线性结构线性结构的结构特点的结构特点结点结点(node):树的度树的度: :叶子结点叶子结点(leaf) :分支结点分支结点: :数据元素数据元素+ +若干指向子树的分支若干指向子树的分支树各结点的度的最大值树各结点的度的最大值度为零的结点度为零的结点度大于零的结点度大于零的结点dhijm3.3.树的相关术语树的相关术语结点的度结点的度(degree):结点拥有的子树数结点拥有的子树数结点的层次结点的层次: (level)假设根结点的层次为假设根结点的层次为1 1, ,第第l 层的结点的子树根结层的结点的子树根结点的层次为点的层次为l+1树的深度树的深度(depth):叶子结

5、点所在的最大层次叶子结点所在的最大层次分支分支(branch):表示数据元素与它的子树的关系表示数据元素与它的子树的关系路径路径(path):常用家族树的术语表示结点关系常用家族树的术语表示结点关系孩子孩子(child) 结点结点双亲双亲(parent)结点结点 兄弟兄弟结点结点由根到该结点所经的分支和结点构成由根到该结点所经的分支和结点构成abcdefghijmkl树的结点数树的结点数n和分支数和分支数b的关系是的关系是: b=n-1任何一棵非空树是一个二元组任何一棵非空树是一个二元组 tree = (root,f)其中其中:root 被称为根结点被称为根结点 f 被称为子树森林被称为子树森

6、林森林森林(forest):是是m(m0)棵互不棵互不相交的树的集合相交的树的集合arootbcdefghijmklf二叉树二叉树1 二叉树的定义与基本操作二叉树的定义与基本操作定义定义： 满足以下两个条件的树称做二叉树满足以下两个条件的树称做二叉树(binary tree): （1）每个结点的度都不大于）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。）每个结点的孩子结点次序不能任意颠倒。 二叉树或为空树空树, 或是由一个根结点根结点加上两两棵棵分别称为左子树左子树和右子树右子树的、互不交的互不交的二叉二叉树树组成。注意注意:二叉树是有序树有序树,它的子树有左右之分。二叉树

7、的度数不超过二二叉树的度数不超过二,但度数不超过二的树但度数不超过二的树未必是二叉树。未必是二叉树。abcdefghk根结点左子树左子树右子树右子树二叉树的五种基本形态二叉树的五种基本形态:n空树空树只含根结点只含根结点nnnlrr右子树为空树右子树为空树l左子树为空树左子树为空树左右子左右子树均非树均非空树空树用归纳法证明用归纳法证明: 归纳基归纳基: 归纳假设归纳假设: 归纳证明归纳证明:i = 1 层时层时,只有一个根结点只有一个根结点: 2i-1 = 20 = 1 命题成立命题成立;假设假设 i-1 命题成立命题成立,即即: 第第i-1层至多有结点层至多有结点= 2i-1-1 = 2i

8、-2 个个; 二叉树每个结点至多有两棵子树二叉树每个结点至多有两棵子树,则则第第i 层至多有结点层至多有结点 = 2i-2 2 = 2i-1 个。个。2 二叉树的重要特性二叉树的重要特性性质性质1 :二叉树第二叉树第 i 层上至多有层上至多有2i-1 个结点。个结点。证明证明: 基于性质基于性质1, 深度为深度为 k 的二叉树上的结点总数的的二叉树上的结点总数的最大值是将二叉树每层上结点的最大值相加，所以最大值是将二叉树每层上结点的最大值相加，所以深度为深度为 k 的二叉树上含的二叉树上含 结点数至多为：结点数至多为： 20+21+ +2k-1 = 2k-1 性质性质 2 : 深度为深度为 k

9、 的二叉树上至多含的二叉树上至多含 2k-1 个结点个结点(k1)。证明证明:设设 二叉树上结点总数：二叉树上结点总数： n = n0 + n1 + n2再根据树的性质：再根据树的性质： b = n-1 = n0 + n1 + n2 - 1由有二叉树分支总数：由有二叉树分支总数： b = n1+2n2两式右边相等得两式右边相等得: n0 = n2 + 1 。性质性质 3 : 对任何一棵二叉树对任何一棵二叉树,若它含有若它含有n0 个叶子结点、个叶子结点、n2 个个度为度为 2 的结点的结点, 则必存在关系式则必存在关系式:n0 = n2+1。也可以用归纳法证明也可以用归纳法证明满二叉树 在一个

10、二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。 即如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。 完全二叉树如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。完全二叉树完全二叉树: 树中所含的树中所含的 n 个结点和满二叉树中个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应。一一对应。abcdefghij可用一维数组存储可用一维数组存储: btn 顺序顺序: 完全二叉树中将编号完全二叉树中将编号i的结点存在的结点存

11、在bti中。中。 一、一、 二叉树的顺序存储二叉树的顺序存储 3 二叉树的存储结构二叉树的存储结构 二叉树是非线性结构，结点最多有两个后继。二叉树是非线性结构，结点最多有两个后继。存储结构有两种：存储结构有两种：顺序存储顺序存储结构和结构和链式存储链式存储结构。结构。abcdefghijkla b c d e fg h ijk l例如例如: a b d c e f1 1 2 3 2 3 4 5 64 5 6 7 8 9 7 8 9 10 1110 11 12 13 1412 13 14abcdef2511437 一般二叉树，一般二叉树，按完全二叉树结点的编号存放按完全二叉树结点的编号存放, 无

12、结点的单元存放空元素。无结点的单元存放空元素。会造成空间浪费会造成空间浪费二、二叉树的链式存储表示二、二叉树的链式存储表示 二叉链表二叉链表 每个结点包括两个指针域：指向左孩子和右孩子每个结点包括两个指针域：指向左孩子和右孩子lchilddatarchilddabcefga bcd e f g 二叉树二叉树t t二叉链表二叉链表结点结构结点结构:lchild data rchild结点结构结点结构:二叉链表结点的结构用二叉链表结点的结构用c语言描述为语言描述为 ： typedef struct nodetypedef struct node datatype data; datatype da

13、ta; strct node strct node * * lchild; lchild; struct node struct node * * rchild; rchild;bitnode, bitnode, * *bitreebitree; 一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法描述三、算法描述二叉树的遍历二叉树的遍历 “遍历遍历”: 沿某条搜索路径沿某条搜索路径巡访巡访二叉树的结点二叉树的结点, 使每个结点使每个结点均被访问一次均被访问一次, 且且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出“访问访问”: 的含义很广的含义很广, 如如

14、:输出结点信息等。输出结点信息等。 “遍历遍历”是任何类型均有的操作是任何类型均有的操作, 对线性结对线性结构而言构而言, 只有一条搜索路径只有一条搜索路径(因为每个结点只因为每个结点只有一个后继有一个后继), 故不需要另加讨论故不需要另加讨论. 二叉树是非线性结构二叉树是非线性结构, 每个结点有两个后每个结点有两个后继继, 则存在按什么样的则存在按什么样的搜索路径搜索路径遍历的问题。遍历的问题。 “二叉树二叉树”由三部分组成：由三部分组成：根结点、左根结点、左子树和右子树子树和右子树。若能依次遍历这三部分，就。若能依次遍历这三部分，就遍历了整个二叉树。遍历了整个二叉树。用用l、d、r表示表示

15、遍历左子树遍历左子树、访问根结访问根结点点、遍历右子树遍历右子树，则有，则有8种遍历二叉树方案：种遍历二叉树方案：先左后右：先左后右：dlr、ldr、lrd、按层次、按层次先右后左：先右后左：drl、rdl、rld 、按层次、按层次二、二、先左后右先左后右的遍历算法的遍历算法先先序的遍历算法序的遍历算法dlr中中序的遍历算法序的遍历算法ldr后后序的遍历算法序的遍历算法lrddlr 若二叉树为空树若二叉树为空树,则空操作则空操作;否则否则,(1)访问根结点访问根结点;(2)先序遍历左子树先序遍历左子树;(3)先序遍历右子树。先序遍历右子树。先序的遍历算法先序的遍历算法:dlr 若二叉树为空树若

16、二叉树为空树,则空操作则空操作;否则否则,(1)中序遍历左子树中序遍历左子树;(2)访问根结点访问根结点;(3)中序遍历右子树。中序遍历右子树。中序的遍历算法中序的遍历算法:dlr 若二叉树为空树若二叉树为空树,则空操作则空操作;否则否则,(1)后序遍历左子树后序遍历左子树;(2)后序遍历右子树后序遍历右子树;(3)访问根结点。访问根结点。后序的遍历算法后序的遍历算法:dlrabcdefghij例如:先序序列先序序列: a b d h i e j c f g中序序列中序序列: h d i b j e a f c g后序序列后序序列: h i d j e b f g c a三、算法描述三、算法描

17、述1) 1) 先序遍历先序遍历void void preorderpreorder(bitree bt) (bitree bt) / /* *先序遍历先序遍历, ,根指针为根指针为btbt的二叉树的二叉树* */ / if(bt!=null) if(bt!=null) visit(bt-data); visit(bt-data); /访问根结点访问根结点 preorderpreorder(bt-lchild); (bt-lchild); /遍历左子树遍历左子树 preorderpreorder(bt-rchild); (bt-rchild); /遍历右子树遍历右子树 2) 2) 中序遍历中序遍

18、历void void inorderinorder(bitree bt) (bitree bt) / /* *中序遍历根指针为中序遍历根指针为btbt的二叉树的二叉树* */ / if(bt!=null) if(bt!=null) inorderinorder(bt-lchild); (bt-lchild); /遍历左子树遍历左子树visit(bt-data); visit(bt-data); /访问根结点访问根结点inorderinorder(bt-rchild); (bt-rchild); /遍历右子树遍历右子树 3) 3) 后序遍历后序遍历void void postorderpostorder(bitree bt