数据结构（Java语言版）实验指导书-查找实验.docx
-
资源ID：96744378
资源大小：18.90KB
全文页数：3页
- 资源格式： DOCX
下载积分：15金币
快捷下载
会员登录下载
微信登录下载
三方登录下载：
微信扫一扫登录
|
友情提示
2、PDF文件下载后，可能会被浏览器默认打开，此种情况可以点击浏览器菜单，保存网页到桌面，就可以正常下载了。
3、本站不支持迅雷下载，请使用电脑自带的IE浏览器，或者360浏览器、谷歌浏览器下载即可。
4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩，下载后原文更清晰。
5、试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓。
|
数据结构（Java语言版）实验指导书-查找实验.docx
查找实验答案public class 实验 10_1 static final double EPSINON = 0.0000000001;static double sqrt2() double low = 1.4, high = 1.5;/72 值的区间double mid = (low + high) / 2;while (high - low > EPSINON) /折半查找if (mid * mid < 2)low = mid;/ /高区间查找elsehigh = mid;/ /低区间查找mid = (low + high) / 2;)return mid;)public static void main(String args) System.out printf(" sqrt(2)=%.lOfn"rsqrt2(); ) class BSTNode (public int key;int size;int ent;public BSTNode Ichild; public BSTNode rchild; BSTNode() (Ichild = rchild = null; size = ent = 1;) class BSTClass public BSTNode r; public BSTClass () (r = null;)public void InsertBST (int k)/二叉排序树结点类/存放关键字,假设关键字为int类型/以这个结点为根的子树中结点个数/相同关键字出现次数/存放左孩子指针/存放右孩子指针/构造方法/二叉排序树类/二叉排序树根结点/构造方法/插入一个关键字为k的结点InsertBSTl (r, k);/求结点p的sizepublic void CreateBST (int a)/由关键字序列a创建一棵二叉排序树private int getsize(BSTNode p)if (p = null) return 0;elsereturn p.size; )private BSTNode InsertBSTl (BSTNode p, int k) /在以p 为根的BST 中插入 关键字为k的结点if (p = null)/原树为空,新插入的元素为根结点p = new BSTNode(); p.key = k; else if (k = p.key) p cnt+; else if (k < p.key)p . Ichild = InsertBSTl (p. Ichild, k) ;/插入到p 的左子树中else if (k > p.key)p . rchild = InsertBSTl (p.rchild, k) ;/插入到p 的右子树中p. size = getsize (p. Ichild) + getsize (p. rchild) + ?/ / 维护结 点p的size值 return p;r = new BSTNode () ;/创建根结点rkey = a0 ;for (int i = 1; i < a. length; i+)/创建其他结点InsertBSTl (rz a i ) ;/插入关键字) public int Rank (int k)/求关键字k 的名次( return Rankl(r, k); ) private int Rankl (BSTNode p, int k) /在结点p的子树中求关键字k的名次 (if (p = null) return 0;if (k = p.key)/找到关键字为k的结点return getsize(p.Ichild) + 1; if (k < p.key) return Rankl(p.Ichild, k);elsereturn Rankl(p.rchild, k) + getsize(p.Ichild) + p.ent;)public void DispBST ()/输出二叉排序树的括号表示串DispBSTl (r);/被DispBST方法调用)private void DispBSTl(BSTNode p)if (p != null) System.out.print(p.key + H " + p.size + p.ent + "");/输出根结点值(p.Ichild != null | p.rchild != null) System.out.print ( n ( n); DispBSTl(p.Ichild); if (p.rchild != null)System.out.print DispBSTl(p.rchild); System.out.print(")n);/有孩子结点时才输出(/递归处理左子树/有右孩子结点时才输出/递归处理右子树/有孩子结点时才输出'')public class 实验 10_2 public static void main(String args) int a = 3, 5, 4, 6, 6, 5, 1, 3;BSTClass bt = new BSTClass ();bt , CreateBST (a);System.out.printin();System.out.print (u BST : H;bt.DispBST();System.out.printin();TreeSet<Integer> s = new TreeSet ();for (int i = 0; i < a. length; i+)/米用 TreeSet 集合去重s add(ai);System. out .printin ( n求解结果");for (Integer e : s)System, out.printin (n ” + + ”的名次是” + bt. Rank (e);
