数据结构课件第5

1、第第5 5章章 树树 树形结构是元素之间具有分层关系的结构，它树形结构是元素之间具有分层关系的结构，它类似于自然界中的树，应用广泛，是一类很重要的类似于自然界中的树，应用广泛，是一类很重要的非线性数据结构。非线性数据结构。 在计算机应用中，常出现嵌套的数据，树结构在计算机应用中，常出现嵌套的数据，树结构提供了对该类数据的自然表示；提供了对该类数据的自然表示； 利用树结构，可以有效地解决一些算法问题。利用树结构，可以有效地解决一些算法问题。 由于结构特征，树形结构常采用递归方式定义。由于结构特征，树形结构常采用递归方式定义。被称为递归数据结构。有关树的许多算法是递归的。被称为递归数据结构。有关树

2、的许多算法是递归的。1 1、树的基本概念；、树的基本概念； 给出树的定义，关于树中的一些术语；给出树的定义，关于树中的一些术语；2 2、二叉树的定义、性质及其规范；、二叉树的定义、性质及其规范；3 3、二叉树的遍历等算法的实现；、二叉树的遍历等算法的实现；4 4、树和森林的表示、存储和遍历；、树和森林的表示、存储和遍历；5 5、二叉树的应用实例、二叉树的应用实例 哈夫曼树和哈夫曼编码。哈夫曼树和哈夫曼编码。 层次结构的数据在现实自然界中大量存在。层次结构的数据在现实自然界中大量存在。国家、省、市、县和区。国家、省、市、县和区。书的章节、回目。书的章节、回目。上级和下级。上级和下级。整体和部分。

3、整体和部分。祖先和后裔。祖先和后裔。5.1 5.1 树树的基本概念的基本概念5.1.1 5.1.1 树的定义树的定义第第5 5章章 树树5.1 5.1 树的基本概念树的基本概念5.2 5.2 二叉树二叉树5.3 5.3 二叉树的遍历二叉树的遍历5.5 5.5 树和森林树和森林5.7 5.7 哈夫曼树和哈哈夫曼树和哈 夫曼编码夫曼编码图图5-1 5-1 西欧语言谱系图西欧语言谱系图原始印欧语原始印欧语古意大利语古意大利语日耳曼语日耳曼语西日耳曼语西日耳曼语拉丁语拉丁语西西班班牙牙语语法法语语意意大大利利语语希腊语希腊语北日耳曼语北日耳曼语冰冰岛岛语语瑞瑞典典语语挪挪威威语语英英语语荷荷兰兰语语德

4、德语语古希腊语古希腊语树树形形结结构构操作系统的目录结构操作系统的目录结构1. 1. 树的定义树的定义定义定义5.15.1 有根数或树的定义有根数或树的定义 树是包括树是包括n n（n n 1 1）个元素的有限）个元素的有限非空非空集合集合D D，R R是是D D中元中元素的序偶的集合，素的序偶的集合，R R满足以下特性：满足以下特性： （1 1）有且仅有一个结点）有且仅有一个结点rDrD，不存在任何结点，不存在任何结点vDvD，vrvr，使得，使得RR，称，称r r为树的根。为树的根。 （2 2）除根）除根r r以外的所有结点以外的所有结点uDuD，都有且仅有一个结点，都有且仅有一个结点v

5、v DD， vuvu，使得，使得RR。这样定义的树也称这样定义的树也称有根树有根树，简称，简称树树。 树不为空集合，树中至少有一个根结点，根结点没有前树不为空集合，树中至少有一个根结点，根结点没有前驱，其余结点都有唯一的前驱结点。因此树形成驱，其余结点都有唯一的前驱结点。因此树形成层次层次结构。结构。2. 2. 树的递归定义树的递归定义 定义定义5.25.2 树树是包括是包括n n个结点的有限个结点的有限非空非空集合集合T T，其中一个特定的结点其中一个特定的结点r r称为称为根根，其余结点（，其余结点（T-T-rr）划分成）划分成m m（m0m0）个互）个互不相交不相交的的子集子集T T1

