《二叉树的概念.ppt》由会员分享，可在线阅读，更多相关《二叉树的概念.ppt（28页珍藏版）》请在三一文库上搜索。
1、5-1 二叉树,主要内容,5.1 二叉树的概念 5.2 二叉树的周游 5.3 二叉树的存储结构 5.4 二叉搜索树 5.5 堆与优先队列 5.6 Huffman树及其应用 5.7 二叉树知识点总结,5.1.1 二叉树的定义及基本术语 5.1.2 满二叉树、 完全二叉树、 扩充二叉树 5.1.3 二叉树的主要性质,5.1 二叉树的概念,二叉树,二叉树的定义 二叉树：是n(n0)个结点的有限集合。n=0的树称为空二叉树；n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。,根结点,左子树,右子树,二叉树,基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点） 左子
2、树和右子树次序不能颠倒。下面是两棵不同的树:,二叉树,基本形态,A,空二叉树,只有根结点 的二叉树,右子树为空,左子树为空,左、右子树 均非空,问：具有3个结点的二叉树可能有几种不同形态？,有5种,二叉树,一般的树有几种？,结点：包含一个数据元素及若干指向其子树的分支。 结点的度：结点拥有的子树个数。,二叉树的基本术语,叶子(leaf) ：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点或内部结点。,二叉树的基本术语,路径与路径长度：路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。 子女结点、父母结点、祖先、后继,二叉树的基本术语,结点的层次：根结点的层数
3、为0，根的孩子层数为1，依此类推。 二叉树深度：树中结点的最大层次。 二叉树的高度：层数最大的叶结点的层数加1。,0,1,2,3,二叉树的基本术语,满二叉树（考研大纲）,在一棵二叉树中，如果所有分支结点都存在左子 树和右子树，并且所有叶子结点都在同一层上， 这样的二叉树称为满二叉树。,满二叉树特点（考研大纲）,高度为k且有2k-1个结点的二叉树。 每一层上的结点数都是最大结点数； 所有的分支结点的度数都为2； 叶子结点都在同一层次上。,满二叉树(教材),一棵二叉树的任何结点，或者是树叶，或者恰有两 棵非空子树,这样的二叉树称为满二叉树。 (A full binary tree is a tre
4、e in which every node other than the leaves has two children),B,A,C,E,D,F,G,E,完全二叉树,如果一棵深度为k，有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树称为完全二叉树。（只有最下两层结点可以度小于2）,完全二叉树特点,叶子结点只可能在层次最大的两层上出现； 前k-1层中的结点都是“满”的，且第 k 层的结点都集中在左边。,判断是否为完全二叉树,思考：满二叉树与完全二叉树的关系？,扩充二叉树,当二叉树里出现空的子树时，就增加新的、特殊的结点空树叶 对于原来二叉树里度数为1
5、的分支结点，在它下面增加一个空树叶 对于原来二叉树的树叶，在它下面增加两个空树叶 扩充的二叉树是满二叉树，新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数加1,扩充二叉树,扩充二叉树,外部路径长度E 从扩充的二叉树的根到每个外部结点的路径长度之和 内部路径长度I 扩充的二叉树里从根到每个内部结点的路径长度之和 E和I两个量之间的关系为 E=I+2n （证明见课本）,扩充二叉树,例如，在图5.3这个有10个内部结点的扩充二叉树里 E = 3 + 4 + 4 + 3 + 4 + 4 + 3 + 4 + 4 + 3 + 3= 39 I = 0 + 1 + 2 + 3 + 2 +
6、3 + 1 + 2 + 3 + 2 = 19 E和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。由于这些边
7、是由度为1或2的的结点发出的，所以又有e=n1+2n2，于是得 n=e+1=n1+2n2+1 （公式5.2） 由公式5.1和5.2得 n0+n1+n2=n1+2n2+1， 即 n0=n2+1,二叉树的主要性质,在二叉树的第i层上至多有2i个结点(根为第0层，i0)。 高度为k(深度为k-1)的二叉树至多有2k-1个结点 有n个结点（n0）的完全二叉树的高度为log2 (n+1) (深度为log2 (n+1) - 1),二叉树性质,对完全二叉树中编号为i的结点(0in-1, n1,n为结点数)有：,（1）若i=0,则结点i是二叉树的根，无双亲。 （2）若i0,则它的双亲结点的编号为(i-1)/2。当i为偶数时,其双亲结点的编号为i/2-1,它是右孩子结点,当i为奇数时,其双亲结点的编号为(i-1)/2,它是左孩子结点。,二叉树性质,(3)若编号为i的结点有左孩子结点,则左孩子结点的编号为2i+1；若编号为i的结点有右孩子结点,则右孩子结点的编号为(2i+2)。,二叉树性质,(4)若n为偶数,则每个分支结点都既有左孩子结点,也有右孩子结点；若n为奇数,则编号最大的分支结点(编号为(n-1)/2)只有左孩子结点,没有右孩子结点,其余分支结点都有左、右孩子结点。,二叉树性质,