数据结构 (1)

1、数据结构Data Structure数据结构与算法分析 - Java语言描述，Mark Allen Weiss著 冯舜玺译，机械工业出版社 直接插入排序算法l一个元素的数组是一个有序的数组l从第一个元素开始，通过把第二个元素插入到这个单元数组中，就可以得到一个大小为2的有序数组。l依次类推，插入第三个元素可以得到一个大小为3的有序数组,l该算法称为直接插入排序。（3）例子）例子 例如，已知待排序的一组记录的初始排列如下所示：例如，已知待排序的一组记录的初始排列如下所示：),94(),27(),13(),76(),97(),65(),38(),49(RRRRRRRR按算法按算法10.1进行直接插

2、入排序的过程如图进行直接插入排序的过程如图10.1所示。所示。监视哨监视哨 L.r0 图图 直接插入排序示例直接插入排序示例初始关键字初始关键字: (49) 38 65 97 76 13 27 49 i = 2: (38) (38 49) 65 97 76 13 27 49i = 3: (65) (38 49 65) 97 76 13 27 49 i = 4: (97) (38 49 65 97) 76 13 27 49 i = 5: (76) (38 49 65 76 97) 13 27 49 i = 6: (13) (13 38 49 65 76 97) 27 49 i = 7: (27)

3、 (13 27 38 49 65 76 97) 49 i = 8: (49) (13 27 38 49 49 65 76 97) （4）算法效率）算法效率 从空间来看，只需要一个记录的辅助空间。从空间来看，只需要一个记录的辅助空间。 从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。 数达最大值数达最大值(n + 2)(n1)/2（即（即 ），记录移动的次数也达最大值），记录移动的次数也达最大值(n + 4)(n1)/2（即（即 ）。）。nii2)1(当待排序列中记录按关键字非递增有序排序（当待排序列中记录按关键字非递增

4、有序排序（“逆序逆序”）时，总的比较次）时，总的比较次nii2若待排序记录是随机的，即待排序列中的记录可能出现的各种排列概率若待排序记录是随机的，即待排序列中的记录可能出现的各种排列概率 相同，则取上述最小值和最大值的平均值，作为直接插入排序时所需进相同，则取上述最小值和最大值的平均值，作为直接插入排序时所需进 行关键字间的比较次数和移动记录的次数，约为行关键字间的比较次数和移动记录的次数，约为n2/4。综上所述，直接插入排序的时间复杂度为综上所述，直接插入排序的时间复杂度为O(n2)。当待排序列中记录按关键字非递减有序排序（当待排序列中记录按关键字非递减有序排序（“正序正序”）时，所需进行关

5、）时，所需进行关键字间比较的次数达最小值键字间比较的次数达最小值n1（即（即 ），记录不需移动。），记录不需移动。ni21算法实现（JAVA 重点）void InsertionSort (int a, int n)for (int i =1;i=0&temp=n-1，f(n)BDCD L R先序遍历序列：A B D C先序遍历先序遍历（必须掌握（必须掌握 先序先序 中序中序 后序排列方法）后序排列方法）二叉树的遍历（递归实现）l中序遍历（LDR）中序遍历的递归过程为：若二叉树为空，遍历结束。否则，l（1）中序遍历根结点的左子树；l（2）访问根结点；l（3）中序遍历根结点的右子树。中序遍

6、历二叉树的递归算法如下：lvoid InOrder（BiTree bt）l/*中序遍历二叉树bt*/l if (bt=NULL) return; /*递归调用的结束条件*/l InOrder（bt-lchild）; /*中序递归遍历bt的左子树*/l Visite（bt-data）; /*访问结点的数据域*/l InOrder（bt-rchild）; /*中序递归遍历bt的右子树*/ lADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:二叉树的遍历（递归实现）l后序遍历（LRD）后序遍历的递归过程为若二叉树为空，遍历结束。否则：l（1）后序遍历根结点

7、的左子树；l（2）后序遍历根结点的右子树。l（3）访问根结点；后序遍历二叉树的递归算法如下：lvoid PostOrder（BiTree bt）l/*后序遍历二叉树bt*/l if (bt=NULL) return; /*递归调用的结束条件*/l PostOrder（bt-lchild）; /*后序递归遍历bt的左子树*/l PostOrder（bt-rchild）; /*后序递归遍历bt的右子树*/ l Visite（bt-data）; /*访问结点的数据域*/lADBC L R DL R DL R DADCL R D后序遍历序列： D B C A后序遍历:B二叉树的遍历（重点重点 必须掌握

8、排列方法必须掌握排列方法）l举例先序遍历结果序列：A B D G C E F 中序遍历结果序列：D G B A E C F 后序遍历结果序列：G D B E F C A 二叉树的遍历（递归实现列子列子）l练习先序遍历序号：A,B,D,E,C,F中序遍历序号：D,B,E,A,C,F后序遍历序号：D,E,B,F,C,A二叉树遍历的应用l应用：表达式求值的表达式语法分析树表达式的语法用二叉树表示非常直观把表达式语法树用3种遍历方式写出来会得到什么呢？先序遍历：- + a * b - c d / e f中序遍历：a + b * c - d - e / f后续遍历：a b c d - * + e f /

9、 -Exercise(30 mins)l给出前述二叉树前序、中序和后序遍历结果给出前述二叉树前序、中序和后序遍历结果l假设一棵二叉树的后序遍历序列为假设一棵二叉树的后序遍历序列为D G J H E B I F C A，中序遍历序列为，中序遍历序列为D B G E H J A C I F，则其前序遍历序列为，则其前序遍历序列为 。l高度为高度为h的二叉树中，节点最大个数为的二叉树中，节点最大个数为 2h-1 。（。（重重点点）l计算二叉树的高度。计算二叉树的高度。l计算二叉树中左子树比右子树高计算二叉树中左子树比右子树高1的节点个数。的节点个数。l计算二叉树中树叶的个数。计算二叉树中树叶的个数。

10、举一反三 会运用排序 重点后序遍历序列为后序遍历序列为 D G J H E B I F C A，中序遍历序列为中序遍历序列为 D B G E H J A C I F，则其前序遍历序列为则其前序遍历序列为 A B D E G H J C F I 。二叉查找树l如果在二叉树中，对于每个节点X，它的左子树所有项的值都小于X中的项，而它的右子树中所有项都大于X中的项，则称这样的二叉树为二叉查找树。6243861142378YesNo123532264520(g)二叉查找树的生成 (b)32(c)3226 (d)322645(a)32264535 (e)3226451235 (f)设序列为设序列为(32

11、,26,45,35,12,20)记录的关键码序列为：63，90，70，55，67，42，98，83，则构造一棵二叉查找树的过程如下：636390706390557063906755706390426755706390984267557063908398426755706390findMin和findMaxBinaryNode findMin( BinaryNode t)if (t = null)return null;else if ( t.left =null)return t;return findMin(t.left);二叉查找树的查找算法假定二叉查找树的根结点指针为 root ，给定的

12、关键字值为 x ，则查找算法可描述为： 置初值： t root ； 如果 x t .element ，则查找成功，算法结束； 否则，如果 x t .element ，而且 q 的左子树非空，则将 q 的左子树根送 q ，转步骤；否则，查找失败，结束算法； 否则，如果 x t .element ，而且 q 的右子树非空，则将 q 的右子树根送 q ，转步骤；否则，查找失败，算法结束。lBinaryNode find( Comparable x, BinaryNode t) /二叉查找树中查找算法l if( t = = null )l return null;l if( x. compareTo(

13、 t.element ) 0 )l return find( x, t.right );l elsel return t; /Matchl 二叉查找树的插入算法 540230803530540802插入 35二叉查找树上结点的插入 步骤：步骤：（1）若二叉查找树是空树，则）若二叉查找树是空树，则k成为二叉查找树成为二叉查找树的根；的根；（2 2）若二叉查找树非空，则将）若二叉查找树非空，则将k与二叉查找树的与二叉查找树的根进行比较，如果根进行比较，如果k的值等于根结点的值，则停的值等于根结点的值，则停止插入；如果止插入；如果k的值小于根结点的值，则将的值小于根结点的值，则将k插入插入左子树；如

14、果左子树；如果k的值大于根结点的值，则将的值大于根结点的值，则将k插入插入右子树。右子树。 Insert（重点重点 插入算法插入算法）private BinaryNode insert( Comparable X, BinaryNode t)if(t =null)t = new BinaryNode( x, null, null );else if( pareTo( t.element)0)t.right = insert(x,t.right);else;return t;Remove（重点重点 删除算法删除算法）private BinaryNode remove (Comparable x,

15、 BinaryNode t)if(t=null)return t;if( pareTo( t.element )0)t.right = remove( x, t.right );else if( t.left!=null&t.right!=null )t.element = findMin(t.right).element;t.right = remove(t.element, t.right);elset = (t.left !=null)?t.left:t.right;return t;扩充二叉树l考察一棵二叉树，有一类特殊的节点，叫做外部节点，用来代替树中的空子树，其他节点叫做内

16、部节点。l增加了外部节点的二叉树称为扩充二叉树。二叉树遍历的应用l应用二：二叉树遍历的递归思维应用于二叉树的其他操作l查找二叉树的数据元素（存储结构为二叉链表）Search（bt，x）在bt为二叉树的根结点指针的二叉树中查找数据元素x。查找成功时返回该结点的指针；查找失败时返回空指针。BiTree Search（BiTree bt，elemtype x）/*在bt为根结点指针的二叉树中查找数据元素x*/ BiTree p; if (bt-data=x) return bt; /*查找成功返回，先序遍历，先检查根节点*/ if (bt-lchild!=NULL) return(Search(bt

17、-lchild,x); l/*在bt-lchild为根结点指针的二叉树中查找数据元素x*/ if (bt-rchild!=NULL) return(Search(bt-rchild,x);l/*在bt-rchild为根结点指针的二叉树中查找数据元素x*/ return NULL; /*查找失败返回*/二叉树遍历的应用l应用二：二叉树遍历的递归思维应用于二叉树的其他操作l求二叉树的高度（存储结构为二叉链表）这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。int hight(BTree BT)/h1和h2

18、分别是以BT为根的左右子树的高度 if (BT=NULL) return 0; else h1=hight(BT-lchild);/先处理树的左右子树 h2=hight(BT-right); return maxh1,h2+1; 二叉树遍历的应用l应用二：二叉树遍历的递归思维应用于二叉树的其他操作l计算一棵二叉树的叶子结点数目这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面中序遍历实现。void Leaf(BTree BT,int *count) if (BT) Leaf(BT-child,&count); /计算左子树的叶子结点个数 if (BT-lchild=NULL&BT-rchild=NULL) (*count)+; /处理节点，中序 Leaf(BT-rchild,&count); /计算右子树的叶子结点个数 二叉树遍历的应用l应用三：由遍历序列恢复二叉树l思考：已知二叉树，可以确定其先序序列、中序序列和后序序列，所以遍历序列中包含了二叉树的逻辑信息。那么，如果已知二叉树的某种遍历序列，是否能够确定这颗二叉树呢？如果能，应该如何做呢？举例：如果已知某个二叉树的先序遍历结果是1，2，3，那么它的二叉树