数据结构导论第六章

《数据结构导论第六章》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、集合：是一种逻辑结构，其特点是元素之间没有逻辑关系，元素只是共处于一个集合当中。集合的操作：插入删除查找查找：是指在数据元素集合中查找满足某种条件的数据元素。查找表：称用于查找的数据集合为查找表。查找表由同一类型的数据元素所构成，在查找表的结构中每一个数据元素称为查找对象。关键字：其中应当有一个属性，其值可以唯一地标识这个数据元素查找表可分为两类:静态查找表仅作查询和检索操作的查找表。动态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。查找根据给定的某个值，在查找表中确定一个其关键字等于

2、给定值的数据元素或（记录）若查找表中存在这样一个记录，则称“查找成功”，给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，给出“空记录”或“空指针”。nASLsuccpicii1•Ｐi为查找第i个元素的概率•Ｃi为查找第i个元素所用到的比较次数。nn11n(n1)n1ASL顺序查找piciii1i1nn221234567][3101623263853]lowmidhigh查找key=16的过程intbinsearch(R,K){low=1;high=R.n;while(low

3、R.item[mid].key)returnmid;if(KR.item[mid].key)low=mid+1；}return0；}34234134234判定树6391471025811bs11b1s11nASLLLji(s)1bsbwbs222sj1i1bs11b1s11nASLLLji(s)1bsbwbs222sj1i11900f(s)(s)12s20101030630405155920811是否二叉排序树中序遍历的结果是一个递增的序列。图中二叉排序树

4、的各结点的值为1～9，标出各结点的值已知二叉排序树10个结点值依次为1-10，其结构如图所示，试标出该二叉树各结点所对应得具体值。550033008800204400990035853288查找关键字==50,35,90,95二叉排序树上的查找思想若二叉排树为非空，先拿根结点值与待查值进行比较，①若相等，则查找成功；②若根结点值大于待查值，则进入左子树继续查找，③否则，进入右子树继续查找；若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找失败。336611225282266406618229933333317550039925662216285632.给定表（39，1

5、4，22，8，65，28，88，29，67，13，10），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。391465822881328671029被删关键字=828050308020409035853288其双亲结点中相应指针域的值改为“空”（2）被删除的结点只有左子树或者只有右子树被删关键字=840050308020409035853288其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。（3）被删除的结点既有左子树，也有右子树被删关键字=5050308020409035853288方式1：以其中序前驱替代被删除结点，然后再

6、删除该前驱结点（3）被删除的结点既有左子树，也有右子树被删关键字=50503080204090354285323688方式1：以其中序前驱替代被删除结点，然后再删除该前驱结点（3）被删除的结点既有左子树，也有右子树被删关键字=5050308020409035853288方式2：p为被删除结点P的左孩子代替p，p的右孩子做p的左孩子的最右孩子平衡二叉树(AVL树)若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。平衡因子：结点的左、右子树高度差-1,0,155484822是平衡树1不是平衡树构造二叉平衡（查找）树的方法是：按照构造二叉排序树的方法

7、进行构造，出现不平衡时，进行旋转调整四种不平衡形态313122133122LL型RR型LR型RL型有数据序列：{20，50，35，80，90，32，85，40，88，30}请按顺序构造一棵二叉平衡树205035有数据序列：{20，50，35，80，90，32，85，40，88，30}请按顺序构造一棵二叉平衡树2035502050358090有数据序列：{20，50，35，80，90，32，85，40，88，30}请按顺序构造一棵二叉平衡树353