[课件资料]第五章 树

第五章树,编程任务哈夫曼树在通信编码中的应用,问题描述：发电报时，电文中的字符都必须转换成0、1序列，例：A用000表示，B用001表示。这是编码。类似地，在接收端要解码。同一份电文中，不同字符出现的频率不同，为了提高电文的输入和翻译效率，必须有一套简短而无歧义的字符代码。如何编码才能使传送的电报最短？这个问题曾经困扰了许多通信技术专家，直到人们对树结构有了认识之后，才有效的解决了该问题。它的实际意义在于：使整个电文的长度大大缩短，从而迅速提高了通信的效率。,有且只有一个根；每个分枝又可以看作是一个树。,树的特点：,在树的每个生长点处用结点来表示，可得：,根上有枝，枝上有叶。一个根上有多个分枝，每条枝上又有多个更小的枝，最后是叶。,5.1.1树的定义,1）树的递归定义在一棵非空树(n0,n为树的结点数)中，有且仅有一个根结点。其余的结点可分为若干棵互不相交的子树。每棵子树也是一个树结构。,引言：前面我们学习的线性表是线性结构。接着要学习两种非线性数据结构树和图。树型结构简称为树。,2）树的二元组定义tree=(K,R)K=树中所有结点的集合R各结点间的关系r对于一棵非空树，r应满足以下条件：有且仅有一个结点无前驱，该结点被称为根结点。除根结点外，其余每个结点有且仅有一个前驱。每个结点（包括根）可以有任意多个（含0个）后继。,树的应用,定义层次关系：如家族树，表示家庭结构的关系和辈分。如单位组织结构、计算机目录结构。有序树：表明子树间的某种顺序关系。如书的目录结构。用树来表示算术表达式：如书上例5-4判定树：,思考：日常生活中树结构的例子。,5.1.2树的表示,树形表示法（图示法）二元组表示法集合图表示凹入表表示广义表表示,叶结点：度为0（没有后继结点）的点。分支结点：度0（至少有一个后继结点）的点。问：哪些叶结点、分支结点？结点的孩子：结点的直接后继。问：B的孩子？结点的双亲：结点的直接前驱。问：D、E、F的双亲？兄弟：同一个双亲的孩子祖先：根到该结点的路径上的所有点。问：H的祖先？子孙：该结点所有子树中的结点。问：B的子孙？,5.1.3树的基本术语,结点的度：每个结点具有的后继结点数或子树数。树的度：树的结点中最大的度。度为k的树被称为k叉树。问：上图中A、B、C、D、E点的度？树的度？,有序树：树中同一层上的子树有序，即子树不能交换位置。交换则成为另一棵树。无序树：树中同一层上的子树无序。即：若子树交换位置，仍认为是同一棵树。森林：零棵或多棵不相交的树的集合。一棵树若去掉根，就成为森林。例：左图去掉A，成为有2棵树的森林。,结点的层数：从根开始算起，根为第一层，根的孩子为第二层，依此类推。问：上图有几层，各层中的结点？树的深度：树中结点的最大层数。问：上图中树的深度？,5.1.4树的性质,性质1：树中的结点总数所有结点的度数+1,推导如下：从根开始，如上图中的A点，有：根(A)的度第二层结点数接着，B的度+C的度第三层结点数D的度+E的度+F的度+G的度第四层结点数依此类推，最后加1是加上一个根结点。,性质2：度为k的树中第i层上最多有ki-1个结点。(i=1)数学归纳法证明：当i=1时：树的第1层上最多有ki-1k01个结点。这是显然成立的，因为任何树的第1层都只有一个根结点。假设当i的时候上面结论成立。求证当i+1时也成立：度为k的树中第i+1层上最多有k(i+1)-1ki个结点。已知：树的第i层上有ki-1个结点。又已知：树的度为k，故每个结点最多有k个后继结点。所以：到第i+1层，结点数最多为ki-1kki个。得证。,性质3：深度为h,度为k的树最多有(kh-1)/(k-1)结点。推导如下：因为树的度为k，所以每个结点最多有k个后继。第一层：1个根结点，最多有k个后继结点1k0第二层：最多有k个结点，每个最多有k个后继kk1第三层：最多有k*k个结点，每个最多有k个后继k*kk2如此类推，直到第h层(因为树的深度为h)：有kh-1个结点，也是叶结点，无后继将每一层的最多结点数加起来，可得树的最多结点数为：k0+k1+k2+kh-1(kh-1)/(k-1),性质4：根据k叉树的总结点数，求得该树的最小深度。（证明略）,5.2二叉树,5.2.1二叉树的定义前面我们曾经学过：度为k的树被称为k叉树。那么二叉树将如何定义？二叉树的定义为：度为2的有序树。(每个结点最多有两个后继)树的度为2，则结点的度有几种可能？结点的度可以为0、1、2。考虑根结点的度为0、1、2时，可以得到二叉树的五种基本结构。,引言：二叉树是最简单的一类树；因此我们先学习它。,二叉树的五种基本结构：,二叉树的递归定义：二叉树或者是一棵空树；或者是一棵非空树。非空树由根结点和两棵互不相交的子树组成。两棵子树分别被称为左子树和右子树。注意：左右位置不可交换。左子树和右子树也都是二叉树。左孩子：左边的直接后继结点。右孩子：右边的直接后继结点。,学习二叉树的意义：从许多实际问题中抽象出来的数据结构往往是二叉树形式。一般的树都很容易转化为二叉树。许多算法问题用二叉树形式来解决非常简便。,5.2.2二叉树的性质,性质1：二叉树的叶结点数n0=度为2的结点数n21证明如下：设二叉树的叶结点总数为n0，度为1的结点总数为n1，度为2的结点总数为n2因为二叉树中结点的度只可能为0、1或2，所有以上三种结点数之和树中总结点数n0+n1+n2所有结点的度数之和n00n11n22由树的性质1，可得：n0+n1+n2n12n21化简后可得：n0n21,性质2：二叉树的第i层上最多有2i-1个结点(i=1)。证明：由树的性质2，令k=2，得证。性质3：深度为h的二叉树最多有2h-1个结点。证明：由树的性质3，令k=2，得证。二叉树的两种特殊形式：满二叉树：满足条件：每一层的结点数都达到最大值。这样的二叉树被称为满二叉树。如书上图5-7(a)完全二叉树：满足条件：1)除最后一层外，其余层都满；2)且最后一层，或者是满的，或者是在右边缺少若干个连续的结点。这样的二叉树被称为完全二叉树。如书上图5-7(b),性质4的分析如下：树中结点数为奇数的情况：如上图，n=9。（1）i=2结点：左孩子为2i=4；右孩子为2i+1=5i=3结点：左孩子为2i=6；右孩子为2i+1=7i=4结点：左孩子为2i=8；右孩子为2i+1=9,（2）i=3结点：双亲点为i/2取下整，即3/2下整1i=4结点：双亲点为4/2取下整为2i=7结点：双亲点为7/2取下整为3。其余点都可依此类推。（3）n=9，所以n/2取下整4，所以i4的点为分支结点，其余为叶结点。（4）n为奇数，所以每个分支结点既有左孩子，又有右孩子。,当n为偶数时，如书上分析图5-7(b)：n=10,性质5：建立了完全二叉树深度h与结点数n之间的关系(详见书)理想平衡树满足条件：除最后一层外，其余各层都满。而最后一层的结点可以任意分布。这样的二叉树称为理想平衡树。如书上图5-8(a)性质5对于理想平衡树也成立。满二叉树、完全二叉树和理想平衡树之间的关系：,5.2.3二叉树的基本运算,InitBTree(BT)初始化二叉树：即置为空树。CreatBTree(BT,s)建立二叉树：根据字符串s所给出的树的广义表形式，建立树的存储结构。EmptyBTree(BT)判断二叉树是否空：若空返回true，否则返回false。TraverseBTree(BT)遍历二叉树：经过树中每一个结点。FindBTree(BT,item)在二叉树中查找值为item的结点。BTreeDepth(BT)求二叉树的深度PrintBTree(BT)输出二叉树：用树的一种表示方法输出。ClearBTree(BT)清空二叉树：清除树中所有结点，并置树为空。,5.2.4二叉树的存储结构,1、顺序存储结构如何实现用一维数组对树中每个结点编号。编号的方法是：1)根结点编号为1；2)从上到下、从左到右编号；3）若某结点编号为i，则它的左孩子编号为2i，它的右孩子编号为2i+1以各结点的编号作为数组下标，把各结点中的值对应存储到一维数组中。,和线性表一样，二叉树的存储结构也有顺序和链接两种。,顺序存储的优缺点：,优点：便于查找或访问每个结点的双亲和孩子。如：编号为i的结点，其双亲点的数组下标为i/2取下整；其左孩子下标为2i；其右孩子的下标为2i+1缺点：可能造成存储空间的浪费。思考：最不浪费的情况，最浪费的情况,最不浪费的情况：完全二叉树。如右图所示。,最浪费的情况：单支二叉树。如下图为深度为4的右单支树。,2、链接存储结构,二叉树中结点的结构：,包含三个域：值域data：用于存储数据元素的值指针域left：指向左孩子，即存储左孩子结点的地址。指针域right：指向右孩子，即存储右孩子结点的地址。,用C语言如何定义二叉树中的结点：structBTreeNode/定义结点为BTreeNode结构类型ElemTypedata;/值域BTreeNode*left;/左指针域BTreeNode*right;/右指针域,二叉树链接存储示意图：可见：从二叉树的根指针出发，通过左右指针的链接，就可以找到二叉树中的每个结点。,还可以发现：链接图中有10个空指针域，仍然存在空间的浪费。6.4节“线索二叉树”会讲到如何将这些空域利用起来。,5.3二叉树遍历,二叉树遍历的定义：按照一定次序访问树中所有结点，且每个结点只能被访问一次。如何实现？,基本思想：以递归的思想来分析树。则任何一棵二叉树都可以简化为：,遍历这样一棵二叉树有几种可能的途径？,如果规定先左后右，则有三种方案：DLR：先访问根，再访问子树。被称为前序遍历或先根遍历。LDR：访问根的操作在中间。被称为中序遍历或中根遍历。LRD：先访问子树，最后访问根。被称为后序遍历或后根遍历。类似的，如果先右后左，则又有三种方案：DRL、RDL、RLD所以共6种方案。依据根被访问的次序来分，有前序、中序和后序三种遍历。由于左子树和右子树又各是一棵二叉树，因此，遍历左、右子树的问题仍是遍历二叉树的问题。所以，此问题可以用递归方法解决。,分析中序遍历算法：,Inorder(Ap),1,2,3,4,5,6,7,二叉树上前序、中序、后序遍历的用途之一,可以发现：对此二叉树进行中序遍历，结果为中缀表达式，即表达式本身：A*(B-C)+D对它进行后序遍历，得到相应的后缀表达式ABC-*D+对它进行前序遍历，得到相应的前缀表达式+*A-BCD,用途之二：非线性结构线性化：,5.4二叉树的其他运算,InitBTree(BT)初始化二叉树：即置为空树。CreateBTree(BT,s)建立二叉树：根据字符串s所给出的树的广义表形式，建立树的存储结构。EmptyBTree(BT)判断二叉树是否空：若空返回true，否则返回false。DepthBTree(BT)求二叉树的深度。递归思想。FindBTree(BT,x)在二叉树中查找值为x的结点。若找到返回true，并由x带回完整值；找不到返回false。递归思想。PrintBTree(BT)输出二叉树：用树的广义表形式输出。ClearBTree(BT)清空二叉树：清除树中所有结点，并置树为空。递归思想，由下往上清除。,1顺序存储结构与二叉树的顺序存储类似。用一维数组来实现。先对树中每个结点编号，然后以各结点的编号作为数组下标，把各结点值对应存储到一维数组中。2链接存储结构（1）标准方式k叉树的每个结点除包含值域外，还包含k个指针域，分别指向k个孩子结点。,5.5.2树的存储结构,2链接存储结构（2）广义标准方式在标准方式的每个结点中，还增加了一个指向双亲结点的指针。（3）二叉树方式先将树转换为对应的二叉树形式，再用二叉链表存储。,5.5.2树的存储结构,树转换为二叉树的方法：（1）加线：在树的所有兄弟之间加一条连线。（2）删线：对树中每个结点，只保留它与第一个孩子之间的连线，删除该结点与其它所有孩子结点之间的连线。（3）旋转以树的根结点为轴心，将子树顺时针旋转45度，使原来的右兄弟都变为结点的右孩子。,5.5.2树的存储结构,（1）CreateGTree(GT,a)功能：根据树的广义表形式a构造一棵树GT，即建立树的链接存储结构（标准方式）。（2）树的遍历功能：按照某种顺序依次访问树GT中的每个结点，并使每个结点只被访问一次。分为三种：先根遍历、后根遍历、按层遍历（3）FindGTree(GT,item)功能：在树GT中查找值为item的结点，若找到则返回true，否则返回false。递归思想。,5.5.3树的运算,（4）PrintGTree(GT)功能：以广义表的形式输出一棵树。递归思想。（5）GTreeDepth(GT)功能：求树的深度。即所有子树的最大深度+1。递归思想。（6）ClearGTree(GT)功能：先依次删除所有子树，然后删除根结点，最后置树为空。递归思想。,5.5.3树的运算,复习小结：,掌握树的概念和有关术语。理解树的性质。掌握树的图示法和广义表表示，能熟练转换两种表示。掌握二叉树