2023年6月22日发(作者：)

⼆叉排序树的删除节点步骤：⾸先，我们先从根节点开始查找到要删除的这个节点，然后删除该节点，然后再妥善安置该该节点的⼦树或⼦节点。要删除的节点分为三种情况：1，当要删除的节点的是叶⼦结点的时候；2，当要删除的节点只有⼀个⼦节点或⼦树的时候；3，当要删除的节点同时有左右两棵⼦树的时候。对于第⼀种情况，要删除的节点是叶⼦结点的时候，删除的办法是直接删除掉该节点即可；对于第⼆种情况，要删除的节点有⼀个⼦节点或⼦树的时候，删除的办法是先将该节点删除，然后将它的⼦节点或⼦树直接挪到该节点的位置即可。对于第三种情况，要删除的节点同时有左右两颗⼦树的时候，删除的办法是分为两种情况：1，先找到右⼦树中最⼩的那个节点、或者左⼦树中最⼤的那个节点，然后删除该删除的节点，然后将右⼦树中最⼩的那个节点或者左⼦树中最⼤的那个节点，挪到删除的位置即可。2，如果右⼦树中最⼩的那个节点有⼀个右⼦节点，或者左⼦树中最⼤的那个节点有⼀个左⼦结点，此时删除的办法是：先删除该删除的节点，然后将右⼦树中最⼩的那个节点或者左⼦树中最⼤的那个节点，挪到删除的位置，然后将右⼦树中最⼩的那个节点的右⼦节点，或者左⼦树中最⼤的那个节点的左⼦结点，挪到右⼦树中最⼩的那个节点、或者左⼦树中最⼤的那个节点的位置即可。3，如果右⼦树中最⼩的那个节点有左右两个节点，或者左⼦树中最⼤的那个节点有左右两个结点，这种情况是不可能的，因为此时右⼦树中最⼩的那个节点肯定就是该节点的左⼦结点了，左⼦树中最⼤的那个节点肯定就是该节点的右⼦节点了。写不下去、烂尾的代码... /** * 删除节点： * @param rootNode：根节点，⽤来找到指定的要删除的节点 * @param value：要删除的节点的值 */ public void deleteLeafNode(BinaryTreeNode rootNode, int value) { //1，寻找该节点： if (null == rootNode) { return; } else { BinaryTreeNode leftNode = tNode(); BinaryTreeNode rightNode = htNode(); if (leftNode != null) { if (eValue() == value) { //1，如果该节点是叶⼦结点：—— 则直接删除该节点 if (null == tNode() && null == htNode()) { tNode(null); } //2，如果该节点有⼀个⼦节点/⼦树：——先删除该节点，然后将其⼦节点上位挪到该节点的位置； if (null == tNode() && null != htNode()) { tNode(htNode()); } else if (null != tNode() && null == htNode()) { tNode(tNode()); } //3，如果该节点有两个⼦节点/⼦树：——先删除该节点，然后将其该节点的左⼦树的最⼤节点或者右⼦树的最⼩节点上位挪到该节点的位置； if (null != tNode() && null != htNode()) { //以将该节点的右⼦树的最⼩节点上位为例： BinaryTreeNode leftNodeRightNode = htNode(); BinaryTreeNode minNode = qryRightChildMinNode(leftNodeRightNode); //3.1，如果该节点的右⼦树的最⼩节点为叶⼦结点，则直接上位挪到该节点的位置即可； //3.2，如果该节点的右⼦树的最⼩节点有⼀个右⼦节点， // 则先将这个右⼦树的最⼩节点上位到该节点的位置， // 然后将这个右⼦树的最⼩节点的右⼦节点上位到这个右⼦树的最⼩节点的位置； //写不下去了，就这吧... } } } if (rightNode != null) { } } } /** * 查找该节点的右⼦树中的最⼩节点： * @param node 该节点的右⼦节点 */ BinaryTreeNode minBinaryTreeNode = null; public BinaryTreeNode qryRightChildMinNode(BinaryTreeNode node) { if (null == node) { return minBinaryTreeNode; } else { minBinaryTreeNode = node; BinaryTreeNode leftNode = tNode(); BinaryTreeNode rightNode = htNode(); minBinaryTreeNode = eValue() < eValue() ? leftNode : minBinaryTreeNode; minBinaryTreeNode = eValue() < eValue() ? rightNode : minBinaryTreeNode; qryRightChildMinNode(leftNode); qryRightChildMinNode(leftNode); } return minBinaryTreeNode; }