第6章 树和二叉树(新) (2)

1第六章树和二叉树【学习目标】1．领会树和二叉树的类型定义，理解树和二叉树的结构差别。2．熟记二叉树的主要特性，并掌握它们的证明方法。3．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。4．理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5．熟练掌握二叉树和树的各种存储结构及其建立的算法。6．学会编写实现树的各种操作的算法。7．了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。课前索引2第六章树和二叉树【重点和难点】二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。【知识点】树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码。课前索引（续）3第六章数和二叉树【学习指南】本章是整个课程的第二个学习重点，也是整个课程中的一大难点。在本章的学习过程中主要应该学会如何根据二叉树和树的结构及其操作的递归定义编写递归算法。本章必须完成的算法设计题为:6.41,6.43,6.45,6.47,6.50,6.59,6.68和6.66。课前索引（续）4第六章树和二叉树【课前思考】1.你见过家族谱系图吗？试以图形表示从你的祖父起的家族成员关系。你一定可以画出如下类似的图形或者用如右下的图形表明你的祖先。课前索引（续）56.1树的定义和基本术语6.2二叉树定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码第六章数和二叉树66.1树的定义和基本术语树是一类重要的非线性数据结构，是以分支关系定义的层次结构。一、树的定义：1．树(Tree)是n(n≥0)个结点的有限集T，如果n=0，称为空树；否则：有且仅有一个称为树的根(root)的结点。其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。ABCDEFGHIJKLM72、树的表示形式-—是一颗倒立的树ACBGFEHIJDMKLAT1T2T3只含有根结点的树含有子树T1、T2和T3的树对于非空树，其特点：•树中至少有一个结点——根•树中各子树是互不相交的集合8树的其它表示方式ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示ABFEKLGCDHMIJ嵌套集合(A(B(E(K,L),F),C(G),D(H(M),I,J)))广义表9树的基本术语10二、树的基本术语结点(node)—表示树中的元素，包括数据项及若干指向其子树的分支结点的度—结点拥有的子树个数叶子—度为0的结点树的度—一棵树中最大的结点度数(子树数）孩子—结点的子树的根称为该结点的孩子（结点）双亲—孩子结点的上一层结点叫该结点的~(父结点)兄弟——同一双亲的孩子互称兄弟（结点）结点的层次——从根结点算起，根为第一层，它的孩子为第二层……ABCDEFGHIJKLM树的示意图11二、树的基本术语树的深度（树高）—树中结点的最大层次数堂兄弟--其双亲在同一层的结点互称为堂兄弟。结点的祖先—从根结点到该结点所经分支上的所有结点结点的子孙—以某结点为根的子树中的任一结点都称之为该结点的子孙有序树和无序树：树中各结点的子树从左到右有次序（不能互换），称该树为有序树，否则为无序树。（有序树：第一个孩子、第二个孩子…）森林—m(m0)棵互不相交的树构成的集合ABCDEFGHIJKLM树的示意图12就逻辑结构而言，可以森林和树相互递归的定义来描述树：任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF13(从根结点到结点的)路径：结点的层次:树的深度：由从根结点到该结点所经分支和结点构成。ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次注意：树的叶子结点不一定都在树的最大层次上14线性结构（1:1）树型结构（1:n）第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、一个或多个后继)对比线性结构和树型结构的结构特点(a1,a2,a3,…an-2,an-1,an)ABCDEFGHIJMKL15数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：三、树的抽象数据类型定义ADTTree{基本操作：……}ADTTree树的结构定义+树的基本操作=抽象数据类型树的定义16基本操作：查找类插入类删除类17Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历18InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树19ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树206.2二叉树的类型定义21或：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树6.2.1二叉树的定义一、二叉树定义：度不大于2且有左右之分的树(有序树)（即树中每个结点最多只有两棵子树的有序树）（区别于度为2的树或度不大于2的树）。二叉树的递归定义：其左右子树又都是二叉树。22二叉树的基本特征1、每个结点最多只有两棵子树。2、子树有左右之分，其次序不能任意颠倒，是一个有序树。23二、二叉树的五种基本形态（概括性）N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树定义：度不大于2（每个结点最多只有两棵子树）的有序树24思考题：3个结点的二叉树具有几种基本形态？对比：3个结点的树具有几种基本形态？25三、二叉树的主要基本操作：查找类插入类删除类26Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());查找类27InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入类28ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);删除类296.2.2二叉树的重要特性30在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设对所有的j，1≤ji，命题成立；即第j层上至多有2j-1个结点。因二叉树上每个结点至多有两棵子树，则第i层的结点数=2(i-1)-12=2i-1。性质1：证明j=i时命题成立12345768第i-1层的结点数31深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=1*（1-2k）/1-2=2k-1性质2：思考题：深度为h的k叉树最多有多少个结点？hiik1111kkh=32对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2…①再看二叉树中的分支数。除了根结点外，其余结点都有一个分支进入，设B为分支总数，则有：B=n-1…②由于这些分支是由度为1或为2的结点射出的，所以又有：B=n1+2n2+0*n0…③有从而有：n0+n1+n2–1=n1+2n2由此，n0=n2+1。性质3：12345633利用结点总数与分支总数求解问题思考题：有n个结点的树，仅有度为0的叶子结点和度为k的结点,问该树含有多少叶子结点？结点总数n=n0+nk…①分支总数：叶子数目=（n(k-1)+1）/k从入支角度（从下向上）看，有b=n-1…②从出支角度（从上向下）看，有b=nk*k…③34两类特殊的二叉树：满二叉树：指的是深度为k且含有2k–1个结点的二叉树。123456789101112131415特点：每一层上的结点数都是最大结点数二叉树性质1：第i层上至多有2i-1个结点。二叉树性质2：深度为k的二叉树至多有2k-1个结点。35完全二叉树：若一颗二叉树中所含的n个结点与满二叉树中编号为1至n的结点一一对应(编号和位置一一对应)。123456789101112131415abcdefghij特点1.叶子结点只可能在层次最大的两层上出现.2.对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或l+1kl361231145891213671014151231145891267101234567123456法一：若二叉树中最多只有最下两层有度小于2的结点,且最下层的结点都依次排列在最左边,则称此二叉树为完全二叉树法二：深度为k二叉树,若第1到第k-1层为深度为k-1的满二叉树,第k层的结点都依次排列在最左边,则称此二叉树为完全二叉树。如何判别完全二叉树？定义37具有n个结点的完全二叉树的深度为log2n+1。证明：设完全二叉树的深度为k则根据第二条性质得2k-1-1n≤2k-1或2k-1≤n2k两边取对数得：k-1≤log2nkk≤log2n+1k+1因为k只能是整数，因此，k=log2n+1性质4：深度为k的二叉树上至多含2k-1个结点（k≥1）。123114589126710特点38性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲；否则，编号为i/2的结点为其双亲结点；(2)若2in，则该结点无左孩子LCHILD，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点RCHILD，否则，编号为2i+1的结点为其右孩子结点。39示意图2i2i+1i2i+22i+3i+1[i/2]j层12jij+1层假设编号为i的结点处在第j层的最左边。∵前j-1层为满二叉树，前j-1层共有2j-1-1个结点，最后一个结点序号:2j-1-1，则第j层最左边的结点为第2j-1个(即i=2j-1)。同理，∵有第j+1层，故前j层为满二叉树，前j层共有2j-1个结点，最后一个结点序号：2j-1，则第j+1层最左边的结点为第2j个。i2