System.out.println("您要查找的是："+data);
? ? ? ? Node node;
? ? ? ? if((node=searchNode(new Node(data)))==null){
? ? ? ? ? ? System.out.println("树中没有该结点！");
? ? ? ? }else{
? ? ? ? ? ? System.out.println("查找"+node.key+"成功！");
? ? ? ? }
? ? }
? ?
? ? private Node searchNode(Node node){? ? //private供内部调用，搜索结点
? ? ? ? if(node==null){
? ? ? ? ? ? System.out.println("输入为空，查找失败！");
? ? ? ? }else{
? ? ? ? ? ? if(root==null){
? ? ? ? ? ? ? ? System.out.println("该树为空树！");
? ? ? ? ? ? }else{? ? ? ? ? ? ? ? ? ? ? ? //开始查找
? ? ? ? ? ? ? ? boolean isFound=false;? ?
? ? ? ? ? ? ? ? Node x=root;
? ? ? ? ? ? ? ? Node y=null;
? ? ? ? ? ? ? ? while(!isFound&&x!=null){? ? //当查到或者到了叶子节点还没查到时，终结！
? ? ? ? ? ? ? ? ? ? y=x;
? ? ? ? ? ? ? ? ? ? if(node.key==x.key){? ?
? ? ? ? ? ? ? ? ? ? ? ? isFound=true;
? ? ? ? ? ? ? ? ? ? }else{? ? ? ? ? ? ? ? ? ? //通过比较大小往下面查找
? ? ? ? ? ? ? ? ? ? ? ? if(node.key>x.key){? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? x=x.rightChild;
? ? ? ? ? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? ? ? ? ? x=x.leftChild;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(isFound){? ? //没找到的话，在最后返回null
? ? ? ? ? ? ? ? ? ? return y;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return null;
? ? }
? ?
? ? /*
? ? * 获取最大值
? ? */
? ? public void? getMax(){? ?
? ? ? ? Node node;
? ? ? ? if((node=getMaxNode(root))==null){
? ? ? ? ? ? System.out.println("该树为空！");
? ? ? ? }else{
? ? ? ? ? ? System.out.println("最大的结点是："+node.key);
? ? ? ? }
? ? ? ?
? ? }
? ?
? ? private Node getMaxNode(Node node){? ? //获取最大值
? ? ? ? if(node!=null){
? ? ? ? ? ? Node x=node;
? ? ? ? ? ? Node y=null;
? ? ? ? ? ? while(x!=null){? ? //一直往右遍历直到底就是最大值了！
? ? ? ? ? ? ? ? y=x;
? ? ? ? ? ? ? ? x=x.rightChild;
? ? ? ? ? ? }
? ? ? ? ? ? return y;
? ? ? ? }
? ? ? ? return null;
? ? }
? ?
? ? /*
? ? * 获取最小值
? ? */
? ? public void getMin(){? ?
? ? ? ? Node node;
? ? ? ? if((node=getMinNode(root))==null){
? ? ? ? ? ? System.out.println("该树为空！");
? ? ? ? }else{
? ? ? ? ? ? System.out.println("最小的结点是："+node.key);
? ? ? ? }
? ? }
? ? private Node getMinNode(Node node){? ? //获取最小值
? ? ? ? if(node!=null){
? ? ? ? ? ? Node x=node;
? ? ? ? ? ? Node y=null;
? ? ? ? ? ? while(x!=null){? ? //一直往左遍历直到底就是最小值了！
? ? ? ? ? ? ? ? y=x;
? ? ? ? ? ? ? ? x=x.leftChild;
? ? ? ? ? ? }
? ? ? ? ? ? return y;
? ? ? ? }
? ? ? ? return null;
? ? }
? ?
? ? /*
? ? * 获取前驱结点
? ? */
? ? public void getPre(int data){? ?
? ? ? ? Node node=null;
? ? ? ? System.out.println(data+"的前驱结点：");
? ? ? ? if((node=getPreNode(searchNode(new Node(data))))==null){
? ? ? ? ? ? System.out.println("该结点不存在或无前驱结点！");
? ? ? ? }else{
? ? ? ? ? ? System.out.println(data+"的前驱结点为："+node.key);
? ? ? ? }
? ? }
? ?
? ? private Node getPreNode(Node node){? ? //获取前驱结点
? ? ? ? if(node==null){
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? if(node.leftChild!=null){? ? //当有左孩子时，前驱结点就是左子树的最大值
? ? ? ? ? ? return getMaxNode(node.leftChild);
? ? ? ? }else{//当不存在左孩子时，前驱结点就是——它的祖先，而且，它在这个祖先的右子树中。这句话自己画图就能理解了
? ? ? ? ? ? Node x=node;
? ? ? ? ? ? Node y=node.parent;
? ? ? ? ? ? while(y!=null&&x==y.leftChild){
? ? ? ? ? ? ? ? x=y;
? ? ? ? ? ? ? ? y=y.parent;
? ? ? ? ? ? }
? ? ? ? ? ? return y;
? ? ? ? }
? ? }
? ?
? ? /*
? ? * 获取后继结点
? ? */
? ? public void getPost(int data){? ?
? ? ? ? Node node=null;
? ? ? ? System.out.println(data+"的后继结点：");
? ? ? ? if((node=getPostNode(searchNode(new Node(data))))==null){
? ? ? ? ? ? System.out.println("该结点不存在或无后继结点！");
? ? ? ? }else{
? ? ? ? ? ? System.out.println(data+"的后继结点为："+node.key);
? ? ? ? }
? ? }
? ?
? ? private Node getPostNode(Node node){? ? //获取后继结点
? ? ? ? if(node==null){
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? if(node.rightChild!=null){? ? //当有右孩子时，前驱结点就是右子树的最小值
? ? ? ? ? ? return getMinNode(node.rightChild);
? ? ? ? }else{//当不存在右孩子时，后继结点就是——它的祖先，而且，它在这个祖先的左子树中。这句话自己画图就能理解了
? ? ? ? ? ? Node x=node;
? ? ? ? ? ? Node y=node.parent;
? ? ? ? ? ? while(y!=null&&x==y.rightChild){
? ? ? ? ? ? ? ? x=y;
? ? ? ? ? ? ? ? y=y.parent;
? ? ? ? ? ? }
? ? ? ? ? ? return y; |