《典型查找算法PPT课件》由会员分享，可在线阅读，更多相关《典型查找算法PPT课件（67页珍藏版）》请在金锄头文库上搜索。
1、第第9章章 典型查找算法典型查找算法 顺顺序序查查找找、折折半半查查找找和和分分块块查查找找的的方方法法和算法，相应的平均查找长度和算法，相应的平均查找长度二二叉叉排排序序树树查查找找方方法法和和算算法法，二二叉叉平平衡衡树概念树概念散散列列表表的的概概念念，散散列列函函数数的的构构造造方方法法，处处理理冲冲突突的的方方法法及及散散列列表表各各种种运运算算的的实实现算法现算法 1第第9章章 典型查找算法典型查找算法 9.1 9.1 实例：学生分配座位实例：学生分配座位 9.2 9.2 静态查找静态查找 9.3 9.3 动态查找动态查找 9.4 9.4 散列查找散列查找 本章总结本章总结29.1
2、 实例：学生分配座位实例：学生分配座位 9.1.1 问题描述问题描述 9.1.2 问题的分析问题的分析 9.1.3 实现算法实现算法 9.1.4 基本概念基本概念 39.1.1 问题描述问题描述 教室中的学生座位分配教室中的学生座位分配是一个最简单是一个最简单的例子。假定某教室有的例子。假定某教室有35个座位，如果个座位，如果不加限定任意就坐或按某种规律就座，则不加限定任意就坐或按某种规律就座，则要查找某学生要查找某学生时就要时就要将待查找的学生与当将待查找的学生与当前座位上的学生进行比较前座位上的学生进行比较。 49.1.2 问题的分析问题的分析 用计算机来解决查找学生问题，通常需要做以下工
3、作： 第一，学生信息以什么形式表示和存储学生信息以什么形式表示和存储； 第二，查找的具体实现方法查找的具体实现方法(算法)。5struct student int num1; / 表示座号int num2; / 表示学号char name12; / 表示姓名 ；struct listStudent stusize; /保存学生记录Int len; /学生人数;学生信息的存储方式：学生信息的存储方式：6 从第一个学生开始，从第一个学生开始，依次与查找的学生进依次与查找的学生进行比较行比较。在查找过程中，若某个学生的记录与。在查找过程中，若某个学生的记录与所查找学生记录所查找学生记录相等相等，则查
4、找，则查找成功成功，返回该学返回该学生在表中位置生在表中位置；若全部比较完毕，没有符合条；若全部比较完毕，没有符合条件的学生记录，则查找件的学生记录，则查找不成功不成功，返回返回-1。查找学生的方法：查找学生的方法：79.1.3 实现算法实现算法 int search ( List &L , int s )/从表L.stu0,L.stu1,L.stun-1的n个元素中查找关键字为S的元素，若查找成功返回该生学号，否则返回-1 int i;for (i=0; iL.len; i+)if ( L.stui=s) break;if (i0i0， 从而节省比较的时间。从而节省比较的时间。 顺序查找的平
5、均查找长度为：顺序查找的平均查找长度为： 有时，表中各结点的查找概率并不相等。因有时，表中各结点的查找概率并不相等。因 此若事先知道表中各结点查找概率的分布情此若事先知道表中各结点查找概率的分布情 况，则可将表中结点按查找概率从大到小排况，则可将表中结点按查找概率从大到小排 列，以便提高顺序查找的效率。列，以便提高顺序查找的效率。 顺序查找的特点：算法简单，但查找效率低。顺序查找的特点：算法简单，但查找效率低。16折半查找又称为折半查找又称为二分查找二分查找。折半要求折半要求查找表是有序的查找表是有序的。折半查找的折半查找的基本思想基本思想是：是：首首先先将将待待查查的的K值值与与有有序序表表
6、R0到到Rn-1的的中中间间位位置置mid上上的的结结点点的的关关键键字字进进行行比比较较，若若相相等等，则则查找完成查找完成；否否则则，若若Rmid.keyK，则则说说明明待待查查找找的的结结点点只只可可能能在在左左表表R0到到Rmid-1中中，只只需需在在左左子子表表中中继继续续查查找找；否否则则在在右右子子表表中中继继续续查查找找。这这样样，经过一次键字的比较就缩小了一半的查找区间。经过一次键字的比较就缩小了一半的查找区间。重重复复执执行行，直直到到找找到到关关键键字字为为K的的元元素素或或当当前前查查找区间为空找区间为空(即表明查找失败即表明查找失败)为止。为止。 折半查找折半查找17
7、05 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 92查找查找K=21K=21的过程（查找成功）的过程（查找成功）midhighlowlowhighmidlowhighmid1805 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 92查找查找K=85K=85的过程（查找失败）的过程（查找失败）05 13 19 21 37 5
8、6 64 75 80 88 92 lowhighmidmidlowhighmidlowhighlowhigh19折折半半查查找找算算法法（low和和high分分别别表表示示当当前前查查找找区区间的下界和上界）间的下界和上界）int BINSEARCH(SSTable ST,keytype K) int low,mid,high; low0; highn-1; while (low=high) mid(low+high)/2; /整除整除 if (K=ST.Rmid.key) return mid; if (KST.Rmid.key) highmid-1; else lowmid+1; retu
9、rn -1; /查找失败查找失败20算法分析算法分析 虽然折半查找的效率较高，但它要求被查找虽然折半查找的效率较高，但它要求被查找序列事先按关键字排好序，而排序本身是一种很序列事先按关键字排好序，而排序本身是一种很费时的运算；另外，折半查找只适用于顺序存储费时的运算；另外，折半查找只适用于顺序存储结构，因此，折半查找特别适用于那种一经建立结构，因此，折半查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。就很少改动、而又需要经常查找的线性表。219.2.3 分块查找分块查找 分块查找分块查找(索引顺序查找索引顺序查找) 基本思想：基本思想： 首先把一个线性表(即主表)按照一定的函数
10、关系或条件划分成若干个逻辑子表逻辑子表，为每个子表分别建立一个索引索引项项，由所有子表的索引项构成一个索引表索引表。当进行分块查找时，先根据所给的关键字查找索引表，从中查找出给定先根据所给的关键字查找索引表，从中查找出给定值值K K刚好小于等于索引值的那个索引项，找到待查块，然刚好小于等于索引值的那个索引项，找到待查块，然后再到主表中查找该块，从中查找待查的记录后再到主表中查找该块，从中查找待查的记录。实现算法：实现算法： （略） 索引表是有序的索引表是有序的，所以在索引表上既可以采用顺序查找，也可以采用折半查找，而每个块中的记录排列是任意任意的的，所以在块内只能采用顺序查找。 23平均查找长
11、度为：平均查找长度为： 设将长度为设将长度为n n的表均匀分成的表均匀分成b b块，每块有块，每块有s s个记录，个记录，则则b=n/s，查找表中每条记录的概率相等，则每块查找表中每条记录的概率相等，则每块查找的概率为查找的概率为1/b，块中每条记录的查找概率为块中每条记录的查找概率为1/s。则顺序查找索引表时：则顺序查找索引表时： 24分块有序表的索引存储表示分块有序表的索引存储表示 25索引表结点的数据类型定义如下：索引表结点的数据类型定义如下： #define MaxIndex typedef struct KeyType key; int addr(link); IdxType; 在在
12、这这种种结结构构下下，查查找找过过程程要要分分为为两两步步：首首先先查查找找索索引引表表。因因为为索索引引表表是是有有序序表表，所所以以可可采采用用二二分分查查找找或或顺顺序序查查找找，以以确确定定给给定定值值所所在在的的块块。因因为为块块中中的的记记录录可可以以是任意排列的，所以再在已确定的是任意排列的，所以再在已确定的块块中进行中进行顺序查找顺序查找。 26分块查找算法如下：分块查找算法如下：int IdxSerch(SeqList A,IdxType index,int b,KeyType k,int n) /分块查找关键字为分块查找关键字为k的记录，索引表为的记录，索引表为index0
13、.b-1 int low=0,high=b-1,mid,i; int s=n/b; /每块记录个数每块记录个数 while(low=high) /在索引表中进行二分查找，找到的位置放在在索引表中进行二分查找，找到的位置放在low中中 mid=(low+high)/2; if(indexmid.keyk) low=mid+1 else high=mid-1; if(lowb) /在块中顺序查找在块中顺序查找 for(i=indexlow.addr;i=indexlow.addr+s-1 & i(*q)-elem.key)/*kx大于当前结点*q的元素关键码*/*p=*q;*q=(*q)-rc;/
14、*将当前结点*q的右子女置为新根*/elseif(kxelem.key) /*kx小于当前结点*q的元素关键码*/*p=*q;*q=(*q)-lc; /*将当前结点*q的左子女置为新根*/elseflag=1;break;/*查找成功，返回*/ /*while*/ return flag;35时间复杂度：时间复杂度： 分析：在二叉排序树上进行查找的过程中，根结点为待查结点时，给定值同树中结点的比较次数仅为一次，待查结点位于最后一层时，比较的次数为树的深度。 普通情况下，对二叉排序树进行查找的时间复杂度为O( )； 最差情况下(二叉排序树为一棵单支树)，其时间复杂度为O(n)。 为使得由任何初始
15、序列构成的二叉排序树的平均查找长度是对数级的，所以我们可使得构造的二叉排序树是一个平衡二叉树。36三.二叉排序树插入操作和构造一棵二叉排序树 向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。 构造一棵二叉排序树则是逐个插入结点的过程。 37 图9.5从空树开始建立二叉排序树的过程38【算法9.5】int InsertNode (NodeType *t,KeyType kx) /*在二叉排序树*t上插入关键码为kx的
16、结点*/ NodeType *q, *s , *p=*t; int flag=0;if(!SearchElem(*t,&p,&q,kx); /*在*t为根的子树上查找*/s=(NodeType *)malloc(sizeof(NodeType);/*申请结点,并赋值*/s-elem.key=kx;s-lc=NULL;s-rc=NULL;flag=1; /*设置插入成功标志*/ if(!p) t=s; /*向空树中插入时*/elseif(kxp-elem.key)p-rc=s; /*插入结点为p的右子女*/elsep-lc=s; /*插入结点为p的左子女*/return flag; 399.3.
17、2 二叉平衡树二叉平衡树 二叉平衡树二叉平衡树( (AVL树) )： 或者是一棵空树，或者是一棵具有如下性质的非空二叉树： 它的左子树和右子树都是二叉平衡树，且左子树左子树和右子树的深度之差的绝对值不大于和右子树的深度之差的绝对值不大于1 1。二叉平衡树中结点的左子树的深度减去它的右子树的深度的值定义为平衡因子平衡因子BFBF，则BFBF的值只可能为的值只可能为1 1、0 0和和1 1。 40平衡二叉树和非平衡二叉树平衡二叉树和非平衡二叉树图42 图给出了两棵二叉排序树，每个结点旁边所注数字是以该结点为根的树中，左子树与右子树高度之差，这个数字称为结点的平衡因子。由平衡二叉树定义，所有结点的平
18、衡因子只能取-1，0，1三个值之一。若二叉排序树中存在这样的结点，其平衡因子的绝对值大于1，这棵树就不是平衡二叉树。如图9.9（a）所示的二叉排序树。 在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整。设a结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下四种情况：43对二叉排序树插入结点而构造平衡二叉树的规律：对二叉排序树插入结点而构造平衡二叉树的规律：设最小子树根结点的指针为a，则失去平衡后进行调整的规律： LLLL型：型：单向右旋平衡处理单向右旋平衡处理 RRRR型：型：单向左旋平衡处理单向左旋平衡处理 LR LR型：型：双向旋转
19、双向旋转( (先左后右先左后右) )平衡处理平衡处理 RL RL型：型：双向旋转双向旋转( (先右后左先右后左) )平衡处理平衡处理时间复杂度：时间复杂度： 在查找过程中和给定值进行比较的关键字的个数不超过树的深度，所以，在二叉平衡树上进行查找的时时间间复复杂杂度度为为O(O(log2n)。 44一.左单旋转（RR型） 在图(a)所示的树上插入结点x，如图(b)所示。结点x插入在结点c的右子树E上，导致结点a的平衡因子绝对值大于1，以结点a为根的子树失去平衡。45【调整策略】 调整后的子树除了各结点的平衡因子绝对值不超过1，还必须是二叉排序树。由于结点c的左子树D可作为结点a的右子树，将结点a
20、为根的子树调整为左子树是B，右子树是D，再将结点a为根的子树调整为结点c的左子树，结点c为新的根结点，如图(c)。【平衡化调整操作判定】 沿插入路径检查三个点a、c、E，若它们处于“”直线上的同一个方向，则要作左单旋转，即以结点c为轴逆时针旋转。 46说明： 1.旋转操作的正确性可以由二叉排序树的特性：中序遍历所得关键字序列自小至大有序证明之。2. 当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转即可。因为经过旋转处理之后的子树深度和插入之前相同，因而不影响插入路径上所由祖先结点的平衡度。47二. 右单旋转 （LL型） 右单旋转与左单旋转类似，沿插入路径检查三个点a、
21、c、E，若它们处于“/”直线上的同一个方向，则要作右单旋转，即以结点c为轴顺时针旋转，如图所示。48 如图为插入前的子树，根结点a的左子树比右子树高度高1，待插入结点x将插入到结点b的右子树上，并使结点b的右子树高度增1，从而使结点a的平衡因子的绝对值大于1，导致结点a为根的子树平衡被破坏，如图9.12 插入前图9.13(a)、9.14(d)所示。 图9.12插入前49三. 先左后右双向旋转 （LR型）图9.135051 沿插入路径检查三个点a、b、c，若它们呈“”字形，需要进行先左后右双向旋转： 1. 首先，对结点b为根的子树，以结点c为轴，向左逆时针旋转，结点c成为该子树的新根，如图(b、
22、e)； 2. 由于旋转后，待插入结点x相当于插入到结点b为根的子树上，这样a、c、b三点处于“/”直线上的同一个方向，则要作右单旋转，即以结点c为轴顺时针旋转，如图(c、f)。 52四. 先右后左双向旋转（RL型） 先右后左双向旋转和先左后右双向旋转对称，自行补充整理。 539.4 散列查找散列查找 9.4.1 散列存储和散列函数的构造方法散列存储和散列函数的构造方法 9.4.2 解决冲突的方法解决冲突的方法 9.4.3 散列查找实现算法和性能分析散列查找实现算法和性能分析 549.4.1 散列存储和散列函数构造散列存储和散列函数构造基本术语：基本术语： 散列存储散列存储：以数据中每个元素的关
23、键字：以数据中每个元素的关键字K K为自变量，为自变量，通过一个函数通过一个函数f(k)f(k)计算出函数值，把这个值同存储空计算出函数值，把这个值同存储空间中一个唯一的存储位置相对应，将该元素存储到这间中一个唯一的存储位置相对应，将该元素存储到这个存储位置中。函数个存储位置中。函数f(k)f(k)称为称为散列函数散列函数或或哈希函数哈希函数。f(k)f(k)的值称为的值称为散列地址散列地址或或哈希地址哈希地址；进行散列存储的；进行散列存储的地址空间称为地址空间称为散列表散列表或或哈希表哈希表。 冲突冲突：实际应用中，由于散列函数的构造方法不实际应用中，由于散列函数的构造方法不同，常会出现同，
24、常会出现多个元素同时占用一个存储单元多个元素同时占用一个存储单元的情况，的情况，即散列地址相同，这种现象叫冲突即散列地址相同，这种现象叫冲突。具有相同函数值具有相同函数值的不同关键字的元素，称为的不同关键字的元素，称为同义词同义词。 55常用的构造散列函数的方法：常用的构造散列函数的方法：直接定址法直接定址法: :取关键字或关键字的某个现行函数值为哈希地址。取关键字或关键字的某个现行函数值为哈希地址。即：即：H(keyH(key)=key )=key 或或 H(keyH(key)=)=akey+bakey+b。数字分析法数字分析法假假设设关关键键字字是是以以r r为为基基的的数数( (如如：以
25、以1010为为基基的的十十进进制制数数) )，并并且且哈哈希希表表中中可可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。平方取中法：平方取中法：取关键字平方后的中间几位为哈希地址。取关键字平方后的中间几位为哈希地址。折叠法折叠法 将将关关键键字字分分割割成成位位数数相相同同的的几几部部分分（最最后后一一部部分分的的位位数数可可以以不不同同），然然后取这几部分的叠加和（舍去进位）作为哈希地址。后取这几部分的叠加和（舍去进位）作为哈希地址。除留余数法除留余数法 取取关关键键字字被被某某个个不不大大于于哈哈希希表表
26、表表长长m m的的数数p p除除后后所所得得余余数数为为哈哈希希地地址址。即即 H(keyH(key) = key MOD p , p=m) = key MOD p , p=m该方法是一种最简单，也最常用的构造哈希函数的方法。该方法是一种最简单，也最常用的构造哈希函数的方法。 随机数法随机数法选选择择一一个个随随机机函函数数，取取关关键键字字的的随随机机函函数数值值为为它它的的哈哈希希地地址址。即即: :H(keyH(key)=)=random(keyrandom(key) )569.4.2 解决冲突的方法解决冲突的方法 常用的解决冲突的方法有以下几种：常用的解决冲突的方法有以下几种：开放定地
27、址开放定地址链地址法链地址法 再哈希法再哈希法建立一个公共溢出区建立一个公共溢出区 57 从发生冲突的那个单元开始，按照一定次序，从散列表中查找出一个空闲存储单元，把发生冲突的待插入元素存入到该单元中的一类解决冲突的方法。设H(key)为散列函数，m为散列表长度。则开放定址法中找下一个空闲空间的散列函找下一个空闲空间的散列函数为：数为：Hi=(H(key)+ dHi=(H(key)+ di i)%m)%m 其中，i=1,2k； d di i称为增称为增量量，以di的取值分为以下三种： (1)di=1,2,3m-1,称线性探测再散列线性探测再散列。 (2)di=12,-12，22，-22，k2,
28、(km/2)称二次探测再散二次探测再散列列。 (3)di=随机数序列，称为随机探测再散列随机探测再散列。开放定址法：开放定址法：58 把具有相同散列地址的关键字放在同一链表中相同散列地址的关键字放在同一链表中，称为同义词链表同义词链表。通常把具有相同散列地址的关键字都存放在一个同义词链表中，有m个散列地址就有m个链表，同时用数组tm存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以ti为头指针的单链表中。 链地址法：链地址法：599.4.3 散列查找实现算法和性能分析散列查找实现算法和性能分析算算法法思思想想：在在哈哈希希表表上上进进行行查查找找的的过过程程和和哈哈希希造造表表的
29、的过过程程一一致致。给给定定K K值值，根根据据造造表表时时设设定定的的哈哈西西函函数数求求得得哈哈希希地地址址，若若表表中中此此位位置置上上没没有有记记录录，则则查查找找不不成成功功；否否则则比比较较关关键键字字，若若何何给给定定值值相相等等，则则查查找找成成功功；否否则则根根据据造造表表时时设设定定的的处处理理冲冲突突的的方方法法找找“下下一一地地址址”，直直至至哈哈希希表表中中某某个位置为个位置为“空空”或者表中所填记录的关键字等于给定值时为止。或者表中所填记录的关键字等于给定值时为止。结论：结论： l由于产生“冲突”，查找过程仍是一个给定值和关键字进行比较的过程。因此，仍需以平均查找长
30、度作为衡量散列表的查找效率的量度。 l查找过程中比较个数取决于因素：散列函数、解决冲突的方法和散列表的装填因子。 装填因子装填因子定义： =越小，发生冲突的可能性就越小；越大，发生冲突的可能性就越大。 60本章总结本章总结本章主要介绍了数据处理中的几几种种典典型型的的查查找找方方法法、及及实现算法和各种查找方法的性能分析实现算法和各种查找方法的性能分析。查查找找：指在一个含有众多数据元素(或记录)的查找表中找出某个“特定的”数据元素（或记录）。 查找过程：查找过程：是数据处理的一个环节，它的下一环节是对查找到的结果进行处理，根据所做的操作的不同根据所做的操作的不同，将查找方法分为静态查找静态查
31、找和动态查找动态查找。静态查找方法介绍了顺序查找、二分查找和分块查找三种方法。动态查找方法介绍了二叉排序树查找和二叉平衡树查找。 61顺顺序序查查找找既适用于顺序表，也适用与单链表，时时间间复复杂度是杂度是O（n），），平均查找长度为（平均查找长度为（n+1）/2 。折折半半查查找找只适用于顺顺序序存存储储的的有有序序表表。折半查找的的时时间间复复杂杂度度为为O（log2n）。折半查找的查找过程可以画成一棵二叉判定树二叉判定树，它是一棵二叉排序树是一棵二叉排序树。分分块块查查找找过过程程分分为为两两部部分分：先在索索引引表表中查找；然后在主表的对应块主表的对应块中顺序查找。二二叉叉排排序序树树
32、查查找找：根根据据二二叉叉排排序序树树的的定定义义，首先访问根结点，若其值等于给定值则查找成功；若给定值比根结点大，继续向右子树中查找；否则给定值比根结点小，继续在左子树中查找，直到找到该结点或找不到为止，此时查找失败。62 二叉平衡树的BFBF的的值值只只可可能能为为1 1、0 0和和1 1。二叉平衡树的构造过程中进行调整的方法共有四种。二叉平衡树的查找过程也与二叉排序树类似，从根结点开始，向左或右子树进行查找。散散列列存存储储是是一一种种存存储储方方法法，也也是是一一种种查查找找方方法法。散列存储通过对元素的关键字按给定函数进行计算，得到存储地址，此地址称为散散列列地地址址，用于计算地址的
33、给定函数称为散散列列函函数数，用于存储元素的地址空间称为散散列列表表。构造散列函数方法有直直接接定定址址法法、数数字字分分析析法法、平平均均取取中中法法、折折叠叠法法和和除除留留余余数数法法。常常用用的的解解决决冲冲突突的的方方法法有有开开放放定定址址法法、链链地地址址法法。平平均均查查找找长长度度等等于于查找每个元素时的比较次数之和除以所有元素的个数。 63习题：习题：1. 请指出在顺序表请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用拆半法查找关键码中，用拆半法查找关键码12需做需做多少次关键码比较。多少次关键码比较。 （）（）A.2 B.3 C.4 D.5
34、答案是C。第一次和15比较；第二次和7比较；第三次和10比较；第四次和14比较;比较后结束，没找到。642.对一棵查找树根结点而言，左子树中所有结点与对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是右子树中所有结点的关键字大小关系是()A、小于、小于 B、大于、大于 C、等于、等于、D、不小于、不小于答案是A653.在一棵空的二叉查找树中依次插入关键字序列为在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、5、1，29，请画出所，请画出所得到的二叉查找树。得到的二叉查找树。664.为什么有序的单链表不能进行折半查找为什么有序的单链表不能
35、进行折半查找? ?答：因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。5.5.将将二二叉叉排排序序树树T T的的先先序序序序列列中中的的关关键键字字依依次次插插入入一一空空树树中，所得二叉排序树中，所得二叉排序树TT与与T T是否相同是否相同? ?为什么为什么? ?答：这两棵二叉树完全相同。建立二叉排序树，每棵子树都是从上到下的建立过程；先序输出顺序：根，左，右。总是先输出根结点。它每棵子树的输出顺序也是从上到下的顺序。对二叉排序树来说用任何一种从上到下的输出序列，来构造二叉排序树形状都是相同的。例如二叉树的层序遍历序列。67
