1 import java.util.Stack; 2 3 public class BinaryTree{ 4 public static void main(String[] args){ 5 BinaryTree b = new BinaryTree(); 6 b.insert(new TreeNode(15)); 7 b.insert(new TreeNode(2)); 8 b.insert(new TreeNode(18)); 9 b.insert(new TreeNode(20)); 10 b.insert(new TreeNode(16)); 11 b.insert(new TreeNode(3)); 12 b.insert(new TreeNode(4)); 13 b.insert(new TreeNode(7)); 14 b.insert(new TreeNode(6)); 15 b.insert(new TreeNode(13)); 16 b.insert(new TreeNode(17)); 17 b.preOrder(b.getRoot()); 18 System.out.println(); 19 b.preOrder(b.delete(b.searchKey(b.getRoot(), 7))); 20 } 21 22 //前序遍历: 递归实现 23 public void preOrder(TreeNode root){ 24 if(root != null){ 25 System.out.print(root.data + " "); 26 preOrder(root.leftChild); 27 preOrder(root.rightChild); 28 } 29 } 30 31 //栈实现 32 public void preOrder2(TreeNode root){ 33 if(root == null){ 34 return; 35 } 36 37 Stack stack = new Stack<>(); 38 while(root != null || !stack.empty()){ 39 if(root != null){ 40 System.out.print(root.data + " "); 41 stack.push(root); 42 root = root.leftChild; 43 } else{ 44 root = stack.pop(); 45 root = root.rightChild; 46 } 47 } 48 System.out.println(); 49 } 50 51 //中序遍历: 递归实现 52 public void inOrder(TreeNode root){ 53 if(root != null){ 54 inOrder(root.leftChild); 55 System.out.print(root.data + " "); 56 inOrder(root.rightChild); 57 } 58 } 59 60 //非递归实现 61 public void inOrder2(TreeNode root){ 62 if(root == null){ 63 return; 64 } 65 66 Stack stack = new Stack<>(); 67 while(root != null || !stack.empty()){ 68 if(root != null){ 69 stack.push(root); 70 root = root.leftChild; 71 } else{ 72 root = stack.pop(); 73 System.out.print(root.data + " "); 74 root = root.rightChild; 75 } 76 } 77 System.out.println(); 78 } 79 80 //后序遍历: 递归实现 81 public void postOrder(TreeNode root){ 82 if(root != null){ 83 postOrder(root.leftChild); 84 postOrder(root.rightChild); 85 System.out.print(root.data + " "); 86 } 87 } 88 89 //非递归实现 90 public void postOrder2(TreeNode root){ 91 if(root == null){ 92 return; 93 } 94 95 /** 96 * 后序遍历: 输出次序: 左结点→右结点→父节点, 放入栈中时的次序 97 * 从上到下就是左节点，右节点，父节点，故遍历时需先将所有结点的 98 * 父节点及其孩子节点按以上次序全都压到一个栈中，最后依次出栈即 99 * 实现后序遍历的效果100 */101 Stack temp = new Stack<>();102 Stack stack = new Stack<>();103 temp.push(root);104 while(!temp.empty()){105 TreeNode node = temp.pop();106 stack.push(node);107 108 if(node.leftChild != null){109 temp.push(node.leftChild);110 }111 112 if(node.rightChild != null){113 temp.push(node.rightChild);114 }115 }116 117 while(!stack.empty()){118 System.out.print(stack.pop() + " ");119 }120 System.out.println();121 }122 123 //查找指定值: 递归实现124 public TreeNode searchKey(TreeNode root, int key){125 if(root != null){126 if(key == root.data){127 return root;128 } else if(key > root.data){129 return searchKey(root.rightChild, key);130 } else{131 return searchKey(root.leftChild, key);132 }133 } else{134 return null;135 }136 }137 138 //非递归实现139 public TreeNode searchKey2(TreeNode root, int key){140 while(root != null){141 if (root.data == key) {142 return root;143 } else if(root.data > key){144 root = root.leftChild;145 } else {146 root = root.rightChild;147 }148 }149 return null;150 }151 152 //查找最大值153 public TreeNode searchMax(TreeNode root){154 if(root == null){155 return null;156 }157 158 TreeNode node = root;159 while(node.rightChild != null){160 node = node.rightChild;161 }162 return node;163 }164 165 //查找最小值166 public TreeNode searchMin(TreeNode root){167 if(root == null){168 return null;169 }170 171 TreeNode node = root;172 while(node.leftChild != null){173 node = node.leftChild;174 }175 return node;176 }177 178 //查找前驱节点179 public TreeNode predecessor(TreeNode node){180 if(node == null){181 return null;182 }183 184 if(node.leftChild != null){185 return this.searchMax(node.leftChild);186 }187 188 TreeNode parentNode = node.parent;189 while((parentNode != null) && (node == parentNode.leftChild)){190 node = parentNode;191 parentNode = node.parent;192 }193 return parentNode;194 }195 196 //查找后继节点197 public TreeNode successor(TreeNode node){198 if(node == null){199 return null;200 }201 202 if(node.rightChild != null){203 return this.searchMin(node.rightChild);204 }205 206 TreeNode parentNode = node.parent;207 while((parentNode != null) && (node == parentNode.rightChild)){208 node = parentNode;209 parentNode = node.parent;210 }211 return parentNode;212 }213 214 //插入结点215 public TreeNode insert(TreeNode node){216 TreeNode p = null;217 TreeNode c = root;218 while(c != null){219 p = c;220 if(node.data > c.data){221 c = c.rightChild;222 } else{223 c = c.leftChild;224 }225 }226 227 node.parent = p;228 if(p == null){229 root = node;230 } else if(node.data > p.data){231 p.rightChild = node;232 } else{233 p.leftChild = node;234 }235 return root;236 }237 238 //删除结点239 public TreeNode delete(TreeNode node){240 TreeNode x = null;241 TreeNode y = null;242 243 if((node.leftChild == null) || (node.rightChild == null)){244 y = node;245 } else{246 y = successor(node);247 }248 249 if(y.leftChild != null){250 x = y.leftChild;251 } else{252 x = y.rightChild;253 }254 255 if(x != null){256 x.parent = y.parent;257 }258 259 if(y.parent == null){260 root = x;261 } else if(y == y.parent.leftChild){262 y.parent.leftChild = x;263 } else{264 y.parent.rightChild = x;265 }266 267 if(node != y){268 node.data = y.data;269 }270 271 return root;272 }273 274 public TreeNode getRoot(){275 return root;276 }277 278 public static class TreeNode {279 public TreeNode(int data){280 this.data = data;281 }282 283 public TreeNode(int data, TreeNode parent, TreeNode leftChild, TreeNode rightChild){284 this.data = data;285 this.parent = parent;286 this.leftChild = leftChild;287 this.rightChild = rightChild;288 }289 290 private int data;291 private TreeNode parent;292 private TreeNode leftChild;293 private TreeNode rightChild;294 }295 private TreeNode root;296 }
