二叉排序树的添加与删除

二叉排序树

百度百科：

　　叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点

二叉排序树的创建与中序遍历：

1、先创建树的节点

/**
 * 树节点
 */
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    /**
     * 二叉排序树的添加
     *
     * @param node
     */
    public void addNode(Node node) {
        if (node == null) {
            return;
        }
        // 判断传进来的节点值与当前节点的关系
        if (node.value < this.value) {
            // 左子节点为null
            if (this.left == null) {
                this.left = node;
            } else {
                // 递归的向左子树添加节点
                this.left.addNode(node);
            }
        } else { // 传入的节点大于等于当前节点
            if (this.right == null) {
                this.right = node;
            } else {
                // 递归的向右子树添加节点
                this.right.addNode(node);
            }
        }

    }

    /**
     * 二叉排序树的中序遍历
     */
    void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}

2、创建二叉树

/**
 * 创建二叉排序树
 */
class BinarySortTree {
    private Node root;

    /**
     * 添加节点的方法
     *
     * @param node
     */
    public void addNode(Node node) {
        // root节点为空，就让root成为根节点
        if (root == null) {
            root = node;
        } else {// root节点不为空,就继续向树中添加节点
            root.addNode(node);
        }
    }

    /**
     * 进行中序遍历
     */
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法进行排序！");
        }
    }
}

3、进行测试

public class BinarySearchTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        BinarySortTree binarySortTree = new BinarySortTree();

        // 向二叉树中添加节点
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.addNode(new Node(arr[i]));
        }

        // 中序遍历排序结果
        binarySortTree.infixOrder();
    }
}

4、测试结果（中序遍历）

Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}

二叉排序树的删除

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑

1) 删除叶子节点 (比如：2, 5, 9, 12)
2) 删除只有一颗子树的节点 (比如：1)
3) 删除有两颗子树的节点. (比如：7, 3，10 )

(1)删除叶子节点：

删除思路：

　　删除叶子节点 (比如：2, 5, 9, 12)

(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的父结点 parent
(3) 确定 targetNode 是 parent 的左子结点还是右子结点
(4) 根据前面的情况来对应删除左子结点 parent.left = null 右子结点 parent.right = null;

code

1、先在Node类中查找到要删除节点和要删除节点的父节点

/**
 * 查找到要删除的节点
 *
 * @param value 希望删除节点的值
 * @return 找到了就返回这个要删除的节点，没有找到就返回null
 */
public Node delSearch(int value) {
    // 找到的就是要删除的节点
    if (value == this.value) {
        return this;
    } else if (value < this.value) {
        /**向左子节点查找*/
        if (this.left == null) {
            return null;
        }
        // 继续递归查找
        return this.left.delSearch(value);
    } else {// 要删除节点的值是大于等于当前节点的值
        if (this.right == null) {
            return null;
        }
        return this.right.delSearch(value);
    }
}
/**
 * 查找到要删除节点的父节点
 *
 * @param value 要删除的节点的值
 * @return 找到就返回要删除节点的父节点，没有找到就返回null
 */
public Node delSearchParent(int value) {
    // 如果当前节点就是要删除的节点的父节点，就返回
    if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == 
        return this;
    } else {
        // 满足条件表示向左递归查找
        if (this.left != null && value < this.value) {
            // 向左子树递归找到就返回
            return this.left.delSearchParent(value);
        } else if (this.right != null && value >= this.value) {
            // 向右子树递归找到就返回
            return this.right.delSearchParent(value);
        } else {
            // 没有找到要删除节点的父节点
            return null;
        }
    }
}

2、在BinarySortTree类中编写查找要删除节点跟要删除节点父节点的方法

 /**
  * 查找要删除的节点
  *
  * @param value
  * @return
  */
 public Node delSearch(int value) {
     if (root == null) {
         return null;
     } else {
         return root.delSearch(value);
     }
 }
 /**
  * 查找到要删除节点的父节点
  *
  * @param value
  * @return
  */
 public Node delSearchParent(int value) {
     if (root == null) {
         return null;
     } else {
         return root.delSearchParent(value);
     }
 }

3、在BinarySortTree类中编写删除节点的方法

/**
 * 删除节点
 *
 * @param value
 */
