数据结构-图PPT.ppt

《数据结构-图PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、树的定义和基本术语二叉树(BinaryTree)二叉树的存储结构遍历二叉树(BinaryTreeTraversal)线索化二叉树(ThreadedBinaryTree)树与森林(Tree&Forest)赫夫曼树(HuffmanTree)二叉树的计数第6章树和二叉树6.1树的定义和基本术语1.树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则:有一个特定的称之为根(root)的结点，它只有后继，但没有前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合本身又是一棵树，并且称之为根

2、的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数树的度——一棵树中最大的结点度数叶子(leaf)——度为0的结点分支结点(非终端结点)--度不为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子祖先—是从根到该结点所经分支上的所有结点子孙—以某结点为根的子树中的任一结点都称为该结点的~结点的层次(l

3、evel)——从根结点算起，根为第一层，它的孩子为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集合ABCDEFGHIJKLM堂兄弟：其双亲在同一层的结点互为堂兄弟有序树：如果将树中结点的各子树看成从左至右是有次序的，则该树为有序树。否则为无序树已知一棵树边的集合为{,,,,,,,,,,,,},请画出这棵树，并回答下列问题：1.哪个是根结点2.哪些是叶子结点3.哪个是结点G

4、的双亲4.哪些是结点G的祖先5.哪些是结点G的孩子6.哪些是结点E的子孙7.哪些是结点E的兄弟？哪些是结点F的兄弟？8.结点B和N的层次号分别是多少9.树的深度是多少10.以结点C为根的子树的深度是多少1.A2.DFJKLMN3.C4.AC5.JK6.IMN7.DGH8.259.510.3树的基本操作：p119树的建立和遍历——重点树的抽象数据类型6.2二叉树(BinaryTree)二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。特点：1）每个结点的度≤

5、2；2）是有序树A只有根结点的二叉树AB右子树为空AB左子树为空ABC左、右子树均非空空二叉树画出具有3个结点的二叉树的所有不同形态：共5种基本操作：p121~p123二叉树的建立和遍历二叉树的抽象数据类型性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i1)[证明用数学归纳法]性质2深度为k的二叉树最多有2k-1个结点。(k1)[证明用求等比级数前n项和的公式Sn=a1(1-qn)/(1-q)]性质3对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1二叉树的性质证明：若设度为1的结点有n1

6、个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1同理：三次树：n0=1+n2+2n3四次树：n0=1+n2+2n3+3n4…K次树：n0=1+n2+2n3+…+(k-1)nk定义1满二叉树(FullBinaryTree)定义2完全二叉树(CompleteBinaryTree)若设二叉树的深度为h，则共有h层。除第h层外，其它各层(1h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。123114589121367

7、101415123114589126710123456性质4具有n个结点的完全二叉树的深度为log2n+1证明：设完全二叉树的深度为k，则有2k-1-11,则i的双亲为i/2若

8、2*i≤n,则i的左孩子为2*i，否则无左孩子若2*