6、1，T T2 2，.T.Tm m，其中，每个子集都是树，被称为，其中，每个子集都是树，被称为树根树根r r的的子树子树。 定义定义5.25.2是递归的，用子树来定义树，也就是是递归的，用子树来定义树，也就是说，在树的定义中引用了树概念本身，所以，说，在树的定义中引用了树概念本身，所以，树被称为递归数据结构。树被称为递归数据结构。EAFGBCDLJMN结点结点(node)(node)：树中的元素。：树中的元素。 E E、A A、F F、B B、G G、C C、D D、L L、J J、M M、N N均为结点。均为结点。5.1.2 5.1.2 基本术语基本术语EAFGBCDLJMN路径路径(path

7、)(path)：从某个结点沿树中的：从某个结点沿树中的边可到达另一个结点，则称这两个边可到达另一个结点，则称这两个结点之间存在一条路径。结点之间存在一条路径。E E和和N N之间存在一条路径。之间存在一条路径。根结点和它的子树根（如果存在）根结点和它的子树根（如果存在）之间形成一条之间形成一条边边。路径路径(path)(path)：从某个结点沿树中的：从某个结点沿树中的边可到达另一个结点，则称这两个边可到达另一个结点，则称这两个结点之间存在一条路径。结点之间存在一条路径。E E和和N N之间存在一条路径。之间存在一条路径。EAFGBCDLJMN路径路径(path)(path)：从某个结点沿树中

8、的：从某个结点沿树中的边可到达另一个结点，则称这两个边可到达另一个结点，则称这两个结点之间存在一条路径。结点之间存在一条路径。E E和和N N之间存在一条路径。之间存在一条路径。双亲双亲(parent)(parent)：若一个结点有子树，那么该结点称为：若一个结点有子树，那么该结点称为子树根的双亲。子树根的双亲。A A、F F、B B的双亲是的双亲是E E。C C、D D的双亲是的双亲是F F。孩子孩子(child)(child)：某结点子树的根是：某结点子树的根是该结点的孩子。该结点的孩子。E E有三个孩子：有三个孩子：A A、F F、B B。D D有一个孩子：有一个孩子：J J。兄弟兄弟(

9、sibling)(sibling)：有相同双亲的结：有相同双亲的结点互为兄弟。点互为兄弟。A A、F F、B B互为兄弟，互为兄弟，C C和和D D互为兄弟。互为兄弟。结点结点G和和C互为兄弟否？互为兄弟否？EAFGBCDLJMN后裔后裔(decendent)(decendent)：一个结点的：一个结点的所有子树上的任何结点都是该结所有子树上的任何结点都是该结点的后裔。点的后裔。结点结点C C的后裔为：的后裔为：L L、M M、N N。EAFGBCDLJMN祖先祖先(ancestor)(ancestor)：从根结点到：从根结点到某个结点的路径上的所有结点某个结点的路径上的所有结点都是该结点的祖

10、先。都是该结点的祖先。结点结点L L的祖先为：的祖先为：E E、F F、C C。结点的度结点的度(degree)(degree)：结点拥有的子树数。：结点拥有的子树数。结点结点E E的度为的度为3 3，结点，结点F F的度为的度为2 2，结点结点A A的度为的度为1 1，结点，结点G G的度为的度为0 0。叶子叶子(leaf)(leaf)：度为零的结点。：度为零的结点。B B、G G、J J、M M、N N均为叶子结点。均为叶子结点。EAFGBCDLJMN分支结点分支结点(branch)(branch)：度不为零的结点。：度不为零的结点。E E、A A、F F、C C等为分支结点。等为分支结点

11、。树的度树的度：树中结点的最大的度。：树中结点的最大的度。该树的度为该树的度为3 3。结点的层次结点的层次：根结点的层次为：根结点的层次为1 1，其余结点的层次等于其，其余结点的层次等于其双亲结点的层次加双亲结点的层次加1 1。结点结点E E的层次为的层次为1 1。结点结点M M的层次为的层次为5 5。树的高度树的高度：树中结点的：树中结点的最大层次。最大层次。树中结点的最大树中结点的最大层次为层次为5 5。树的高度为树的高度为5 5。12345EAFGBCDLJMNAG无序树无序树：如果树中结点的各子树之间的次序是不重要的，：如果树中结点的各子树之间的次序是不重要的，可以交换位置。可以交换位

12、置。下列是下列是同一棵同一棵无序树：无序树：将左边树中所有结点的子树互换次序就是右边的树。将左边树中所有结点的子树互换次序就是右边的树。EAFGBCDLJMNEFBCDLJNM有序树有序树：如果树中结点的各棵子树看成是从左到右有次序：如果树中结点的各棵子树看成是从左到右有次序的，则称该树为有序树。的，则称该树为有序树。有序树的各子树从左到右为第一棵子树、第二棵，有序树的各子树从左到右为第一棵子树、第二棵，如果下列是有序树，则二者是如果下列是有序树，则二者是二棵不同的树二棵不同的树AGEAFGBCDLJMNEFBCDLJNM森林森林：是树的集合。：是树的集合。0 0个或多个不相交的树组成森林。个

