树与二叉树课件.ppt

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

1、树有关树的术语树的存储结构二叉树二叉树的性质满二叉树与完全二叉树二叉树的存储结构树与二叉树的关系二叉树的遍历穿线二叉树表达式的线性化树（非线性数据结构）树的形式化定义：树(Tree)是由一个或多个结点组成的有限集合T，其中有一个特定的称为根的结点；其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm，每一个集合本身又是一棵树，且称为根的子树。树的特点：仅有一个根结点，结点间有明显的层次结构关系。ACGT2BELKT1FDHIT3JM现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次

2、结构、人类的家族血缘关系等。计算机软件技术中，能用树的结构表示的例子：操作系统中的多级文件目录结构，高级语言中源程序的语法结构等。有关树的基本术语:结点（Node）：树中的元素，包含数据项及若干指向其子树的分支。结点的度（Degree）：结点拥有的子树数。结点的层次：从根结点开始算起，根为第一层.叶子（Leaf）：度为零的结点，也称端结点。孩子（Child）：结点子树的根称为该结点的孩子结点。双亲（Parent）：孩子结点的上层结点，称为这些结点的双亲。兄弟（Sibling）：同一双亲的孩子。深度（Depth

3、)：树中结点的最大层次数。森林（Forest）：M棵互不相交的树的集合。ACGT2BELKT1FDHIT3JMCGT2BELKT1FDHIT3JM树的存储结构树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理可以用树来表示算术表达式。二叉树是一种重要的树形结构，其结构定义为：二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为根的左子树和右子树的、互不相交的二叉树组成。二叉树

4、(BinaryTree)的定义二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。二叉树的五种基本形态空二叉树仅有根结点右子树为空左子树为空左右子树均非空要点：二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。二叉树的第i层上至多有2i-1（i1）个结点。深度为m的二叉树中至多含有2m-1个结点。若在任意一棵二叉树中，有n0个叶子结

5、点，有n2个度为2的结点，则：n0=n2+1ABCDEF二叉树的性质性质1：二叉树的第i层上至多有2i-1（i1）个结点。证明：根据二叉树的特点，结论是显然的。性质2：深度为m的二叉树中至多含有2m-1个结点。证明：深度为m的二叉树最多有m层，根据性质1，只要将第1层到第m层的最大结点数相加，就可得到整个二叉树中结点的最大值。21-1+22-1+…+2m-1=2m-1性质3：度为0的结点总比度为2的结点多一个。设：有n0个叶子结点，有n1个度为1的结点，有n2个度为2的结点，则二叉树中结点总数为：n=n0+

6、n1+n2设所有进入分支的总数为m,则总的结点个数为：n=m+1总的射出分支与总的进入分支数相等：m=n1+2n2因此：n0+n1+n2=n1+2n2+1所以：n0=n2+1ABCDEF423156789101112131415ABCDEFABCDEF423156789101112131415用归纳法证明：i=1，则结点数=20=1为根结点。若已知i-1层上结点数至多有2(i-1)-1=2i-2个，由于二叉树每个结点度数最大为2，因此第i层上结点数最多为第i-1层上结点数的2倍，即2×2i-2=2i-1。满二

7、叉树：深度为k且含有2k-1个结点的二叉树。特点：每一层上的结点数都是最大结点数。完全二叉树:指深度为k的，有n个结点的，且每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。423156789101112131415423156789101112完全二叉树423156789101112非完全二叉树二叉树的存储结构(2)链式存储结构T[16]若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。11ABCFED●●●●●●●●●1248910563712131415(1)顺序存储结构(

8、1)顺序存储结构2h-1=24-1=15用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。(2)链式存储结构：每个结点由数据域、左指针域和右指针域组成。rchildDatalchild^ADB^C^^E^^F^图为一般二叉树的二叉链表结