《二叉树的概念》ppt课件

《《二叉树的概念》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5-1二叉树主要内容5.1二叉树的概念5.2二叉树的周游5.3二叉树的存储结构5.4二叉搜索树5.5堆与优先队列5.6Huffman树及其应用5.7二叉树知识点总结5.1.1二叉树的定义及基本术语5.1.2满二叉树、完全二叉树、扩充二叉树5.1.3二叉树的主要性质5.1二叉树的概念二叉树二叉树的定义二叉树：是n(n≥0)个结点的有限集合。n=0的树称为空二叉树；n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。ABCDEIJGH根结点左子树右子树二叉树基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）②左子树和右子树次序不能颠倒。下

2、面是两棵不同的树:BACEDFGBACEDFG二叉树基本形态AABABABC空二叉树只有根结点的二叉树右子树为空左子树为空左、右子树均非空问：具有3个结点的二叉树可能有几种不同形态？有5种二叉树一般的树有几种？结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树个数。二叉树的基本术语叶子(leaf)：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点或内部结点。二叉树的基本术语路径与路径长度：路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。子女结点、父母结点、祖先、后继二叉树的基本术语结点的层次：根结点的层数为0，根的孩

3、子层数为1，依此类推。二叉树深度：树中结点的最大层次。二叉树的高度：层数最大的叶结点的层数加1。0123二叉树的基本术语满二叉树（考研大纲）在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。BACEDFGHIJKLMNO满二叉树特点（考研大纲）高度为k且有2k-1个结点的二叉树。每一层上的结点数都是最大结点数；所有的分支结点的度数都为2；叶子结点都在同一层次上。123114589121367101415满二叉树(教材)一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树,这样的二叉树称为满二叉树。(Afullbi

4、narytreeisatreeinwhicheverynodeotherthantheleaveshastwochildren)BACEDFGE完全二叉树如果一棵深度为k，有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树称为完全二叉树。（只有最下两层结点可以度小于2）BACEDFGHIJ完全二叉树特点叶子结点只可能在层次最大的两层上出现；前k-1层中的结点都是“满”的，且第k层的结点都集中在左边。123114589126710判断是否为完全二叉树1234567123456思考：满二叉树与完全二叉树的关系？扩充二叉树当二叉树里出现空

5、的子树时，就增加新的、特殊的结点——空树叶对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶对于原来二叉树的树叶，在它下面增加两个空树叶扩充的二叉树是满二叉树，新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数加1扩充二叉树扩充二叉树外部路径长度E从扩充的二叉树的根到每个外部结点的路径长度之和内部路径长度I扩充的二叉树里从根到每个内部结点的路径长度之和E和I两个量之间的关系为E=I+2n（证明见课本）扩充二叉树例如，在图5.3这个有10个内部结点的扩充二叉树里E=3+4+4+3+4+4+3+4+4+3+3=39I=0+1+2+3+2+3+1+2+3

6、+2=19E和I两个量之间的关系为E=I+2n。二叉树的主要性质书上列举的6个性质大都可以计算出来满二叉树定理：非空满二叉树树叶数等于其分支结点数加1。满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1。二叉树的主要性质任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设n1为二叉树中度为1的结点数。该二叉树的结点总数n为度分别为0，1，2的结点数之和，即n=n0+n1+n2（公式5.1）除根结点外，其余结点都有一条边进入，设边数为e，有n=e+1。由于这些边是由度为1或2的的结点发出的，所以又有e=n1+2n2，于是得n

7、=e+1=n1+2n2+1（公式5.2）由公式5.1和5.2得n0+n1+n2=n1+2n2+1，即n0=n2+1二叉树的主要性质在二叉树的第i层上至多有2i个结点(根为第0层，i≥0)。高度为k(深度为k-1)的二叉树至多有2k-1个结点有n个结点（n>0）的完全二叉树的高度为log2(n+1)(深度为log2(n+1)-1)二叉树性质对完全二叉树中编号为i的结点(0≤i≤n-1,n≥1,n为结点数)有：ABCDEHIJKFG012345678910完全二叉树（1）若i=0,则结点i是二叉树的根，无双亲。