13、或多个不相交的树组成森林。果园或有序森林果园或有序森林：有序树的有序集合。：有序树的有序集合。 森林与树只有很小的差别，若将树中的根去掉，森林与树只有很小的差别，若将树中的根去掉，则得到根的子树组成的森林。则得到根的子树组成的森林。 BEAGFCDLJMNE 若增加一个结点，将森林中各树的根作为新增结点的若增加一个结点，将森林中各树的根作为新增结点的孩子，则森林即成为树。孩子，则森林即成为树。 递归递归1.1.递归的定义递归的定义函数直接（间接）调用自已，称为函数的递归调用。函数直接（间接）调用自已，称为函数的递归调用。2.2.简单实例简单实例以下是一个最简单的递归函数以下是一个最简单的递归函

14、数 。void func()void func() func(); func(); 修改为：修改为：void func(int n)void func(int n) if (n=0) return ; if (n=0) return ; func(n-); func(n-); 3.3.递推关系递推关系可以把要解决的问题转化为一个新问题，而这可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的个新的问题的解决方法仍与原来的解决方法相解决方法相同同，只是所处理对象的，只是所处理对象的规模规模有规律地递增或递有规律地递增或递减，即要找到对象之间的减，即要找到对象之间的递推关系递推关

15、系。 方法相同，规模变化方法相同，规模变化4.4.递归的结束条件递归的结束条件要有一个明确的要有一个明确的结束递归结束递归的条件，一定要能够的条件，一定要能够在适当的地方在适当的地方结束递归调用结束递归调用，不然可能导致系，不然可能导致系统崩溃统崩溃int func(int n)if (n=1) return 1;return func(n-1)*n;例如：采用例如：采用递归计算递归计算N！正整数正整数N！N*(N-1)*(N-2)*2*1， 阶乘序列可转换为阶乘序列可转换为 N！N*(N-1)!，而而(N-1)!以可转换为以可转换为(N-1)!=(N-1)*(N-2)! (N-2)!=(N-

16、2)*(N-3)! ， 2!=2*1! 1!=1 递推关系：递推关系： N！N*(N-1)! 结束条件：结束条件：N等于等于1int func(int n)if (n=1) return 1;return func(n-1)*n;n=3 if(n=1) .func(n-1)*nn=2if(n=1) .func(n-1)*nn=1if(n=1)return 11func(n-1)func(n-1)n=2n=12执行过程：执行过程：设计递归算法，求有设计递归算法，求有n个元素的整数数组个元素的整数数组A中的最大值。中的最大值。 a a0 0 a a1 1 a ai i a an-2 n-2 a a

17、n-1n-10 1 0 1 i i n-2 n-1 n-2 n-1 a(n-1)Max(n)Max(n-1) a a0 0 a a1 1 a ai i a an-3 n-3 a an-2 n-2 a an-1n-10 1 0 1 i i n-2 n-1 n-2 n-1 a(n-2)Max(n-1)Max(n-2)设计递归算法，求整数数组设计递归算法，求整数数组An中的最大值。中的最大值。 a a0 0 a a1 1 a ai i a an-3 n-3 a an-2 n-2 a an-1n-10 1 0 1 i i n-2 n-1 n-2 n-1 a(1)Max(2)Max(1)递推关系：递推关

18、系：max(n)等于等于max(n-1)与与an-1之间的大者之间的大者结束条件：结束条件：n等于等于1时，时，Max(1)的值即为的值即为a0，所以不再向下递推，所以不再向下递推int Max (int a,int n) int temp;if (n=1) return a0; else temp=Max (a,n-1); if (tempan-1) return an-1; else return temp; 递推关系：递推关系：max(n)等于等于max(n-1)与与an-1之间的大者之间的大者结束条件：结束条件：n等于等于1时，时，Max(1)的值即为的值即为a0，所以不再向下递推，所

19、以不再向下递推int Max (int a,int n) int temp;if (n=1) return a0; else temp=Max (a,n-1); if (tempan-1) return an-1; else return temp; 8 8 9 10 10 0 1 2 0 1 2 n=3 if(n=1) .Max(a,2)a2n=2if(n=1) .Max(a,1)0h0时，利用时，利用性质性质1 1，高度为，高度为h h的二叉树中结点的总数最多为：的二叉树中结点的总数最多为：1012112(222.2)21hihhi12311.1nnaaaaaa补充：等比数列的求和公式是1

