日本一区二区三区专线,国产精品中文字幕在线,亚洲男人第一无码av网站

排序二叉樹（Search Tree 簡稱BST）：又稱二叉搜索樹，首先是滿足二叉樹，二叉樹就是每個結點最多有2個子結點，其特點是：它的左結點的值必須小于它的根結點的值，它的右結點的值必須大于它的根結點的值，比如5，3，7，1，4，6，8。好了，到了這里我想大家已經對二叉搜索樹有了一定的了解

插入：由于排序二叉樹的定義，其思路也是比較簡單，只要比當前結點小就去找它的左子樹，反之找右子樹，為空的話就把當前值設為改根結點的子節點。

刪除：刪除的話比較復雜，我這邊將情況總結為了3種情況，每次都得需要考慮被刪結點是不是根節點，這個應該很基本的判斷吧。

1.被刪結點是沒有孩子：這個時候，我們可以直接將該結點刪除即可。

2.被刪結點有一個孩子：在這里我們需要判斷一下被刪結點是它的父結點的左孩子還是右孩子，然后將被刪結點的不為空的孩子變成被刪結點的父結點的子孩子

3.被刪結點有兩個孩子：這時候我們有2種方法處理：一種是將被刪結點的左子樹的最右的結點找到，一種是將被刪結點的右子樹的最左結點找到，我這里是寫的是以右子樹的最左結點，其實在這里我們可以簡單理解一下，本身這個排序二叉樹的中序遍歷就是一個遞增的數據，刪除數據之后，無非就是將被刪數據的左邊或者右邊移過去即可，所謂的左子樹的最右結點不就是被刪結點的左邊的數，另外一個情況就是被刪結點的右邊的數，找到這個關系之后，我覺得寫的話就比較簡單，我也在下面的源碼中打了注釋，這里大家可以根據注釋來閱讀，

具體的代碼實現我沒有寫出來了，有思路寫出來應該就問題不大了。

當菜鳥的第6天 2022-04-14，有什么問題希望各位能夠及時指出來。

源碼如下：

  1 package test;
  2 
  3 import javax.swing.text.DefaultEditorKit;
  4 
  5 public class BST{
  6       static class TreeNode {
  7       public int val;
  8       public TreeNode left;
  9       public TreeNode right;
 10       public TreeNode(int x) { val = x; }
 11       }
 12       private TreeNode root;
 13       //排序二叉樹的插入
 14       public void insert(int key){
 15             if(root == null){
 16                   root = new TreeNode(key);
 17                   return ;
 18             }
 19             TreeNode current = root;
 20             TreeNode parent = null;
 21             while(true){
 22                   if(key < current.val)
 23                   {
 24                         parent = current;
 25                         current = parent.left;
 26                         if(current == null){
 27                               parent.left = new TreeNode(key);
 28                               return ;
 29                         }
 30                   }
 31                   else if(key > current.val)
 32                   {
 33                         parent = current;
 34                         current = parent.right;
 35                         if(current == null){
 36                               parent.right = new TreeNode(key);
 37                               return ;
 38                         }
 39                   }
 40                   else {
 41                         System.out.println("該節點值已經存在");
 42                         return ;
 43                   }
 44             }
 45       }
 46       //判斷排序二叉樹中是否存在key
 47       public int get(int key){
 48             TreeNode current = root;
 49             while(current != null && current.val != key){
 50                   if(current.val > key){
 51                         current = current.right;
 52                   }else if(current.val < key){
 53                         current = current.left;
 54                   }
 55             }
 56             return current == null ? 0 : 1;
 57       }
 58       /*
 59       * 排序二叉樹的刪除：
 60       * 三種情況，此處的孩子并不是指葉子節點，也有可能是son tree
 61       * 1.被刪節點沒有孩子:直接將此節點變為null
 62       * 2.被刪節點有一個孩子:將此節點變為父節點的孩子
 63       * 3.被刪節點有兩個孩子:找到右孩子里面最小的節點，然后將此節點移到要刪的節點的位置
 64       * */
 65       public boolean del(int key){
 66             TreeNode parent = root;
 67             TreeNode current = root;
 68             while(current != null && current.val != key)
 69                   //注意，此處不能通過get來實現查找key值是否在樹中，因為需要通過parent節點來實現刪除，如果用key，那么parent就無法來完成刪除
 70             {
 71                   parent = current;
 72                   if(current.val > key)
 73                         current = current.left;
 74                   else
 75                         current = current.right;
 76             }
 77             if(current == null){
 78                   return false;
 79             }
 80             //case1
 81             if(current.left == null && current.right == null)
 82             {
 83                   if(current == root){
 84                         root = null;
 85                   }
 86                   else if(parent.left == current){
 87                         parent.left = null;
 88                   }
 89                   else parent.right = null;
 90             }
 91             //case2:
 92             else if(current.left == null){
 93                   if(current == root){
 94                         root = root.right;
 95                   }
 96                   else if(parent.left == current){
 97                         parent.left = current.right;
 98                   }
 99                   else parent.right = current.right;
100             }
101             else if(current.right == null){
102                   if(current == root){
103                         root = root.left;
104                   }
105                   else if(parent.left == current){
106                         parent.left = current.left;
107                   }
108                   else parent.right = current.left;
109             }
110             //case3
111             else{
112                   TreeNode Minr = MinrTree(current);
113                   if(current == root)
114                   {
115                         root = Minr;
116                   }
117                   else if(parent.left == current){
118                         parent.left = Minr;
119                   }
120                   else parent.right = Minr;
121             }
122       }
123       //此方法來找出右子樹的最小節點
124       public TreeNode MinrTree(TreeNode root){
125             TreeNode rTree = null;
126             TreeNode rTreeParent = null;
127             TreeNode node = root.right;
128             while(node != null){
129                   rTreeParent = rTree;
130                   rTree = node;
131                   node = node.left;
132             }
133             if(rTree != root.right){
134                   rTreeParent.left = rTree.right;
135                   rTree.right = root.right;
136             }
137             return rTree;
138       }
139 }

posted on 2022-04-14 15:42 小小小噠大閱讀(83) 評論(0) 收藏舉報

刷新頁面返回頂部