二叉树及其应用课件

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

1、☞7.1二叉树的概念7.2二叉树的存储7.3二叉树的遍历7.4线索二叉树7.5二叉树的应用1—基本算法7.6二叉树的应用2—哈夫曼树7.7二叉树的应用3—二叉排序树7.8二叉树的应用3—堆和堆排序第7章二叉树及其应用☞7.1.1什么是二叉树7.1.2特殊的二叉树7.1.3二叉树的性质7.1二叉树的概念二叉树的定义二叉树是由n(n≥0)个结点组成的有限集合，其中：①当n＝0时为空树；②当n＞0时，有且仅有一个特定的结点，称为二叉树的根，其余结点可分为2个互不相交的子集，其中每一个子集本身又是一棵二叉树，分

2、别称为左子树和右子树。ABCDEFGHIJ二叉树的形态空树单结点二叉树AØ右子树不空的二叉树Ø左子树不空的二叉树左右子树均不空的二叉树二叉树的基本术语：父结点：若一个结点有子树，则该结点为父结点（也称双亲结点）。孩子结点：若某结点有左子树，则其左子树的根为该结点的左孩子；若其有右子树，则其右子树的根为该结点的右孩子。ABCDEFGHIJ结点A为结点B、C的父结点B为A的左孩子，C是A的右孩子；兄弟结点：同一个结点的孩子。延伸父子关系可得到祖先结点和后代结点关系。层次：根结点的层次为1，其余结点的层次是其

3、父结点的层次加1。高度（深度）：二叉树中结点的最大层次数。ABCDEFGHIJ该二叉树的深度为4；度：一个结点的孩子数目是这个结点的度。叶子结点：度为0的结点。二叉树的度：二叉树中结点的最大的度。ABCDEFGHIJA、B、C的度均为2；E、F、G的度均为1；D、H、I、J的度为0.注意：对于结点数>1的二叉树，有且仅有一个结点为二叉树的根，其余结点均为孩子结点，且有左右之分——左孩子、右孩子。例：具有三个结点的二叉树ABCBACABCABCCAB总结：二叉树的逻辑结构（1）二叉树中任一结点（除根结点外

4、）只有一个父结点；（2）二叉树中任一结点（除叶子结点外）最多有2个孩子结点；（3）结点间为非线性关系。7.1.1什么是二叉树☞7.1.2两种特殊的二叉树7.1.3二叉树的性质7.1二叉树的概念满二叉树定义：满二叉树是满足如下条件的二叉树：①任一非叶子结点均有两个孩子；②对于二叉树的任一层，若该层上有一个结点有孩子，则该层上所有结点均有孩子。特点：满二叉树的每层都有最大结点数。MNABCDEFGJHIKLP1234567问题：可不可以说，所有非叶子结点均有两个孩子的二叉树为满二叉树？完全二叉树定义：在满二

5、叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。特点：①叶子结点只可能在层次最大的两层上出现；②满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。ABCDEFGJHIKL例：满二叉树和完全二叉树1231145891213671014151231145891267101234567.1.1什么是二叉树7.1.2两种特殊的二叉树☞7.1.3二叉树的性质7.1二叉树的概念性质1：在二叉树的第i层上至多有2i-1个结点（i>0）证明：用数学归纳法。归纳基础：当i=1时，整个二叉树只有一根结点，此时

6、2i-1=20=1，结论成立。归纳假设：假设i=k时结论成立，即第k层上结点总数最多为2k-1个。现证明当i=k+1时，结论成立：因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-1，故结论成立。性质2：深度为k的二叉树至多有2k-1个结点（k>0）证明：因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为故结论成立。深度为k的满二叉树有2k-1个结点；或者说，深度为k且有2

7、k-1个结点的二叉树为满二叉树。性质3：对任一棵非空的二叉树T，如果其叶子数为n0，度为2的结点数为n2，则：n0=n2+1证明：设总结点数为n，度为1的结点数为n1.则：n=n1+n2+n0又∵度为1的结点有1个孩子，度为2的结点有2个孩子.故二叉树中孩子结点的总数为n1+2n2二叉树中只有根结点不是任何结点的孩子∴总结点数n=n1+2n2+1即：n1+2n2+1=n1+n2+n0∴n0=n2+1例：已知叶子数为20，10个结点有一个左孩子，15个结点有一个右孩子，求该二叉树的总结点数。解：n0=20

8、n1=10+15=25由于n0=n2+1则：n2=n0–1=19∴n=n0+n1+n2=20+25+19=64性质4：有n个结点的完全二叉树(n>0)的高度为+1证明：假设一棵高度为h的二叉树有n个结点，根据性质2，有n≤2h－1从而h≥log2(n+1)所以h≥+1性质5：若对满二叉树或完全二叉树按照“从上到下，每层从左到右，根结点编号为1”的方式编号，则编号为i的结点，它的两个孩子结点的编号分别为2i和2i+1，它的父结点的编号为i/2