20、 (1)21ii i 性质 二叉树的第层上至多有个结点。性质性质1 1、2 2的图形解释的图形解释性质性质5.35.3 包含包含n n个元素的二叉树的高度个元素的二叉树的高度至少至少为为 loglog2 2 (n+1)(n+1) 根据根据性质性质2 2，高度为，高度为h h的二叉树最多有的二叉树最多有2 2h h 1 1个结点（性质个结点（性质2 2），因而），因而n n 2 2h h 1, 1, 则有则有h h loglog2 2(n+1)(n+1)。 由于由于h h是整数，所以是整数，所以h h loglog2 2 (n+1)(n+1) 。性质性质5.45.4 任意一棵二叉树中，若叶结点的

21、个数为任意一棵二叉树中，若叶结点的个数为n n0 0，度为，度为2 2的结点的个数为的结点的个数为n n2 2，则必有，则必有n n0 0=n=n2 2+1+1。设二叉树的度为设二叉树的度为1 1的结点数为的结点数为n n1 1，树中结点总数为，树中结点总数为n n，则，则n=nn=n0 0+n+n1 1+n+n2 2 （二叉树中只有度为二叉树中只有度为0 0、1 1、2 2三种类型的结点）三种类型的结点）设分支数为设分支数为B B，n n个结点的二叉树，除了根结点外，每个结点个结点的二叉树，除了根结点外，每个结点都有一个分支进入，则都有一个分支进入，则B=n-1B=n-1；分支是由度为；分支

22、是由度为1 1或者度为或者度为2 2的的射出的，又有射出的，又有B=2nB=2n2 2+n+n1 1；则有：则有：n-1=2nn-1=2n2 2+n+n1 1 n=2nn=2n2 2+n+n1 1+1+1由由 可得到：可得到：n n0 0+n+n1 1+n+n2 2=2n=2n2 2+n+n1 1+1 +1 n n0 0+n+n2 2=2n=2n2 2 +1 +1即即n n2 2=n=n0 0-1-1。定义定义5.45.4 高度为高度为h h的二叉树恰好有的二叉树恰好有2 2h h 1 1个结点时称为个结点时称为满二叉树满二叉树。0123456789101112 1314(a)满二叉树满二叉树

23、图图5.6 几种特殊的二叉树几种特殊的二叉树性质性质5.2 高度为高度为h的二叉树上的二叉树上至多至多有有2h1个结点。个结点。0123456789(b)完全二叉树完全二叉树图图5.6 几种特殊的二叉树几种特殊的二叉树9定义定义5.5 一棵二叉树中，只有一棵二叉树中，只有最下面两层结点最下面两层结点的度可以小的度可以小于于2，并且最下一层的，并且最下一层的叶结点叶结点集中在集中在靠左靠左的若干位置上。的若干位置上。这样的二叉树称为这样的二叉树称为完全二叉树完全二叉树。定义定义5.65.6 扩充二叉树也称扩充二叉树也称2-2-树，其中除树，其中除叶子叶子结点外，其余结点都必须有两个孩子。结点外，

24、其余结点都必须有两个孩子。532330111213173589完全二叉树的性质完全二叉树的性质性质性质5.55.5 具有具有n n个结点的完全二叉树的高度为个结点的完全二叉树的高度为 loglog2 2 (n+1)(n+1) 。证明：根据性质证明：根据性质2 2高度为高度为h-1h-1的完全二叉树结点个数最多为的完全二叉树结点个数最多为2 2h-1h-1-1-1高度为高度为h h的完全二叉树结点个数最多为的完全二叉树结点个数最多为2 2h h-1-1高度为高度为h h的完全二叉树结点个数取值范围的完全二叉树结点个数取值范围22h-1 h-1 , 2, 2h h) )2 2h-1 h-1 - 1

25、- 1 n 2n 2h h 1 1loglog2 2(n+1) h(n+1) hloglog2 2(n+1)+1(n+1)+1h = h = loglog2 2 (n+1)(n+1) 结论：结论： n n个结点的二叉树中完全二叉树最矮，高度为个结点的二叉树中完全二叉树最矮，高度为 loglog2 2 (n+1) (n+1) 。 n n个结点的完全二叉树和二叉判定树的高度是一样的个结点的完全二叉树和二叉判定树的高度是一样的2log1n2 2h-1h-1nn2 2h hh-1logh-1log2 2n nh hhh是整数是整数 h=h=2log1n性质性质2 2 高度为高度为h h的二叉树上至多有