public void delNode(int value) {
    if (root == null) {
        return;
    } else {
        // 1、找到要删除的节点
        Node targetNode = delSearch(value);
        // 没有找到
        if (targetNode == null) {
            return;
        }
        // 表示这颗二叉排序树只有一个节点(父节点)
        if (root.left == null && root.right == null) {
            root = null;
            return;
        }
        // 2、找到要删除节点的父节点
        Node parentNode = delSearchParent(value);
        // 表示要删除的节点是一个叶子节点
        if (targetNode.left == null && targetNode.right == null) {
            // 继续判断这个叶子节点是父节点的左子节点还是右子节点
            if (parentNode.left != null && parentNode.left.value == value) {
                // 将这个叶子节点置为空
                parentNode.left = null;
            } else if (parentNode.right != null && parentNode.right.value == value) {
                parentNode.right = null;
            }
        }
    }

4、测试

public static void main(String[] args) {
    int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
    BinarySortTree binarySortTree = new BinarySortTree();
    // 向二叉树中添加节点
    for (int i = 0; i < arr.length; i++) {
        binarySortTree.addNode(new Node(arr[i]));
    }
    // 中序遍历排序结果
    binarySortTree.infixOrder();
    // 删除节点
    binarySortTree.delNode(2);
    binarySortTree.delNode(5);
    binarySortTree.delNode(9);
    // 删除叶子节点后的中序遍历结果是
    System.out.println("删除后:");
    binarySortTree.infixOrder();
}

5、测试结果

Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除后:
Node{value=1}
Node{value=3}
Node{value=7}
Node{value=10}
Node{value=12}

(2)删除只有一颗子树的节点

思路

(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的父结点 parent
(3) 确定 targetNode 的子结点是左子结点还是右子结点
(4) targetNode 是 parent 的左子结点还是右子结点
(5) 如果 targetNode 有左子结点
- 5. 1 如果 targetNode 是 parent 的左子结点parent.left = targetNode.left;
- 5.2 如果 targetNode 是 parent 的右子结点 parent.right = targetNode.left;
(6) 如果 targetNode 有右子结点
- 6.1 如果 targetNode 是 parent 的左子结点 parent.left = targetNode.right;
- 6.2 如果 targetNode 是 parent 的右子结点 parent.right = targetNode.right

code　　

在delNode中添加：

/**
 * 删除节点
 *
 * @param value
 */
public void delNode(int value) {
    if (root == null) {
        return;
    } else {
        // 1、找到要删除的节点
        Node targetNode = delSearch(value);
        // 没有找到
        if (targetNode == null) {
            return;
        }
        // 表示这颗二叉排序树只有一个节点(父节点)
        if (root.left == null && root.right == n
            root = null;
            return;
        }
        // 2、找到要删除节点的父节点
        Node parentNode = delSearchParent(value)
        // 表示要删除的节点是一个叶子节点
        if (targetNode.left == null && targetNod
            // 继续判断这个叶子节点是父节点的左子节点还是右子节点
            if (parentNode.left != null && paren
                // 将这个叶子节点置为空
                parentNode.left = null;
            } else if (parentNode.right != null 
                parentNode.right = null;
            }
        } else if (targetNode.left != null && ta
        } else {// 删除只有一颗子树的节点
            if (targetNode.left != null) {// 如果要
                // 待删除节点是父节点的左子节点
                if (parentNode.left.value == val
                    parentNode.left = targetNode
                } else {// 待删除节点是父节点的右子节点
                    parentNode.right = targetNod
                }
            } else {// 如果要删除的节点有右子节点
                // 待删除节点是父节点的左子节点
                if (parentNode.left.value == val
                    parentNode.left = targetNode
                } else {// 待删除节点是父节点的右子节点
                    parentNode.right = targetNod
                }
            }
        }
    }
}

测试删除1号节点(只有1棵子树的节点)：

成功！　

Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除后:
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}

(3) 删除有两颗子树的节点. (比如：7, 3，10 )

思路：

(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的父结点 parent
(3) 从 targetNode 的右子树找到最小的结点
(4) 用一个临时变量，将最小结点的值保存 temp = 11
(5) 删除该最小结点
(6) targetNode.value = temp

code：

编写一个方法，从右边找到最小值：

/**
 * 找到最小值并删除
 *
 * @param node
 * @return 返回删除节点的值
 */
public int delRightTreeMin(Node node) {
    // 作一个辅助节点
    Node target = node;
    // 循环往左子树进行查找，就会找到最小值
    while (target.left != null) {
        target = target.left;
    }
    // 删除最小值
    delNode(target.value);
    // 返回最小值
    return target.value;
}

在delNode中添加：

测试：删除7号节点

Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除后:
Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=9}
Node{value=10}
Node{value=12}

最终代码：

  1 package Demo10_二叉排序树;
  2 
  3 /**
  4  * @author zhangzhixi
  5  * @date 2021/3/3 15:15
  6  */
  7 public class BinarySearchTreeDemo {
  8     public static void main(String[] args) {
  9         int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
 10         BinarySortTree binarySortTree = new BinarySortTree();
 11 
 12         // 向二叉树中添加节点
 13         for (int i = 0; i < arr.length; i++) {
 14             binarySortTree.addNode(new Node(arr[i]));
 15         }
 16 
 17         // 中序遍历排序结果
 18         binarySortTree.infixOrder();
 19 
 20         // 删除节点
 21         binarySortTree.delNode(7);
 22         binarySortTree.delNode(9);
 23         binarySortTree.delNode(2);
 24         binarySortTree.delNode(12);
 25         binarySortTree.delNode(5);
 26         binarySortTree.delNode(3);
 27         binarySortTree.delNode(1);
 28         binarySortTree.delNode(10);
 29 
 30         // 删除叶子节点后的中序遍历结果是
 31         System.out.println("删除后:");
 32         binarySortTree.infixOrder();
 33     }
 34 }
 35 
 36 /**
 37  * 创建二叉排序树
 38  */
 39 class BinarySortTree {
 40     private Node root;
 41 
 42     public Node getRoot() {
 43         return root;
 44     }
 45 
 46     /**
 47      * 查找要删除的节点
 48      *
 49      * @param value
 50      * @return
 51      */
 52     public Node delSearch(int value) {
 53         if (root == null) {
 54             return null;
 55         } else {
 56             return root.delSearch(value);
 57         }
 58     }
 59 
 60     /**
 61      * 查找到要删除节点的父节点
 62      *
 63      * @param value
 64      * @return
 65      */
 66     public Node delSearchParent(int value) {
 67         if (root == null) {
 68             return null;
 69         } else {
 70             return root.delSearchParent(value);
 71         }
 72     }
 73 
 74     /**
 75      * 找到最小值并删除
 76      *
 77      * @param node
 78      * @return 返回删除节点的值
 79      */
 80     public int delRightTreeMin(Node node) {
 81         // 作一个辅助节点
 82         Node target = node;
 83         // 循环往左子树进行查找，就会找到最小值
 84         while (target.left != null) {
 85             target = target.left;
 86         }
 87         // 删除最小值
 88         delNode(target.value);
 89         // 返回最小值
 90         return target.value;
 91     }
 92 
 93     /**
 94      * 删除节点
 95      *
 96      * @param value
 97      */
 98     public void delNode(int value) {
 99         if (root == null) {
100             return;
101         } else {
102             // 1、找到要删除的节点
103             Node targetNode = delSearch(value);
104             // 没有找到
105             if (targetNode == null) {
106                 return;
107             }
108             // 表示这颗二叉排序树只有一个节点(父节点)
109             if (root.left == null && root.right == null) {
110                 root = null;
111                 return;
112             }
113 
114             // 2、找到要删除节点的父节点
115             Node parentNode = delSearchParent(value);
116             // 表示要删除的节点是一个叶子节点
117             if (targetNode.left == null && targetNode.right == null) {
118                 // 继续判断这个叶子节点是父节点的左子节点还是右子节点
119                 if (parentNode.left != null && parentNode.left.value == value) {
120                     // 将这个叶子节点置为空
121                     parentNode.left = null;
122                 } else if (parentNode.right != null && parentNode.right.value == value) {
123                     parentNode.right = null;
124                 }
125             } else if (targetNode.left != null && targetNode.right != null) {// 删除有两颗子树的节点
126                 // 找到最小值
127                 int minVal = delRightTreeMin(targetNode.right);
128                 // 重置
129                 targetNode.value = minVal;
130             } else {// 删除只有一颗子树的节点
131                 if (targetNode.left != null) {// 如果要删除的节点有左子节点
132                     if (parentNode != null) {
133                         // 待删除节点是父节点的左子节点
134                         if (parentNode.left.value == value) {
135                             parentNode.left = targetNode.left;
136                         } else {// 待删除节点是父节点的右子节点
137                             parentNode.right = targetNode.left;
138                         }
139                     } else {
140                         root = targetNode.left;
141                     }
142                 } else {// 如果要删除的节点有右子节点
143                     if (parentNode != null) {
144                         // 待删除节点是父节点的左子节点
145                         if (parentNode.left.value == value) {
146                             parentNode.left = targetNode.right;
147                         } else {// 待删除节点是父节点的右子节点
148                             parentNode.right = targetNode.right;
149                         }
150                     } else {
151                         root = targetNode.right;
152                     }
153                 }
154             }
155         }
156     }
157 
158     /**
159      * 添加节点的方法
160      *
161      * @param node
162      */
163     public void addNode(Node node) {
164         // root节点为空，就让root成为根节点
165         if (root == null) {
166             root = node;
167         } else {// root节点不为空,就继续向树中添加节点
168             root.addNode(node);
169         }
170     }
171 
172     /**
173      * 进行中序遍历
174      */
175     public void infixOrder() {
176         if (root != null) {
177             root.infixOrder();
178         } else {
179             System.out.println("二叉树为空，无法进行排序！");
180         }
181     }
182 }
183 
184 /**
185  * 树节点
186  */
187 class Node {
188     int value;
189     Node left;
190     Node right;
191 
192     public Node(int value) {
193         this.value = value;
194     }
195 
196     @Override
197     public String toString() {
198         return "Node{" +
199                 "value=" + value +
200                 '}';
201     }
202 
203     /**
204      * 查找到要删除的节点
205      *
206      * @param value 希望删除节点的值
207      * @return 找到了就返回这个要删除的节点，没有找到就返回null
208      */
209     public Node delSearch(int value) {
210         // 找到的就是要删除的节点
211         if (value == this.value) {
212             return this;
213         } else if (value < this.value) {
214             /**向左子节点查找*/
215             if (this.left == null) {
216                 return null;
217             }
218             // 继续递归查找
219             return this.left.delSearch(value);
220         } else {// 要删除节点的值是大于等于当前节点的值
221             if (this.right == null) {
222                 return null;
223             }
224             return this.right.delSearch(value);
225         }
226     }
227 
228     /**
229      * 查找到要删除节点的父节点
230      *
231      * @param value 要删除的节点的值
232      * @return 找到就返回要删除节点的父节点，没有找到就返回null
233      */
234     public Node delSearchParent(int value) {
235         // 如果当前节点就是要删除的节点的父节点，就返回
236         if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
237             return this;
238         } else {
239             // 满足条件表示向左递归查找
240             if (this.left != null && value < this.value) {
241                 // 向左子树递归找到就返回
242                 return this.left.delSearchParent(value);
243             } else if (this.right != null && value >= this.value) {
244                 // 向右子树递归找到就返回
245                 return this.right.delSearchParent(value);
246             } else {
247                 // 没有找到要删除节点的父节点
248                 return null;
249             }
250         }
251     }
252 
253     /**
254      * 二叉排序树的添加
255      *
256      * @param node
257      */
258     public void addNode(Node node) {
259         if (node == null) {
260             return;
261         }
262         // 判断传进来的节点值与当前节点的关系
263         if (node.value < this.value) {
264             // 左子节点为null
265             if (this.left == null) {
266                 this.left = node;
267             } else {
268                 // 递归的向左子树添加节点
269                 this.left.addNode(node);
270             }
271         } else { // 传入的节点大于等于当前节点
272             if (this.right == null) {
273                 this.right = node;
274             } else {
275                 // 递归的向右子树添加节点
276                 this.right.addNode(node);
277             }
278         }
279 
280     }
281 
282     /**
283      * 二叉排序树的中序遍历
284      */
285     void infixOrder() {
286         if (this.left != null) {
287             this.left.infixOrder();
288         }
289         System.out.println(this);
290         if (this.right != null) {
291             this.right.infixOrder();
292         }
293     }
294 }