二叉排序树

  1 package com.asus.comm;
  2 
  3 public class Tree {
  4     public class node{
  5         public node left;
  6         public node right;
  7         public int value;
  8         public node(int data){
  9             this.value=data;
 10         }
 11         
 12         public String toString() {
 13             System.out.println(String.valueOf(value));
 14             return String.valueOf(value);
 15         }    
 16     }
 17     
 18     public node root;
 19     
 20     public Tree(){
 21         
 22     }
 23     
 24     public void add(int data){
 25         if (root==null){
 26             root=new node(data);
 27         }
 28         else{
 29             add(root,data);            
 30         }
 31     }
 32     
 33     public void add(node n,int data){
 34         if (data<n.value){
 35             if (n.left==null){
 36                 n.left=new node(data);
 37                 return;
 38             }
 39             add(n.left,data);    
 40         }else{
 41             if (n.right==null){
 42                 n.right=new node(data);
 43                 return;
 44             }
 45             add(n.right,data);
 46         }
 47     }
 48     
 49     public void InOrder(node n){
 50         if (n!=null){
 51             InOrder(n.left);
 52             n.toString();
 53             InOrder(n.right);
 54         }
 55     }
 56     
 57     public node findnode(int data){
 58         node ret=null;
 59         if (root!=null){
 60             node cur=root;
 61             while(true){
 62                 if (cur.value==data){
 63                     ret=cur;
 64                     break;
 65                 }        
 66                 if (cur.value>data){
 67                     cur=cur.left;
 68                 }else{
 69                     cur=cur.right;
 70                 }
 71                 if (cur==null){
 72                     break;
 73                 }
 74             }
 75         }
 76         return ret;            
 77     }
 78     
 79     public node findparent(int data){
 80         node ret=null;
 81         if (root!=null){
 82             node cur=root;
 83             node parent=root;
 84             while(true){        
 85                 if (cur.value==data){
 86                     ret=parent;
 87                     break;
 88                 }        
 89                 if (cur.value>data){
 90                     parent=cur;
 91                     cur=cur.left;                    
 92                 }else{
 93                     parent=cur;
 94                     cur=cur.right;                    
 95                 }
 96                 if (cur==null){
 97                     break;
 98                 } 
 99             }
100         }
101         return ret;
102     }
103     
104     public void del(int data){
105 
106 
107         node cur=findnode(data);
108         node parent=findparent(data);
109         if (cur!=null){
110             if (cur.left==null && cur.right==null){
111                 if (cur==parent){
112                     root=null;
113                 }
114                 
115                 if (data>parent.value){
116                     parent.right=null;
117                 }else{
118                     parent.left=null;
119                 }
120             }
121             
122             
123             if (cur.left==null && cur.right!=null){
124                 if (data>parent.value){
125                     parent.right=cur.right;
126                 }else{
127                     parent.left=cur.right;
128                 }
129             }
130             
131             
132             if (cur.left!=null && cur.right==null){
133                 if (data>parent.value){
134                     parent.right=cur.left;
135                 }else{
136                     parent.left=cur.left;
137                 }
138             }
139             
140              if (cur.left!=null && cur.right!=null){
141                 if (data>parent.value){
142                      parent.right=delnode2(cur);        
143                 }else if (data<parent.value){
144                      parent.left=delnode(cur); ;    
145                 }else{
146                     root=delnode(cur); ;
147                 }
148                 
149              }     
150         }
151         
152         
153     }
154     private node delnode(node cur1){
155         node temp=null;
156         node tempP=null;
157         tempP=cur1;
158         temp=cur1.right;
159         while(temp.right!=null){
160             tempP=temp;
161             temp=temp.right;
162         }
163         tempP.right=null;
164         temp.right=cur1.right;
165         temp.left=cur1.left;
166         return temp;       
167     }
168     
169     private node delnode2(node cur1){
170         node temp=null;
171         node tempP=null;
172         tempP=cur1;
173         temp=cur1.right;
174         while(temp.left!=null){
175             tempP=temp;
176             temp=temp.left;
177         }
178         tempP.left=null;
179         temp.right=cur1.right;
180         temp.left=cur1.left;
181         return temp;       
182     }
183 
184 }
View Code