26、的二叉树上至多有2 2h h 1 1个结点。个结点。性质性质5.65.6 假定对一棵有假定对一棵有n n个结点的完全二叉树中的结点，按从上个结点的完全二叉树中的结点，按从上到下、从左到右的顺序，从到下、从左到右的顺序，从0 0到到n-1n-1编号（见图编号（见图5.6(c)5.6(c)），设树中），设树中一个结点的序号为一个结点的序号为i i，0 0 i i n n ，则有以下关系成立：，则有以下关系成立：（1 1）当）当i=0i=0时，该结点为二叉树的根。时，该结点为二叉树的根。（2 2）若）若i0i0，则该结点的双亲的序号为，则该结点的双亲的序号为 ( (i-1)/2i-1)/2 （3 3

27、）若）若2i+12i+1n n，则该结点的左孩子的序号为，则该结点的左孩子的序号为2i+12i+1，否则该结点，否则该结点无左孩子。无左孩子。（4 4）若）若2i+22i+2n n，则该结点的右孩子的序号为，则该结点的右孩子的序号为2i+22i+2，否则该结点，否则该结点无右孩子。无右孩子。0123456789(b)(b)完全二叉树完全二叉树ADT ADT BinaryTreeBinaryTree Data:Data: 二叉树是结点的有限集合，该集合或者为空集，或者是由一个根二叉树是结点的有限集合，该集合或者为空集，或者是由一个根和两个互不相交的称为该根的左子树和右子树的二叉树组成。和两个互不

28、相交的称为该根的左子树和右子树的二叉树组成。 Operations:Operations: Create() Create()： 创建一棵空二叉树。创建一棵空二叉树。 Destroy(): Destroy(): 撤销一棵二叉树。撤销一棵二叉树。 IsEmpty()IsEmpty()：若二叉树空，则返回：若二叉树空，则返回truetrue，否则返回，否则返回falsefalse。 Clear(): Clear(): 移去所有结点，成为空二叉树。移去所有结点，成为空二叉树。 Root(x)Root(x)：取：取x x为根结点；若操作成功，则返回为根结点；若操作成功，则返回truetrue，否则返回

29、，否则返回falsefalse MakeTree(x,left MakeTree(x,left，right)right)：创建一棵二叉树，：创建一棵二叉树，x x为根结点，为根结点，leftleft为为 左子树，左子树，rightright为右子树。为右子树。 BreakTree(x ,left, right)BreakTree(x ,left, right)：拆分二叉树为三部分，：拆分二叉树为三部分，x x为根的值，为根的值， leftleft和和rightright分别为原树的左右子树分别为原树的左右子树 PreOrderPreOrder： 使用函数使用函数VisitVisit访问结点，先

30、序遍历二叉树。访问结点，先序遍历二叉树。 InOrderInOrder： 使用函数使用函数VisitVisit访问结点，中序遍历二叉树。访问结点，中序遍历二叉树。 PostOrderPostOrder：使用函数：使用函数VisitVisit访问结点，后序遍历二叉树。访问结点，后序遍历二叉树。 5.2.3 5.2.3 二叉树二叉树ADTADT1. 1. 完全二叉树的顺序表示完全二叉树的顺序表示 完全二叉树中的结点可以按层次顺序存储在一片连完全二叉树中的结点可以按层次顺序存储在一片连续的存储单元中。根结点保存在编号为续的存储单元中。根结点保存在编号为0 0的位置上。的位置上。注意：一般的二叉树不适

31、合用这种存储结构。注意：一般的二叉树不适合用这种存储结构。0 01 12 23 34 45 56 67 78 89 90 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9图图6.5 6.5 图图6.4(b)6.4(b)完全二叉树的顺序表示完全二叉树的顺序表示0123456789图图6.4(b) 6.4(b) 完全二叉树完全二叉树5.2.4 5.2.4 二叉树的存储表示二叉树的存储表示elementelement2. 2. 二叉树的链接表示二叉树的链接表示ABCDEFA AB B C C D D E E F F (a)(a)二叉树二叉树(b)(b)二叉树的链接表示二叉树的

32、链接表示图图6-6 6-6 二叉树的链接表示二叉树的链接表示lChildrChild二叉树的二叉链表结构有利于从二叉树的二叉链表结构有利于从双亲到孩子双亲到孩子方向的访问。采方向的访问。采取从取从根根开始，遍历整个二叉树。开始，遍历整个二叉树。root 如果应用程序需要经常执行从如果应用程序需要经常执行从孩子到双亲孩子到双亲访问，访问，可在二叉链表结点中增加一个可在二叉链表结点中增加一个parentparent域，令它指域，令它指向该结点的双亲结点。这就实现了从孩子到双亲，向该结点的双亲结点。这就实现了从孩子到双亲，以及从双亲到孩子的双向链接结构，形成以及从双亲到孩子的双向链接结构，形成多重链

