作者：禪樓望月（http://www.cnblogs.com/yaoyinglong/）

屬性：

①若它的左子樹不為空，則左子樹上所有節點的值均小于它的根節點的值。

②若它的右子樹不為空，則右子樹上所有節點的值均大于它的根節點的值。

③它的左、右子樹也都是排序二叉樹。

添加操作：

當根節點為空時，添加進的節點作為根節點。然后每次添加節點時，都從根節點過濾，以根節點作為當前節點，如果新節點大于當前節點，則走當前節點的右子節點分支，如果新節點小于當前節點，則走當前節點的左子節點分支。然后再用右子節點或左子節點作為當前節點與新加節點比較，如果新加節點大，則當前節點的右子節點，如果新加節點小，則當前節點的左子節點。依次類推直到左子樹或右子樹為null時，將該新節點添加在這里。

圖解：

代碼解析：

1 public void add(T data){ 2 Node newNode=new Node(data); 3 if(root==null){ 4 root=newNode; 5 }else { 6 add(newNode, root); 7 } 8 } 9 public void add(Node addNode,Node parentNode) { 10 T data=addNode.data; 11 Node currentNode=parentNode; 12 Node parent=null; 13 int flag=0; 14 while(currentNode!=null){ 15 parent=currentNode; 16 flag=data.compareTo(currentNode.data); 17 if(flag>0){ 18 currentNode=currentNode.rightChild; 19 }else { 20 currentNode=currentNode.leftChild; 21 } 22 } 23 if(flag>0){ 24 parent.rightChild=addNode; 25 }else { 26 parent.leftChild=addNode; 27 } 28 addNode.parent=parent; 29 } View Code

添加操作相對簡單，麻煩的是刪除操作。

刪除操作

該操作有很多的情況：

????? 第一：待刪除的節點是葉子節點

????? 第二：待刪除的節點有左子樹沒有右子樹

????? 第三：待刪除的節點沒有左子樹有右子樹

????? 第四：待刪除的節點既沒有左子樹也沒有右子樹。

圖解

在第一大類中我們還可分：

1、該葉子節點就是根節點，即樹中只有一個根節點。

這是最簡單的情況，直接樹的根root指向null即可。

2、否則便要判斷該葉子節點是其父節點的左子節點呢還是其父節點的右子節點

下圖為葉子節點是其父節點的左子節點，右子節點一樣。

在第二大類中我們還可以細分：

1、待刪除的節點就是根節點。

只需將根節點的左子節點（因為這是根節點只有左子節點）指向父節點的指針打斷，并將該左子節點設為根節點即可。

2、如果待刪除的節點不是根節點，那就必須討論待刪除的節點是其父節點的左子節點還是右子節點。

以是其父節點的左子節點為例（右子節點的情況一樣），我們需要讓待刪除節點的父節點的指向其左孩子的指針重新指向待刪除節點的左孩子，讓待刪除節點的左孩子的指向父節點的指針重新指向待刪除節點的父節點。

這期間，我們并沒有打斷圖中節點5指向其左孩子節點3的指針，也沒有打斷節點5指向其父節點6的指針。這是因為，沒這個必要。我們不打斷這些節點5永遠也不會被訪問到，而且會被垃圾回收。

第三大類和第二大類一樣。

第四大類中

總的思想就是：找到待刪除節點左子樹中的最大節點（leftMaxNode)，然后用leftMaxNode替代待刪除的節點即可。這句話看似簡單，但是實現起來可不是那么的容易！！！

我們也可以細分：

1、待刪除節點就是根節點

???? 1.1 leftMaxNode就是待刪除節點的左孩子。即待刪除節點左子樹中沒有右節點。

???? 1.2 如果待刪除的節點不是根節點

對于這種情況，我們需要顯示顯示打斷的“指針”只有兩個：如下圖中，節點3指向其右子節點4（leftMaxNode）的指針，即節點4（leftMaxNode）指向其父節點3的指針。然后用節點4（leftMaxNode）替換節點5（根節點）即可。

