问题描述：
对给定查找集合建立一颗二叉查找树，考查在二叉排序树中进行查找的最好情况、最坏情况和平均情况。
基本要求：
- 对给定的同一个查找集合，按升序和随机顺序建立两颗二叉排序树
- 比较同一个待查值在不同二叉排序树上进行查找的比较次数
- 对随机顺序建立的二叉排序树，输出查找的最好情况、最坏情况和平均情况。
以下代码仅供参考
以下代码仅供参考
以下代码仅供参考
/** *作者：魏宝航 *2020年11月29日,下午20:20 */ import java.util.*; public class Main { public static int searchCount=0; public static void main(String[] args) { int[] arr1 = new int[] { 4, 7, 3, 2, 5, 12, 14, 23, 34, 21 }; int[] arr2 =Arrays.copyOf(arr1, arr1.length); Arrays.sort(arr2); binarySortTree tree1 = new binarySortTree(); binarySortTree tree2 = new binarySortTree(); for (int i = 0; i < arr1.length; i++) { tree1.add(arr1[i]); tree2.add(arr2[i]); } levelOrder(tree1.root); levelOrder(tree2.root); search(tree1.root, 5); System.out.println("随机顺序二叉树查找次数："+searchCount); searchCount=0; search(tree2.root, 5); System.out.println("升序二叉树查找次数："+searchCount); } public static void levelOrder(Node root) { Queue<Node> list=new LinkedList<Node>(); list.add(root); System.out.print("层序遍历："); while(!list.isEmpty()) { Node temp=list.poll(); System.out.print(temp+" "); if(temp.left!=null) { list.add(temp.left); } if(temp.right!=null) { list.add(temp.right); } } System.out.println(); } public static void search(Node root,int key) { searchCount++; if(root==null) { return; } if(root.val==key) { return; } if(root.val<key) { search(root.right, key); } if(root.val>key) { search(root.left, key); } } } class binarySortTree { Node root; int size; public binarySortTree() { } void add(int val) { if (root == null) { root = new Node(val, null); size++; return; } Node parent = root; Node temp = root; int cmp = 0; while (temp != null) { parent = temp; if (val < temp.val) { temp = temp.left; cmp = -1; } else if (val > temp.val) { temp = temp.right; cmp = 1; } else { return; } } if (cmp < 0) { parent.left = new Node(val, parent); } else { parent.right = new Node(val, parent); } size++; } } class Node { int val; Node left; Node right; Node parent; Node(int val, Node parent) { this.val = val; this.parent = parent; } Node(int val) { this.val = val; } public String toString() { return val + " "; } }
