二叉树课件.ppt

1二叉树刘 鹏山西农业大学信息学院2 2一、上节课知识回顾1、什么是树？ 树（Tree）是n（n0）个结点的有限集。在任意一棵非空树中：（1）有且只有一个特定的称为根（Root）的结点；（2）当n1时，其余结点可分为m（m0）个互不相交的有限集T1，T2，TM，其中每个集合本身又是一棵树，并且称为根的子树（SubTree）。根叶子结点3 3二、二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 1）二叉树的结构最简单，规律性最强； 2）可以证明，所有树都能转为唯一对应的二叉树，不失一般性。4 4二、二叉树2、二叉树的定义 二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。根叶子结点左子树左子树右子树右子树5 5二、二叉树3、逻辑结构： 一对二（1：2） 4、基本特征: 1）每个结点最多只有两棵子树（不存在度大于2的结点）； 2）左子树和右子树次序不能颠倒（有序树）。5、基本形态： 6 6二、二叉树6、二叉树的性质 (3+2)12i-11）讨论1：第i层的结点数至多是多少？（利用二进制性质可轻松求出）性质性质1: 1: 在二叉树的第在二叉树的第i i层上至多有层上至多有2i-12i-1个结点（个结点（i0i0）提问：第i层上至少有 个结点？7 7二、二叉树l2）讨论2：深度为k的二叉树，至多有多少个结点？（利用二进制性质可轻松求出）k性质性质2: 2: 深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点（个结点（k0k0）。）。l提问：深度为k时至少有 个结点？2k-18 8二、二叉树l3）讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？性质性质3: 3: 对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，个，则叶子数（则叶子数（n n0 0）必定为）必定为n n2 21 1 （即（即n n0 0=n=n2 2+1+1）9 9二、二叉树7、满二叉树l一棵深度为k 且有2k -1个结点的二叉树。（特点：每层都“充满”了结点）AOBCGEKDJFIHNML深度为深度为4 4的满二叉树的满二叉树1010二、二叉树8、完全二叉树l深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。深度为深度为4 4的的完全二叉树完全二叉树ABCGEIDHFJ11 11二、二叉树l对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：l性质4: 具有n个结点的完全二叉树的深度必为log2n1l性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i1；其双亲的编号必为i/2（i1 时为根,除外）。 1212二、二叉树9、课堂讨论：l1）二叉树是不是树的特殊情况？答：不是！虽然二叉树也属于一种树结构，但它答：不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树，并非一般树的特例。是另外单独定义的一种树，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。能随意颠倒。1313二、二叉树9、课堂讨论：l2）满二叉树和完全二叉树有什么区别？ 答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。l3）为什么要研究满二叉树和完全二叉树这两种特殊形式？答：因为只有这两种形式可以实现顺序存储！1414三、习题1、树中各结点的度的最大值称为树的 。) 高度 ) 层次 ) 深度 ) 度2、深度为k 的二叉树的结点总数，最多为 个。)k-1 ) log2k ) k )k1515三、习题l3. 深度为9的二叉树中至少有 个结点。)29 )28 )9 )291l4、设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。1616四、总结1、二叉树的定义2、满二叉树和完全二叉树的概念3、二叉树的5种性质1717五、预习1、二叉树的存储结构2、二叉树的遍历以上课件内容及习题答案可到http:/下载1818