二叉树的删除

有序二叉树的删除

三种删除模式：

1、删除叶子节点

（1）找到要删除的叶子节点trageNode

（2）找到目标结点的父节点parentNode（考虑是否有父节点）

（3）找到删除的节点是父节点的左子树还是右子树

（4）根据前面的情况进行删除

左子树：parent.left = null

右子树：parent.right = nul

2、删除只有一个子树的节点

（1）找到要删除的叶子节点trageNode

（2）找到目标结点的父节点parentNode（考虑是否有父节点）

（3）找到删除的节点是父节点的左子树还是右子树

（4）确定删除的节点是有左子树还是右子树

（5）根据前边的情况进行删除

1）targetNode是左子树

【1】targetNode有左子树 parent.left = target.left

【2】targetNode有右子树 parent.left= target.right

2）targetNode是右子树

【1】targetNode有左子树 parent.right = target.left

【2】targetNode有右子树 parent.right= target.right

3、删除有两个子树的节点

（1）找到要删除的叶子节点trageNode

（2）找到目标结点的父节点parentNode（考虑是否有父节点）

（3）找到删除节点右子树当中最小的或找到左子树当中最大的

（4）将右子树当中最大的值替换掉删除节点的值

（5）使用删除叶子节点的逻辑，删除最小值

下面来看一下代码段的实现

1.  
   /**
2.  
   * 找到被删除的节点
3.  
   * @param node 树
4.  
   * @param value 删除节点的值
5.  
   * @return
6.  
   */
7.  
   public TreeNode Search(TreeNode node,int value){
8.  
   if (root == null){
9.  
   return null;
10.  
    }
11.  
     
12.  
    //判断node当前所指向的节点是不是要删除的节点
13.  
    if (node.value == value){
14.  
    return node;
15.  
    }else if(value<node.value){
16.  
    if (node.leftChild == null){
17.  
    return null;
18.  
    }
19.  
    return Search(node.leftChild,value);
20.  
    }else {
21.  
    if (node.rightChild == null){
22.  
    return null;
23.  
    }
24.  
    return Search(node.rightChild,value);
25.  
    }
26.  
     
27.  
    }
28.  
     
29.  
    /**
30.  
    * 找打删除节点的父节点
31.  
    * @param node 树
32.  
    * @param value 删除的值
33.  
    * @return
34.  
    */
35.  
    public TreeNode SearchParent(TreeNode node,int value){
36.  
    if (root == null){
37.  
    return null;
38.  
    }
39.  
     
40.  
    //判断我们当前的节点的左或右孩子是不是我们要删除的值
41.  
    if ((node.leftChild != null && node.leftChild.value == value) || (node.rightChild != null && node.rightChild.value == value) ){
42.  
    return node;
43.  
    }else {
44.  
    // 往左走
45.  
    if (node.leftChild !=null && value < node.value){
46.  
    return SearchParent(node.leftChild,value);
47.  
    }else if(node.rightChild !=null && value > node.value){
48.  
    //向右走
49.  
    return SearchParent(node.rightChild,value);
50.  
    }else {
51.  
    return null; //没有父节点
52.  
    }
53.  
    }
54.  
     
55.  
    }
56.  
     
57.  
    public int SearchRightMin(TreeNode node){
58.  
    //定义一个指针
59.  
    TreeNode tempNode = node;
60.  
    while (tempNode.leftChild !=null){
61.  
    tempNode = tempNode.leftChild;
62.  
    }
63.  
    delete(root,tempNode.value); // 删除的左子树当中的最小值
64.  
    return tempNode.value;
65.  
    }
66.  
     
67.  
    /**
68.  
    * 删除方法
69.  
    * @param node
70.  
    * @param value
71.  
    */
72.  
    public void delete(TreeNode node,int value){
73.  
    if (node == null){
74.  
    return;
75.  
    }
76.  
    // 1.找到删除的节点
77.  
    TreeNode targetNode = Search(node,value);
78.  
    // 2.如果没有删除的节点
79.  
    if (targetNode == null){
80.  
    System.out.println("没有删除的节点");
81.  
    return;
82.  
    }
83.  
     
84.  
    //如果这颗树只有一个节点
85.  
    if (node.leftChild == null && node.rightChild == null){
86.  
    root = null;
87.  
    return;
88.  
    }
89.  
     
90.  
     
91.  
    //3.找到targetNode的父节点
92.  
    TreeNode parentNode = SearchParent(node,value);
93.  
     
94.  
    //删除的节点是叶子节点
95.  
    if (targetNode.rightChild == null && targetNode.leftChild == null){
96.  
    if (parentNode.leftChild !=null && parentNode.leftChild.value == targetNode.value){
97.  
    parentNode.leftChild = null;
98.  
    }else if (parentNode.rightChild !=null && parentNode.rightChild.value == targetNode.value){
99.  
    parentNode.rightChild = null;
100.  
     }
101.  
     }else if(targetNode.rightChild!=null && targetNode.leftChild !=null){ //删除的是有两个子树的节点
102.  
     //找到删除节点右子树当中最小的
103.  
     int minValue = SearchRightMin(targetNode.rightChild);
104.  
     targetNode.value = minValue;
105.  
     }else { //删除只有一个子树的节点
106.  
     //如果删除的节点有左子树
107.  
     if (targetNode.leftChild !=null){
108.  
     if (parentNode.leftChild.value == targetNode.value){ //删除的节点是父节的左子树
109.  
     parentNode.leftChild = targetNode.leftChild;
110.  
     }else {//删除的节点是父节的右子树
111.  
     parentNode.rightChild = targetNode.leftChild;
112.  
     }
113.  
     }else {
114.  
     if (parentNode.leftChild.value == targetNode.value){
115.  
     parentNode.leftChild = targetNode.rightChild;
116.  
     }else {
117.  
     parentNode.rightChild = targetNode.rightChild;
118.  
     }
119.  
     }
120.  
     }
121.  
      
122.  
     }
123.  
      

这篇好文章是转载于：学新通技术网