数据结构（Java语言版）实验指导书-查找实验.docx

《数据结构（Java语言版）实验指导书-查找实验.docx》由会员分享，可在线阅读，更多相关《数据结构（Java语言版）实验指导书-查找实验.docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、查找实验答案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 vo

2、id main(String args) System.out printf( sqrt(2)=%.lOfnrsqrt2(); ) 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

3、 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

4、 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 . rchild = InsertBSTl (p.rchild, k) ;/插入到p 的右子树中p. size = getsize (p. Ichild) + getsize (p. rchild) + ?/ / 维护结 点p的size值 return p;r = new BSTNode () ;/创建根结点rkey = a0 ;

5、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);e

6、lsereturn 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.I

7、child); 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 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);