二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。在JAVA中可以用类很方便的实现二叉树：
1 package MyTree; 2 3 //tree.java 4 //demonstrates binary tree 5 //to run this program: C>java TreeApp 6 import java.io.*; 7 import java.util.*; // for Stack class 8 //////////////////////////////////////////////////////////////// 9 class Node 10 { 11 public int iData; // data item (key) 12 public double dData; // data item 13 public Node leftChild; // this node's left child 14 public Node rightChild; // this node's right child 15 16 public void displayNode() // display ourself 17 { 18 System.out.print('{'); 19 System.out.print(iData); 20 System.out.print(", "); 21 System.out.print(dData); 22 System.out.print("} "); 23 } 24 } // end class Node 25 //////////////////////////////////////////////////////////////// 26 class Tree 27 { 28 private Node root; // first node of tree 29 30 //------------------------------------------------------------- 31 public Tree() // constructor 32 { root = null; } // no nodes in tree yet 33 //------------------------------------------------------------- 34 public Node find(int key) // find node with given key 35 { // (assumes non-empty tree) 36 Node current = root; // start at root 37 while(current.iData != key) // while no match, 38 { 39 if(key < current.iData) // go left? 40 current = current.leftChild; 41 else // or go right? 42 current = current.rightChild; 43 if(current == null) // if no child, 44 return null; // didn't find it 45 } 46 return current; // found it 47 } // end find() 48 //------------------------------------------------------------- 49 public void insert(int id, double dd) 50 { 51 Node newNode = new Node(); // make new node 52 newNode.iData = id; // insert data 53 newNode.dData = dd; 54 if(root==null) // no node in root 55 root = newNode; 56 else // root occupied 57 { 58 Node current = root; // start at root 59 Node parent; 60 while(true) // (exits internally) 61 { 62 parent = current; 63 if(id < current.iData) // go left? 64 { 65 current = current.leftChild; 66 if(current == null) // if end of the line, 67 { // insert on left 68 parent.leftChild = newNode; 69 return; 70 } 71 } // end if go left 72 else // or go right? 73 { 74 current = current.rightChild; 75 if(current == null) // if end of the line 76 { // insert on right 77 parent.rightChild = newNode; 78 return; 79 } 80 } // end else go right 81 } // end while 82 } // end else not root 83 } // end insert() 84 //------------------------------------------------------------- 85 public boolean delete(int key) // delete node with given key 86 { // (assumes non-empty list) 87 Node current = root; 88 Node parent = root; 89 boolean isLeftChild = true; 90 91 while(current.iData != key) // search for node 92 { 93 parent = current; 94 if(key < current.iData) // go left? 95 { 96 isLeftChild = true; 97 current = current.leftChild; 98 } 99 else // or go right? 100 { 101 isLeftChild = false; 102 current = current.rightChild; 103 } 104 if(current == null) // end of the line, 105 return false; // didn't find it 106 } // end while 107 // found node to delete 108 109 // if no children, simply delete it 110 if(current.leftChild==null && 111 current.rightChild==null) 112 { 113 if(current == root) // if root, 114 root = null; // tree is empty 115 else if(isLeftChild) 116 parent.leftChild = null; // disconnect 117 else // from parent 118 parent.rightChild = null; 119 } 120 121 // if no right child, replace with left subtree 122 else if(current.rightChild==null) 123 if(current == root) 124 root = current.leftChild; 125 else if(isLeftChild) 126 parent.leftChild = current.leftChild; 127 else 128 parent.rightChild = current.leftChild; 129 130 // if no left child, replace with right subtree 131 else if(current.leftChild==null) 132 if(current == root) 133 root = current.rightChild; 134 else if(isLeftChild) 135 parent.leftChild = current.rightChild; 136 else 137 parent.rightChild = current.rightChild; 138 139 else // two children, so replace with inorder successor 140 { 141 // get successor of node to delete (current) 142 Node successor = getSuccessor(current); 143 144 // connect parent of current to successor instead 145 if(current == root) 146 root = successor; 147 else if(isLeftChild) 148 parent.leftChild = successor; 149 else 150 parent.rightChild = successor; 151 152 // connect successor to current's left child 153 successor.leftChild = current.leftChild; 154 } // end else two children 155 // (successor cannot have a left child) 156 return true; // success 157 } // end delete() 158 //------------------------------------------------------------- 159 // returns node with next-highest value after delNode 160 // goes to right child, then right child's left descendents 161 private Node getSuccessor(Node delNode) 162 { 163 Node successorParent = delNode; 164 Node successor = delNode; 165 Node current = delNode.rightChild; // go to right child 166 while(current != null) // until no more 167 { // left children, 168 successorParent = successor; 169 successor = current; 170 current = current.leftChild; // go to left child 171 } 172 // if successor not 173 if(successor != delNode.rightChild) // right child, 174 { // make connections 175 successorParent.leftChild = successor.rightChild; 176 successor.rightChild = delNode.rightChild; 177 } 178 return successor; 179 } 180 //------------------------------------------------------------- 181 public void traverse(int traverseType) 182 { 183 switch(traverseType) 184 { 185 case 1: System.out.print("\nPreorder traversal: "); 186 preOrder(root); 187 break; 188 case 2: System.out.print("\nInorder traversal: "); 189 inOrder(root); 190 break; 191 case 3: System.out.print("\nPostorder traversal: "); 192 postOrder(root); 193 break; 194 } 195 System.out.println(); 196 } 197 //------------------------------------------------------------- 198 private void preOrder(Node localRoot) 199 { 200 if(localRoot != null) 201 { 202 System.out.print(localRoot.iData + " "); 203 preOrder(localRoot.leftChild); 204 preOrder(localRoot.rightChild); 205 } 206 } 207 //------------------------------------------------------------- 208 private void inOrder(Node localRoot) 209 { 210 if(localRoot != null) 211 { 212 inOrder(localRoot.leftChild); 213 System.out.print(localRoot.iData + " "); 214 inOrder(localRoot.rightChild); 215 } 216 } 217 //------------------------------------------------------------- 218 private void postOrder(Node localRoot) 219 { 220 if(localRoot != null) 221 { 222 postOrder(localRoot.leftChild); 223 postOrder(localRoot.rightChild); 224 System.out.print(localRoot.iData + " "); 225 } 226 } 227 //------------------------------------------------------------- 228 public void displayTree() 229 { 230 Stack globalStack = new Stack(); 231 globalStack.push(root); 232 int nBlanks = 32; 233 boolean isRowEmpty = false; 234 System.out.println( 235 "......................................................"); 236 while(isRowEmpty==false) 237 { 238 Stack localStack = new Stack(); 239 isRowEmpty = true; 240 241 for(int j=0; j<nBlanks; j++) 242 System.out.print(' '); 243 244 while(globalStack.isEmpty()==false) 245 { 246 Node temp = (Node)globalStack.pop(); 247 if(temp != null) 248 { 249 System.out.print(temp.iData); 250 localStack.push(temp.leftChild); 251 localStack.push(temp.rightChild); 252 253 if(temp.leftChild != null || 254 temp.rightChild != null) 255 isRowEmpty = false; 256 } 257 else 258 { 259 System.out.print("--"); 260 localStack.push(null); 261 localStack.push(null); 262 } 263 for(int j=0; j<nBlanks*2-2; j++) 264 System.out.print(' '); 265 } // end while globalStack not empty 266 System.out.println(); 267 nBlanks /= 2; 268 while(localStack.isEmpty()==false) 269 globalStack.push( localStack.pop() ); 270 } // end while isRowEmpty is false 271 System.out.println( 272 "......................................................"); 273 } // end displayTree() 274 //------------------------------------------------------------- 275 } // end class Tree 276 //////////////////////////////////////////////////////////////// 277 class TreeApp 278 { 279 public static void main(String[] args) throws IOException 280 { 281 int value; 282 Tree theTree = new Tree(); 283 284 theTree.insert(50, 1.5); 285 theTree.insert(25, 1.2); 286 theTree.insert(75, 1.7); 287 theTree.insert(12, 1.5); 288 theTree.insert(37, 1.2); 289 theTree.insert(43, 1.7); 290 theTree.insert(30, 1.5); 291 theTree.insert(33, 1.2); 292 theTree.insert(87, 1.7); 293 theTree.insert(93, 1.5); 294 theTree.insert(97, 1.5); 295 296 while(true) 297 { 298 System.out.print("Enter first letter of show, "); 299 System.out.print("insert, find, delete, or traverse: "); 300 int choice = getChar(); 301 switch(choice) 302 { 303 case 's': 304 theTree.displayTree(); 305 break; 306 case 'i': 307 System.out.print("Enter value to insert: "); 308 value = getInt(); 309 theTree.insert(value, value + 0.9); 310 break; 311 case 'f': 312 System.out.print("Enter value to find: "); 313 value = getInt(); 314 Node found = theTree.find(value); 315 if(found != null) 316 { 317 System.out.print("Found: "); 318 found.displayNode(); 319 System.out.print("\n"); 320 } 321 else 322 System.out.print("Could not find "); 323 System.out.print(value + '\n'); 324 break; 325 case 'd': 326 System.out.print("Enter value to delete: "); 327 value = getInt(); 328 boolean didDelete = theTree.delete(value); 329 if(didDelete) 330 System.out.print("Deleted " + value + '\n'); 331 else 332 System.out.print("Could not delete "); 333 System.out.print(value + '\n'); 334 break; 335 case 't': 336 System.out.print("Enter type 1, 2 or 3: "); 337 value = getInt(); 338 theTree.traverse(value); 339 break; 340 default: 341 System.out.print("Invalid entry\n"); 342 } // end switch 343 } // end while 344 } // end main() 345 //------------------------------------------------------------- 346 public static String getString() throws IOException 347 { 348 InputStreamReader isr = new InputStreamReader(System.in); 349 BufferedReader br = new BufferedReader(isr); 350 String s = br.readLine(); 351 return s; 352 } 353 //------------------------------------------------------------- 354 public static char getChar() throws IOException 355 { 356 String s = getString(); 357 return s.charAt(0); 358 } 359 //------------------------------------------------------------- 360 public static int getInt() throws IOException 361 { 362 String s = getString(); 363 return Integer.parseInt(s); 364 } 365 //------------------------------------------------------------- 366 } // end class TreeApp 367 ////////////////////////////////////////////////////////////////
