数据结构与算法设计PPT (22).pdf

《数据结构与算法设计PPT (22).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (22).pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章 树6.2 二叉树及其性质二叉树定义(Binary Tree)二叉树是n个（n=0）结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树是一个递归结构二叉树定义(Binary Tree)二叉树可以为空，空二叉树二叉树的度为2非空的二叉树至少会有一个根结点，除了根之外分成两个子树，以作孩子为根的左子树，以有孩子为根的右子树左右子树是有序的，不能随意交换二叉树的五种基本形态二叉树应用算数表达式 二叉树可以表示算数表达式 叶子结点是操作数，分支结点是运算符 表达式(2 (a-1)+(3 b)的二叉树表示形式：+-2 2a a1 1

2、3 3b b决策树 内部结点：问题，答案只有两种是或者否 叶子结点：结论电源是否打开?打印纸是否装好USB线连接?打开电源装入打印纸联系客服连接USB线YesYesNoNoYesNo性质1 若二叉树的层次从0开始,则在二叉树的第i层最多有2i 个结点。(i 0)证明用数学归纳法性质2 高度为k 的二叉树最多有 2k+1-1个结点。(k-1)证明用求等比级数前k项和的公式性质3 对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0n21二叉树的性质性质3 对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0n21二叉树的性质证明：令n和B表示T

3、中结点和分支的总数。令n0，n1，n2分别代表度为0、度为1和度为2的结点个数（1）B+1=n 且 B=n1+2n2所以 n=n1+2n2+1（2）n=n0+n1+n2n1+2n2+1=n0+n1+n2所以n0=n2+1满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树；K=3的满二叉树满二叉树123456789101112131415若设二叉树的高度为h，则共有h+1层。除第h 层外，其它各层(0 h-1)的结点数都达到最大个数，第h 层从右向左连续缺若干结点，这就是完全二叉树。完全二叉树123456712345123456Xv性质4 具有n个结点的完全二叉树的高度为 log2(n+1)-1证明：设完全二叉树的高度为h，则有2h-1 n 2h+1-1 2h n+1 2h+1取对数h 0,则i的双亲为(i-1)/2n若2*i+1 n,则i的左子女为2*i+1若2*i+2 0,则i的双亲为(i-1)/2n若2*i+1 n,则i的左子女为2*i+1若2*i+2 n,则i的右子女为2*i+2n若i为偶数,且i!=0,则其左兄弟为i-1若i为奇数,且i!=n-1,则其右兄弟为i+1ni所在层次为 log2(i+1)二叉树的性质01234567891011121314