大学计算机基础第9章 程序设计与软件工程基础.ppt

8．二叉树的遍历 遍历二叉树:按某条有哪些信誉好的足球投注网站路径巡访树中的每一个结点，使每一个结点均被访问一次且仅被访问一次。9-27 二叉树的链式存储结构 寻找遍历二叉树的规律： （1）二叉树基本组成单元：根结点Ｄ、左子树Ｌ和右子树Ｒ。 （2）遍历二叉树有DLR、LDR、LRD、DRL、RDL、RLD六种方案。规定先左后右，则只有三种： DLR—先（根）序遍历， LDR—中（根）序遍历， LRD—后（根）序遍历。 如图9-22所示的二叉树的先序序列是ABCDEGF；中序序列是CBEGDFA；后序序列是CGEFDBA；层序序列是ABCDEFG。 图9-22二叉树的遍历 9.2.6 查找 1．顺序查找 顺序查找是一种最基本和最简单的查找方法。它的思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。 2．折半查找 折半查找又称二分查找，是针对有序表进行查找的简单、有效而又较常用的方法。所谓有序表，即要求表中的各元素按关键字的值有序（升序或降序）存放。 设表的长度为n，表的被查找部分的头为low，尾为high，初始时，low=1,high=n,k为关键字的值。 (1)计算中间记录的序号mid=（low+high）/2取整； （2）若k=r[mid].key,成功，否则： 若 kr[mid].key, 则high=mid―1,重复（1）； 若kr[mid].key, 则low=mid+1,重复（1）； 直到成功或不成功（此时lowhigh）。 具体算法如下： Void binsrch(struct node r[ ],int n,int k) { int mid,low,high,find; low=1; high=n;find=0; /*置区间初值*/ while ((low=high) (!find)) { mid=(low+high)/2; /*求中点*/ if (k= = r[mid].key) find=1; /*已查到*/ else if(kr[mid].key ) low=mid+1; /*在后半区间查找*/ else high=mid-1; /*在前半区间查找*/ } if (find) return (mid); /*查找成功，返回找到元素的位置*/ else return (0); /*查找不成功，返回0标记*/ } 9.2.7 排序 1．交换类排序 （1）快速排序 快速排序(Quick Sort)称划分交换排序。其基本思想是：在当前无序区R[1]到R[h]中任取一个记录作为比较的“基准”（不妨记为temp），用此基准将当前无序区划分为左右两个较小的无序子区：R[1]到R[i-1]和R[i+1]到R[h]，且左边的无序子区中记录的关键字均小于或等于基准temp的关键字，右边的无序子区中记录的关键字均大于或等于基准temp的关键字，而基准temp则位于最终排序的位置上。 图9-23展示了一次划分的过程。图中方括号表示无序区，方框表示基准temp的关键字，它未参加真正的交换，只是在划分完成时才将它放入正确的位置上。 初始关键字 [[49 ] 38 65 97 76 13 27 49 ] i j j向左扫描 [[49] 38 65 97 76 13 27 49 ] i j 第一次交换后 [27 38 65 97 76 13 [ ] 49 ] i j i向右扫描 [27 38 65 97 76 13 [ ] 49 ] i j 第二次交换后 [27 38 [ ] 97 76 13 65 49 ] i j j向左扫描，i位置不变 第三次交换后 [27 38 13 97 76 [ ] 65 49