数据结构 课件 二叉树

《数据结构 课件 二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、树与二叉树软件学院王建文树的用处举例线性表适合表示一个顺序序列(e0,e1,e2,…,en-1)Daysofweek.Monthsinayear.Studentsinthisclass.树适合表示具有层次结构的数据族谱(课本176页),公司组织结构等ExampleTreegreatgrandchildofrootgrandchildrenofrootchildrenofrootPresidentVP1VP2VP3Manager1Manager2ManagerManagerWorkerBeeroot搜索树中文输入法的实现原理是字符编码与字符或词组之间

2、的映射形成一张码表，如：zhang，张;wang,王;zhao，赵;li，李;laoshi，老师;线性表存储，顺序地查找，时间复杂度O（n）广义表存储,逐层地查找，时间复杂度O（h）树存储,逐层地查找，时间复杂度O（h），大约为O(logn)第五章树☞树和森林的概念二叉树(BinaryTree)二叉树的表示二叉树遍历(BinaryTreeTraversal)线索化二叉树(ThreadedBinaryTree)堆(Heap)树与森林(Tree&Forest)二叉树的计数霍夫曼树(HuffmanTree)树和森林的概念树的定义树是由n(n0)个结点组

3、成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。A只有根结点的树ABCDEFGHIJKLM有子树的树根子树结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点子女(child)结点双亲(parent)结点兄弟(sibling)结点祖先(an

4、cestor)结点子孙(descendant)结点结点所处层次(level)树的高度(depth)树的度(degree)有序树无序树森林12344树的术语基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~基本术语兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数结点的层次(level)——从根结点算起，根为第一层，它的孩子

5、为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先树的表示方法见课本178-179二叉树的五种不同形态LLRR二叉树(BinaryTree)二叉树的定义一棵二叉树是结点的一个有限集合，该

6、集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树的性质性质1若二叉树结点的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i≥1)[证明用数学归纳法]性质2深度为k的二叉树最少有k个结点，最多有2k-1个结点。(k≥1)因为每一层最少要有1个结点，因此，最少结点数为k。最多结点个数借助性质1：用求等比级数前k项和的公式20+21+22+…+2k-1=2k-1性质3对任何一棵二叉树，如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0＝n2＋1若设度为1的结点有n1个，总结点数为n，总边数为e

7、，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1例：已知叶子数为20，10个结点有一个左孩子，15个结点有一个右孩子，求该二叉树的总结点数。解：n0=20n1=10+15=25由于n0=n2+1则：n2=n0–1=19∴n=n0+n1+n2=20+25+19=64满二叉树定义：满二叉树是满足如下条件的二叉树：①任一非叶子结点均有两个孩子；②对于二叉树的任一层，若该层上有一个结点有孩子，则该层上所有结点均有孩子。特点：满二叉树的每层都有最大结点数。MNABCDEF

8、GJHIKLP两种特殊的二叉树完全二叉树定义：在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。特点：①叶子结