2、待刪除的節點不是根節點

???? 2.1 被刪除節點的左子樹中最大節點不是其左子節點

如下圖所示：

在這種情況下使用節點節點4替換節點5的時候，對于節點4和節點8、節點9的之間的“指針”創建比較容易，但是節點3與節點4之間的“指針”卻不好創建，因為節點4的左子樹可能很復雜，我們不知道將節點3插入哪里合適，所以，解決辦法為，將節點3利用排序二叉樹添加新節點的功能以新節點的形式加入節點4 中。

???? 2.2 被刪除節點的左子樹中最大節點就是是其左子節點

即，如下情況，

這種情況很簡單了，就不詳細說明了。

完整代碼

1 package com.yyl.tree; 2 3 import java.util.ArrayDeque; 4 import java.util.ArrayList; 5 import java.util.List; 6 import java.util.Queue; 7 8 public class SortedBinaryTree<T extends Comparable<T>> { 9 public class Node{ 10 T data=null; 11 Node parent=null; 12 public Node getParent() { 13 return parent; 14 } 15 public void setParent(Node parent) { 16 this.parent = parent; 17 } 18 19 Node leftChild=null; 20 Node rightChild=null; 21 //region【訪問器】 22 public T getData() { 23 return data; 24 } 25 public void setData(T data) { 26 this.data = data; 27 } 28 public Node getLeftChild() { 29 return leftChild; 30 } 31 public void setLeftChild(Node leftChild) { 32 this.leftChild = leftChild; 33 } 34 public Node getRightChild() { 35 return rightChild; 36 } 37 public void setRightChild(Node rightChild) { 38 this.rightChild = rightChild; 39 } 40 //endregion 41 42 // region 【構造器】 43 public Node(){} 44 public Node(T data){ 45 this.data=data; 46 } 47 public Node(T data, Node leftChild, Node rightChild){ 48 this.data=data; 49 this.leftChild=leftChild; 50 this.rightChild=rightChild; 51 } 52 //endregion 53 @Override 54 public boolean equals(Object obj) { 55 if(this.data==obj){ 56 return true; 57 }else if(this.getClass()==obj.getClass()){ 58 Node nodeObj=(Node)obj; 59 return this.data.compareTo(nodeObj.data) ==0 && this.leftChild.equals(nodeObj.leftChild) 60 && this.rightChild.equals(nodeObj); 61 } 62 return false; 63 } 64 65 public String toString(){ 66 return "[data:"+this.data+"]"; 67 } 68 } 69 70 Node root=null; 71 public SortedBinaryTree() {} 72 public SortedBinaryTree(Node root){ 73 this.root=root; 74 } 75 76 //添加節點 77 public void add(T data){ 78 Node newNode=new Node(data); 79 if(root==null){ 80 root=newNode; 81 }else { 82 add(newNode, root); 83 } 84 } 85 public void add(Node addNode,Node parentNode) { 86 T data=addNode.data; 87 Node currentNode=parentNode; 88 Node parent=null; 89 int flag=0; 90 while(currentNode!=null){ 91 parent=currentNode; 92 flag=data.compareTo(currentNode.data); 93 if(flag>0){ 94 currentNode=currentNode.rightChild; 95 }else { 96 currentNode=currentNode.leftChild; 97 } 98 } 99 if(flag>0){ 100 parent.rightChild=addNode; 101 }else { 102 parent.leftChild=addNode; 103 } 104 addNode.parent=parent; 105 } 106 // 刪除節點 107 public void remove(T data){ 108 if(root==null){ 109 return; 110 }else { 111 Node removeNode=null;//待刪除的節點 112 removeNode = getNode(data); 113 //endregion 114 115 //如果沒有找見拋出異常 116 if(removeNode==null){ 117 throw new RuntimeException("未找見要刪除的節點"); 118 } 119 System.out.println("待刪除的節點為："+removeNode.toString()); 120 //如果待刪除的節點既沒有左孩子也沒有右孩子 121 if(removeNode.leftChild==null && removeNode.rightChild==null){ 122 if(removeNode==root){//如果待刪除的節點就是根節點，即樹中只有一個根節點 123 root=null; 124 }else {//如果待刪除的節點不是根節點，這就要考慮這個節點是其父節點的左孩子還是右孩子 125 if(isLeftNodeOfParent(removeNode)){//如果待刪除是其父節點的左孩子，則斷開其父節點指向左孩子的“指針” 126 removeNode.parent.leftChild=null; 127 }else {//如果待刪除是其父節點的有孩子，則斷開其父節點指向右孩子的“指針” 128 removeNode.parent.rightChild=null; 129 } 130 //【注】斷開他的指向父節點的“指針” 131 //removeNode.parent=null; 132 } 133 }else if (removeNode.leftChild!=null && removeNode.rightChild==null) {//如果待刪除的節點有左孩子但是沒有右孩子 134 if(removeNode==root){//如果待刪除的節點就是根節點 135 136 //這條語句并不是必須的，因為對于數而言，不管怎么都是以root為起點開始所有操作，所以遍歷等操作不會涉及 137 //到root.leftChild.parent.不將它設為null，同樣不影響樹的正常運行。但是root.leftChild.parent所引 138 //用的對象并不會被當成垃圾而被回收，因為從root.leftChild.parent依然可以訪問到該Java對象 139 root.leftChild.parent=null; 140 141 root=root.leftChild; 142 }else {//如果待刪除的節點不是根節點，那就必須討論待刪除的節點是其父節點的左子節點還是右子節點 143 if(isLeftNodeOfParent(removeNode)){ 144 removeNode.parent.leftChild=removeNode.leftChild; 145 }else { 146 removeNode.parent.rightChild=removeNode.leftChild; 147 } 148 //這條語句不要更精煉，加上會讓程序更清晰 149 //removeNode.parent=null; 150 151 152 removeNode.leftChild.parent=removeNode.parent; 153 } 154 //這條語句不要更精煉，加上會讓程序更清晰 155 //removeNode.leftChild=null; 156 } 157 else if (removeNode.leftChild==null && removeNode.rightChild!=null) {//如果待刪除的節點沒有左孩子但是有右孩子 158 if(root==removeNode){//如果待刪除的節點就是根節點 159 root=root.rightChild; 160 //釋放內存，讓垃圾回收removeNode 161 removeNode.rightChild.parent=null; 162 }else {//如果待刪除的節點不是根節點 163 if(isLeftNodeOfParent(removeNode)){ 164 removeNode.parent.leftChild=removeNode.rightChild; 165 }else { 166 removeNode.parent.rightChild=removeNode.rightChild; 167 } 168 removeNode.rightChild.parent=removeNode.parent; 169 170 //這條語句不要更精煉，加上會讓程序更清晰 171 //removeNode.parent=null; 172 } 173 //這條語句不要更精煉，加上會讓程序更清晰 174 //removeNode.rightChild=null; 175 }else {//如果待刪除的節點既有左孩子也有右孩子 176 Node leftMaxNode=null; 177 //region【尋找被刪除節點左子樹中最大節點】 178 Node tmp=removeNode.leftChild; 179 while(tmp.rightChild!=null){ 180 tmp=tmp.rightChild; 181 } 182 leftMaxNode=tmp; 183 //endregion 184 185 System.out.println("leftmaxnode:"+leftMaxNode.toString()); 186 if(removeNode==root){//如果待刪除的節點就是根節點 187 if(leftMaxNode==removeNode.leftChild){//如果被刪除節點的左子樹中最大節點就是其左子節點 188 leftMaxNode.rightChild=root.rightChild; 189 root.rightChild.parent=leftMaxNode; 190 root=leftMaxNode; 191 leftMaxNode.parent=null; 192 193 //這條語句不要更精煉，加上會讓程序更清晰 194 //root.leftChild=null; 195 }else { 196 leftMaxNode.rightChild=root.rightChild; 197 leftMaxNode.leftChild=root.leftChild; 198 199 root.rightChild.parent=leftMaxNode; 200 root.leftChild.parent=leftMaxNode; 201 202 leftMaxNode.parent.rightChild=null; 203 leftMaxNode.parent=null; 204 root=leftMaxNode; 205 } 206 }else {//如果待刪除的節點不是根節點 207 if(leftMaxNode!=removeNode.leftChild){//如果被刪除節點的左子樹中最大節點不是其左子節點 208 Node addNode=removeNode.leftChild; 209 removeNode.leftChild=null; 210 addNode.parent=null; 211 add(addNode,leftMaxNode); 212 leftMaxNode.parent.rightChild=null; 213 } 214 leftMaxNode.rightChild=removeNode.rightChild; 215 removeNode.rightChild.parent=leftMaxNode; 216 217 leftMaxNode.parent=removeNode.parent; 218 219 220 if(isLeftNodeOfParent(removeNode)){ 221 removeNode.parent.leftChild=leftMaxNode; 222 }else { 223 removeNode.parent.rightChild=leftMaxNode; 224 } 225 } 226 } 227 } 228 } 229 230 public Node getNode(T data) { 231 Node removeNode=null; 232 Node current=root;//臨時變量，用于輔助查找待刪除的節點 233 //region 【尋找要待刪除的節點】 234 while(current!=null){ 235 if(data.compareTo(current.data)>0){ 236 current=current.rightChild; 237 }else if (data.compareTo(current.data)<0) { 238 current=current.leftChild; 239 }else { 240 removeNode=current; 241 break; 242 } 243 } 244 return removeNode; 245 } 246 247 private boolean isLeftNodeOfParent(Node node) { 248 return node.data.compareTo(node.parent.data)<=0; 249 } 250 //中序遍歷 251 public List<Node> midIterator(){ 252 return midIterator(root); 253 } 254 private List<Node> midIterator(Node node) { 255 List<Node> list=new ArrayList<Node>(); 256 if(node==null){ 257 return null; 258 } 259 if(node.leftChild!=null){ 260 list.addAll(midIterator(node.leftChild)); 261 } 262 list.add(node); 263 if(node.rightChild!=null){ 264 list.addAll(midIterator(node.rightChild)); 265 } 266 return list; 267 } 268 269 //先序遍歷 270 public List<Node> preIterator(){ 271 return preIterator(root); 272 } 273 private List<Node> preIterator(Node root) { 274 List<Node> list=new ArrayList<Node>(); 275 if(root==null) 276 return null; 277 list.add(root); 278 if(root.leftChild!=null){ 279 list.addAll(preIterator(root.leftChild)); 280 } 281 if(root.rightChild!=null){ 282 list.addAll(preIterator(root.rightChild)); 283 } 284 return list; 285 } 286 287 //廣度優先遍歷 288 public List<Node> breadthFirst(){ 289 return breadthFirst(root); 290 } 291 private List<Node> breadthFirst(Node root) { 292 Queue<Node> queue=new ArrayDeque<Node>(); 293 List<Node> list=new ArrayList<Node>(); 294 if(root==null) 295 return null; 296 queue.offer(root); 297 while(!queue.isEmpty()){ 298 Node node=queue.poll(); 299 list.add(node); 300 if(node.leftChild!=null){ 301 queue.offer(node.leftChild); 302 } 303 if(node.rightChild!=null){ 304 queue.offer(node.rightChild); 305 } 306 } 307 return list; 308 } 309 } View Code

可能有些地方理解的還是不到位，并且代碼的性能不是很高，請大家批評指正。

注：版權所有，轉載請注明出處。

轉載于:https://www.cnblogs.com/yaoyinglong/p/DataStruct%e6%8e%92%e5%ba%8f%e4%ba%8c%e5%8f%89%e6%a0%91.html

總結

以上是生活随笔為你收集整理的一步一图一代码之排序二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。