java#二叉搜索树的查找#

treeNode 类的定义

public class treeNode {

    private Object data ;
    private treeNode LeftT ;
    private treeNode RightT ;
    ......
   
构造方法，setter and getter等就省略啦
}

 二叉搜索树：非空左子树的所有节点的键值都要小于根节点的键值，非空右子树的所有节点的键值都要大于根节点的键值，左右子树都是二叉搜索树

public class mySearchTree {
   
//迭代查找
    public static treeNode Find(treeNode root,int x){
        while (root!=null){
            if(x>(int)root.getData()){ 
                root=root.RightT() ;
            }
            else if(x<(int)root.getData()){
                root=root.LeftT() ;
            }
            else
                break;
        }
        return root;
    }
//递归查找
    public static treeNode Finding(treeNode root,int x){
        if(root==null)
            return null;
        if(x>(int)root.getData()){
            return Finding(root.RightT(),x) ;
        }
        else if (x<(int)root.getData()){
            return Finding(root.LeftT(),x) ;
        }
        else
            return root;
    }
    //二叉搜索数找最大元素
    //          4
    //        2   6
    //       1 3 5 7
    //二叉搜索数的最大值一定在右子树的最右节点，就像图中的7
    public static treeNode findMax(treeNode root){
        if(root!=null){
            while (root.RightT()!=null){
                root=root.RightT() ;
            }
        }
        return root ;
    }

    //二叉搜索数找最小元素
    //          4          4
    //        2   6     2     6
    //       1 3 5 7      3 5   7
    //二叉搜索树的最小元素分两种情况
    //a:该二叉树最左端有左一个左叶子节点，如图中的第一种情况，min=1;
    //b:该二叉树最左端没有叶子节点，如同中的第二中情况，此时  min=2;
    public static treeNode findMin(treeNode root){
        if(root==null)
            return null ;
        if(root.LeftT()==null)
            return root;
        else return findMin(root.LeftT()) ;
    }

测试下，buildTreeAuto参考上期内容

public static void main(String[] args) {
        //创建一个二叉搜索树
        //          4             4
        //        2   6         2    6
        //       0 3 5 7       1 3  5 7
        //      
        //注意左右子树也要符合左儿子小于father节点，右儿子大于father节点
        //层序生成二叉树
        Object []treeTest1={4,2,6,0,3,5,7,0,0,0,0,0,0} ;
        treeNode myT1=myTree.buildTreeAuto(treeTest1);
        //先序遍历一下
        rootFirsTravel(myT1);
        //查找data=1的节点
        System.out.println();
        System.out.println("元素3所在节点："+Find(myT1,3) );
        System.out.println("元素6所在节点"+Finding(myT1,6));
        System.out.println(findMax(myT1));
        System.out.println(findMin(myT1));

        Object []treeTest2={4,2,6,1,3,5,7,0,0,0,0,0,0,0,0} ;
        treeNode myT2=myTree.buildTreeAuto(treeTest2);
        //rootFirsTravel(myT2);
        System.out.println(findMin(myT2));

    }