33、多重链表表。templatetemplatestruct struct BTNode /BTNode /树结点树结点 BTNode() lChild = rChild = NULL; BTNode() lChild = rChild = NULL; BTNode(const T& x) BTNode(const T& x) element =x; element =x; lChild = rChild = NULL; lChild = rChild = NULL; BTNode(const T& x, BTNode BTNode(const T& x, BTNo

34、de* * l, BTNode l, BTNode* * r) r) element = x; element = x; lChild = l; lChild = l; rChild = r; rChild = r; T T elementelement; ; BTNode BTNode* * lChildlChild, , * *rChildrChild; ;5.2.5 5.2.5 二叉树类二叉树类templatetemplateclass class BinaryTreeBinaryTree public:public: BinaryTree()root = NULL; BinaryTre

35、e()root = NULL; BinaryTree()Clear();BinaryTree()Clear(); bool IsEmpty()const; bool IsEmpty()const; void Clear(); void Clear(); bool Root(T& x)const; bool Root(T& x)const; void MakeTree(const T& e,BinaryTree& left,BinaryTree& right); void MakeTree(const T& e,BinaryTree& le

36、ft,BinaryTree& right); void BreakTree(T& e,BinaryTree& left,BinaryTree& right); void BreakTree(T& e,BinaryTree& left,BinaryTree& right); void void PreOrderPreOrder(void(void(* *Visit)(T& x); /Visit)(T& x); /公有函数，用户接口公有函数，用户接口 void InOrder(void(void InOrder(void(*

37、*Visit)(T& x);Visit)(T& x); void PostOrder(void( void PostOrder(void(* *Visit)(T& x);Visit)(T& x); protected:protected: BTNode BTNode* * ; ; /指向根结点指向根结点 private:private: int Size(BTNode int Size(BTNode* * t); t); void Clear(BTNode void Clear(BTNode* * t); t); void void PreOrder(PreOr

38、der(void(void(* *Visit)(T& x),BTNodeVisit)(T& x),BTNode* * t);/ t);/私有函数，实现遍历私有函数，实现遍历 void InOrder(void(void InOrder(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t); t); void PostOrder(void( void PostOrder(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t); t);程序程

39、序5.2 5.2 二叉树类二叉树类root 本小节中，我们主要实现本小节中，我们主要实现MakeTreeMakeTree、BreakTreeBreakTree和和RootRoot运算，而将二叉树遍历算法留待下一小节专门讨论。运算，而将二叉树遍历算法留待下一小节专门讨论。 Clear()Clear()函数释放二叉链表中的所有结点，它需要通过函数释放二叉链表中的所有结点，它需要通过遍历二叉树来实现。遍历二叉树来实现。5.2.6 5.2.6 实现二叉树基本运算实现二叉树基本运算程序程序5.3 5.3 部分二叉树运算部分二叉树运算templatetemplatebool BinaryTree:Root

40、(T& x)constbool BinaryTree:Root(T& x)const/取根结点的数据值取根结点的数据值 if(root) if(root) x = root-element; x = root-element; return true; return true; else return false; else return false; ABCDEFroottemplatevoid BinaryTree:MakeTree(const T& x, BinaryTree& left,BinaryTree& right) if(root|&am

41、p;left=&right) return; root = new BTNode(x, left.root, right.root); left.root = right.root = NULL; D DC CE EF FBTNode(const T& x, BTNode* l,BTNode* r) element = x; lChild = l; rChild = r; X Xleftleftrightrightnew BTNode(x, left.root, right.root);函数功能：函数功能：以以x为根，为根，left,right为左右子树构建一棵新二叉树为左右子

42、树构建一棵新二叉树templatetemplatevoid BinaryTree:BreakTree(T& x, void BinaryTree:BreakTree(T& x, BinaryTree&left,BinaryTree&right) BinaryTree&left,BinaryTree&right) if(!root|&left=&root|left.root|right.root) if(!root|&left=&root|left.root|right.root) return; return; x

43、 = root-element; x = root-element; left.root = root-lChild; left.root = root-lChild; right.root = root-rChild; right.root = root-rChild; delete root; delete root; root = NULL; root = NULL; D DC CE EF FA Aleft.rootleft.rootright.rootright.rootroot=root=root函数功能：将二叉树左右子树拆分成二棵新的二叉树，根结点删除函数功能：将二叉树左右子树拆分

44、成二棵新的二叉树，根结点删除int main(void) BinaryTreea, b, x, y, z; char e; y.MakeTree(E, a, b); z.MakeTree(F, a, b); x.MakeTree(C, y, z); y.MakeTree(D, a, b); z.MakeTree(B, y, x); z.BreakTree(e, y, x); return 0;程序程序5.4 5.4 mainmain函数函数一个测试程序一个测试程序a b x y zEyCxFzDyBzA AB BD DC CE EF F5.3 5.3 二叉树的遍历二叉树的遍历遍历遍历（trav

45、ersetraverse）一个有限结点的集合，意味着对该集）一个有限结点的集合，意味着对该集合中的每个结点访问且仅访问一次。合中的每个结点访问且仅访问一次。二叉树遍历算法二叉树遍历算法: : (I) (I) 先左后右：先左后右：VLRVLR，LVRLVR，LRVLRV(II)(II)先右后左：先右后左：VRLVRL，RVLRVL，RLV-RLV-逆逆第第5 5章章 树树5.1 5.1 树的基本概念树的基本概念5.2 5.2 二叉树二叉树5.3 5.3 二叉树的遍历二叉树的遍历5.5 5.5 树和森林树和森林5.7 5.7 哈夫曼树和哈哈夫曼树和哈 夫曼编码夫曼编码 先序遍历（先序遍历（VLRV

46、LR）若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则 访问根结点；访问根结点； 先序遍历先序遍历左子树；左子树； 先序遍历先序遍历右子树。右子树。A AB BD DC CE EF F5.3.1 5.3.1 二叉树遍历算法二叉树遍历算法先序遍历先序遍历序列：序列： A B D C E FA B D C E F 先序遍历先序遍历序列：序列： A B D G H E C FA B D G H E C F ttttttt= t= t=t=ttt=t=t=A AB BC CD DE EF FG GH H任意一个先序遍历任意一个先序遍历序列中，根结点的位置在哪里？序列中，根结点的位置在哪里？若二

47、叉树为空，则空操作；若二叉树为空，则空操作；否则否则 访问根结点；访问根结点； 先序遍历先序遍历左子树；左子树； 先序遍历先序遍历右子树。右子树。 中序遍历（中序遍历（LVRLVR）若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。 A AB BD DC CE EF F中序遍历中序遍历序列：序列：B D A E C F B D A E C F 中序遍历中序遍历A AB BC CD DE EF FG GH HI IJ JK K 后序遍历后序遍历 （LRVLRV） 若二叉树为空，则空操作；若二叉树为

48、空，则空操作； 否则否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。A AB BD DC CE EF F后序遍历后序遍历序列：序列：D B E F C A D B E F C A 后序遍历后序遍历A AB BC CD DE EF FG GH HI IJ JK K层次遍历层次遍历A AB BC CD DE EF FG GH HI IJ JK K 对于遍历运算，设计了一个面向用户的对于遍历运算，设计了一个面向用户的公有公有成员成员函数和一个具体实现遍历操作的递归函数和一个具体实现遍历操作的递归私有私有成员函数，成员函数，两者共同完成遍历运算的功能。

49、两者共同完成遍历运算的功能。 公有成员函数：非递归函数，作为与用户的接公有成员函数：非递归函数，作为与用户的接 口。它调用私有的递归函数。口。它调用私有的递归函数。 私有成员函数：递归函数，具体实现遍历操作。私有成员函数：递归函数，具体实现遍历操作。 被公有成员函数调用。被公有成员函数调用。5.3.2 5.3.2 二叉树遍历的递归算法二叉树遍历的递归算法函数指针格式函数指针格式：函数返回类型：函数返回类型 ( (* *函数指针名函数指针名)()(参数参数1 1，参数，参数2 2) ) #include #include int max(int x,int y)return x y ? x :

50、y;int max(int x,int y)return x y ? x : y;int min(int x,int y)return x y ? x : y;int min(int x,int y)return x y ? x : y;int add(int x,int y)return x + y;int add(int x,int y)return x + y;void process(int x,int y, void process(int x,int y, int (int (* *fun) (int,int)fun) (int,int) int result; int resul

51、t; result = fun(x,y); result = fun(x,y); cout result endl; cout result endl; int main(void)int main(void) int x=1,y=2; int x=1,y=2; process(1,2,min); process(1,2,min); process(1,2,max); process(1,2,max); process(1,2,add); process(1,2,add); return 0; return 0; 程序运行结果：程序运行结果：1 12 23 3指向函数的指向函数的指针指针保存一

52、个函数的入口地址。保存一个函数的入口地址。函数返回类型函数返回类型 ( (* *函数指针名函数指针名)()(参数参数1, 1, 参数参数2)2) int ( int (* *fun)(int, int)fun)(int, int)程序程序5.5 5.5 访问元素函数访问元素函数templatetemplatevoid Visit(T& x) cout x t;void Visit(T& x) cout x t;程序程序5.6 5.6 先序遍历先序遍历templatetemplatevoid BinaryTree:void BinaryTree:PreOrderPreOrder(

53、void(void(* *Visit)(T& x)Visit)(T& x)/非递归函数，作为与用户的接口，调用递归函数非递归函数，作为与用户的接口，调用递归函数 PreOrder(Visit,root); PreOrder(Visit,root);templatetemplatevoid BinaryTree:void BinaryTree:PreOrderPreOrder(void(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t) t) if(t) if(t) /递归函数，实现遍历递归函数，实现遍历

54、Visit(t-element); Visit(t-element); PreOrder(Visit, t-lChild); PreOrder(Visit, t-lChild); PreOrder(Visit, t-rChild); PreOrder(Visit, t-rChild); 注：注：1.1.函数名相同，但参数不同，不是同一个函数。函数名相同，但参数不同，不是同一个函数。 2.2.使用函数指针使用函数指针(*Visit)(T& x)，只是为了增加程序的灵活性，只是为了增加程序的灵活性 templatevoid BinaryTree:PreOrder( BTNode* t) i

55、f(t) coutelement ; PreOrder( t-lChild); PreOrder( t-rChild); templatetemplatevoid BinaryTree:PreOrder(void(void BinaryTree:PreOrder(void(* *VisitVisit)(T& x), BTNode)(T& x), BTNode* * t) t) if(t) / if(t) /递归函数，实现遍历递归函数，实现遍历 VisitVisit(t-element);(t-element); PreOrder( PreOrder(VisitVisit, t-

56、lChild);, t-lChild); PreOrder( PreOrder(VisitVisit, t-rChild);, t-rChild); 除去函数指针，以上递归的除去函数指针，以上递归的PreOrder函数可以简化为：函数可以简化为：C CE EF Ft-cif(t) coutlChild);PreOrder( t-rChild); t-Eif(t) coutlChild);PreOrder( t-rChild); t-if(t) coutPreOrder( t-lChild);PreOrder( t-rChild); t-if(t) coutPreOrder( t-lChild)

57、;PreOrder( t-rChild); t-Fif(t) coutlChild);PreOrder( t-rChild); t-if(t) coutPreOrder( t-lChild);PreOrder( t-rChild); 补充：中序遍历补充：中序遍历templatetemplatevoid BinaryTree:InOrder(void(void BinaryTree:InOrder(void(* *Visit)(T& x)Visit)(T& x) InOrder(Visit,root); InOrder(Visit,root); templatetemplatev

58、oid BinaryTree:InOrder(void(void BinaryTree:InOrder(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t) t) if(t) if(t) InOrder(Visit, t-lChild); InOrder(Visit, t-lChild); Visit(t-element);Visit(t-element); InOrder(Visit, t-rChild); InOrder(Visit, t-rChild); 补充：后序遍历补充：后序遍历templatetemplatev

59、oid BinaryTree:PostOrder(void(void BinaryTree:PostOrder(void(* *Visit)(T& x)Visit)(T& x) PostOrder(Visit,root); PostOrder(Visit,root); templatetemplatevoid BinaryTree:PostOrder(void(void BinaryTree:PostOrder(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t) t) if(t) if(t) PostOr

60、der(Visit, t-lChild); PostOrder(Visit, t-lChild); PostOrder(Visit, t-rChild); PostOrder(Visit, t-rChild); Visit(t-element); 显然，二叉树遍历算法基本操作是访问结点显然，二叉树遍历算法基本操作是访问结点，不论按何种次序遍历，对含有，不论按何种次序遍历，对含有n n个结点的二叉个结点的二叉树，其时间复杂度均为树，其时间复杂度均为O(n)O(n)。关于三种遍历算法：关于三种遍历算法：1.1.给定一棵二叉树，能写出它的三种遍历序列。给定一棵二叉树，能写出它的三种遍历序列。2.2.给出二叉树的给出二叉树的先序遍历先序遍历序列和序列和中序遍历中序遍历序列可以序列可以唯一唯一确确 定一棵二叉树。定一棵二叉树。3.3.给出二叉树的给出二叉树的后序遍历后序遍历序列和序列和中序遍历中序遍历序列可以序列可以唯一唯一确确 定一棵二叉树。定一棵二叉树。4.4.当当n1n1时，给出二叉树的时，给出二叉树的先先序遍历序遍历序列和序列和后序遍历后序遍历序列序列不可以不可以唯唯一确定一棵二叉树。一确定一棵二叉树。例如：例如：先先序序列：序序列：ABAB，后序序列：