1）Find
·查找从根结点开始，如果树为空，返回NULL
·若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：
1）若X小于根结点键值，只需要在左子树进行搜索；
2）若X大于根结点键值，在右子树进行搜索；
3）若两者比较结果相同，搜索完成，返回此结点。
import java.util.Scanner;/** * 二叉搜索树的操作集锦 * * @author Administrator * */class BinSearchTreeTest02 {public Point1 root;// 访问结点public static void visitKey(Point1 p) {System.out.println(p.getKey() + " ");}// 构造树public static Point1 Tree() {Point1 m = new Point1(4, null, null);Point1 a = new Point1(6, m, null);Point1 b = new Point1(5, null, a);Point1 c = new Point1(14, null, null);Point1 d = new Point1(10, b, c);Point1 e = new Point1(24, null, null);Point1 f = new Point1(25, e, null);Point1 g = new Point1(20, null, f);Point1 h = new Point1(15, d, g);return h;// root}// 构造空树public static Point1 EmptyTree(int t) {Point1 a = new Point1(t, null, null);return a;}// *********************************查找操作****************************/** * 二叉搜索树查找操作方法1 * * @param t * @param node * @return */public static boolean contains(int t, Point1 node) {if (node == null)return false;// 结点为空，查找失败String st = Integer.toString(t);// 把要查找的结点转化为String类型int result = compareTo(st, node);if (result == 1) {return true;} else {return false;}}public static int compareTo(String a, Point1 p) {// String b = Integer.toString(p.getKey());// if(a.equals(b))和下面这行是等价的if (a.equals(p.getKey() + ""))return 1;int i = 0, j = 0;if (p.getLeftChild() != null) {i = compareTo(a, p.getLeftChild());}if (p.getRightChild() != null) {j = compareTo(a, p.getRightChild());}if (i == 1) {return i;} else if (j == 1) {return j;} else {return -1;}}/** * 二叉搜索树查找操作方法2(递归算法) 尾递归的方式 * * @param t * @param node * @return */public static Point1 contains2(int t, Point1 node) {if (node == null)return null;// 结点为空，查找失败if (t > node.getKey())return contains2(t, node.getRightChild());// 查找右子树else if (t < node.getKey())return contains2(t, node.getLeftChild());// 查找左子树elsereturn node;}/** * 二叉搜索树查找的搜索方法2的变形，非递归算法的效率更高 将尾递归改为迭代函数 * * @param args */public static Point1 contains3(int t, Point1 node) {while (node != null) {if (t > node.getKey())node = node.getRightChild();else if (t < node.getKey())node = node.getLeftChild();elsereturn node;}return null;}/** * 二叉搜索树的最大元素 根据其性质可以得出二叉搜索树的最大元一定位于右子树的最右端，，最小元则相反 * * @param args */public static int findMax(Point1 point) {if (point != null) {while (point.getRightChild() != null) {point = point.getRightChild();}}return point.getKey();}public static int findMin(Point1 point) {if (point == null)return 0;// 先判断树是否为空else if (point.getLeftChild() == null)return point.getKey();// 在判断左子树是否为空elsereturn findMin(point.getLeftChild());}public static void main(String[] args, Point1 p) {System.out.println("此二叉树的最大结点为：" + findMax(Tree()));System.out.println("此二叉树的最小结点为：" + findMin(Tree()));@SuppressWarnings("resource")Scanner scanner = new Scanner(System.in);System.out.println("输入一个结点，将判断是否是此二叉树的结点");int a = scanner.nextInt();if (contains2(a, Tree()) != null)System.out.println(a + " 是此二叉树的结点"); elseSystem.out.println(a + " 不是此二叉树的结点"); }}class Point1 {private int key;private Point1 LeftChild, RightChild;public Point1(int key, Point1 LeftChild, Point1 RightChild) {this.key = key;this.LeftChild = LeftChild;this.RightChild = RightChild;}public Point1(int key) {this(key, null, null);}public int getKey() {return key;}public void setKey(char key) {this.key = key;}public Point1 getLeftChild() {return LeftChild;}public void setLeftChild(Point1 leftChild) {LeftChild = leftChild;}public Point1 getRightChild() {return RightChild;}public void setRightChild(Point1 rightChild) {RightChild = rightChild;}}
（给出了三种不同的查找的思路，不过确实要比另外两种好实现一些，希望可以有所借鉴，插入和删除晚些时候放上）
往往为了自己的不能失败，而处心积虑前怕狼后怕虎，
