二叉搜索樹(shù)刪除節(jié)點(diǎn)分三種情況:
- 被刪除節(jié)點(diǎn)沒(méi)有子樹(shù)的情況遏片，直接刪除，并修改對(duì)應(yīng)父節(jié)點(diǎn)的指針為空顽爹。
- 對(duì)于只有一個(gè)子樹(shù)的情況，考慮將其子樹(shù)作為其父節(jié)點(diǎn)的子樹(shù)骆姐，關(guān)于是左還是右镜粤，根據(jù)被刪除的節(jié)點(diǎn)確定捏题。
- 被刪除節(jié)點(diǎn)有左右孩子,可以從它的左子樹(shù)找到最大的節(jié)點(diǎn),然后被刪除節(jié)點(diǎn)的值替換為左子樹(shù)最大節(jié)點(diǎn)的值.最后把左子書(shū)最大節(jié)點(diǎn)刪除.也可以對(duì)右子樹(shù)最小節(jié)點(diǎn)做操作.
此外,還需要考慮別刪除的節(jié)點(diǎn)是根節(jié)點(diǎn)或者被刪除節(jié)點(diǎn)不存在,如果需要修改根節(jié)點(diǎn),還要修改樹(shù)根節(jié)點(diǎn)的引用.
BinarySortTree.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* 二叉排序樹(shù)
*/
public class BinarySortTree<T extends Comparable<? super T>> {
//根節(jié)點(diǎn)
private Node root;
public Node getRoot() {
return root;
}
//二叉樹(shù)節(jié)點(diǎn)
class Node {
T val;
Node left;
Node right;
int count = 1;
Node(T val) {
this.val = val;
}
}
/**
* 層次遍歷
* 用一個(gè)鏈表保存節(jié)點(diǎn),每次從前面取節(jié)點(diǎn),同時(shí)把該節(jié)點(diǎn)的左右節(jié)點(diǎn)加入鏈表尾部
*
* @return 每個(gè)List表示一層元素
*/
public List<List<T>> levelTraverse() {
List<List<T>> res = new ArrayList<>();
if (root == null) {
return res;
}
LinkedList<Node> list = new LinkedList<>();
list.push(root);
while (!list.isEmpty()) {
//當(dāng)前層元素?cái)?shù)量
int size = list.size();
List<T> nowLevelElemts = new ArrayList<>();
while (size-- > 0) {
Node node = list.removeFirst();
nowLevelElemts.add(node.val);
if (node.left != null) {
list.addLast(node.left);
}
if (node.right != null) {
list.addLast(node.right);
}
}
res.add(nowLevelElemts);
}
return res;
}
/**
* 插入
*/
public void insert(T val) {
if (root == null) {
root = new Node(val);
return;
}
//找到的位置
Node parentNode = root;
Node curNode = root;
while (curNode != null) {
parentNode = curNode;
if (val.compareTo(curNode.val) < 0) {
curNode = curNode.left;
} else if (val.compareTo(curNode.val) > 0) {
curNode = curNode.right;
} else {
//已經(jīng)存在val了
curNode.count++;
return;
}
}
//插入新節(jié)點(diǎn)
if (val.compareTo(parentNode.val) < 0) {
parentNode.left = new Node(val);
}
if (val.compareTo(parentNode.val) > 0) {
parentNode.right = new Node(val);
}
}
/**
* 查找指定值的父節(jié)點(diǎn)
*
* @return 找不到返回null, 找到則返回父節(jié)點(diǎn)
*/
private Node findParent(Node root, T val) {
if (root == null || val.equals(root.val)) {
return null;
}
Node res = root;
while (root != null) {
if (root.val.equals(val)) {
break;
} else if (val.compareTo(root.val) > 0) {
res = root;
root = root.right;
} else {
res = root;
root = root.left;
}
}
return root == null ? null : res;
}
public boolean delNode(T val) {
if (val.equals(root.val)) {
delNode(root);
return true;
}
//得到val的父節(jié)點(diǎn)
Node parent = findParent(root, val);
//val不存在
if (parent == null) {
return false;
}
return delNode(parent, parent.left.val.equals(val) ? parent.left : parent.right);
}
/**
* @param parent 要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)
* @param p 要?jiǎng)h除的節(jié)點(diǎn)
* @return 刪除成功返回true, 否則返回false
*/
private boolean delNode(Node parent, Node p) {
if (parent == null) {
throw new NullPointerException();
}
if (p == null) {
return true;
}
if (parent.left != p && parent.right != p) {
return false;
}
//p沒(méi)有孩子節(jié)點(diǎn),直接刪除
if (p.left == null && p.right == null) {
if (parent.left == p) {
parent.left = null;
} else {
parent.right = null;
}
//p只有一個(gè)孩子節(jié)點(diǎn),讓p的父節(jié)點(diǎn)指向p的孩子節(jié)點(diǎn)
} else if (p.left == null || p.right == null) {
if (parent.left == p) {
parent.left = (p.left == null ? p.right : p.left);
} else {
parent.right = (p.left == null ? p.right : p.left);
}
//p有兩個(gè)孩子節(jié)點(diǎn)時(shí),找到p的左字樹(shù)中最大的節(jié)點(diǎn),p賦值為左字樹(shù)中最大的節(jié)點(diǎn)的值,
//同時(shí)刪除左字樹(shù)中最大的節(jié)點(diǎn)
} else {
parent = p;
Node leftMaxNode = p.left;
while (leftMaxNode.right != null) {
parent = leftMaxNode;
leftMaxNode = leftMaxNode.right;
}
p.val = leftMaxNode.val;
//如果p的左孩子沒(méi)有孩子節(jié)點(diǎn),parent就是p,parent的左孩子就是左邊最大的節(jié)點(diǎn)
if (parent.left == leftMaxNode) {
parent.left = leftMaxNode.left;
} else {
parent.right = leftMaxNode.left;
}
}
return true;
}
/**
* 尋找二叉樹(shù)最大節(jié)點(diǎn)
*
* @param root
* @return
*/
public Node findMaxNode(Node root) {
if (root == null) {
return null;
}
//一直往右邊走就對(duì)了
Node res = root;
while (res.right != null) {
res = res.right;
}
return res;
}
/**
* 尋找二叉樹(shù)最小節(jié)點(diǎn)
*
* @param root
* @return
*/
public Node findMinNode(Node root) {
if (root == null) {
return null;
}
//一直往左邊走就對(duì)了
Node res = root;
while (res.left != null) {
res = res.left;
}
return res;
}
private boolean delNode(Node p) {
if (p == null) {
return true;
}
//要?jiǎng)h除的節(jié)點(diǎn)為根節(jié)點(diǎn)
if (p == root) {
//找到左子樹(shù)最大的節(jié)點(diǎn)
if (p.left != null) {
Node parent = p;
Node leftMaxNode = p.left;
while (leftMaxNode.right != null) {
parent = leftMaxNode;
leftMaxNode = leftMaxNode.right;
}
p.val = leftMaxNode.val;
if (parent.left == leftMaxNode) {
parent.left = leftMaxNode.left;
} else {
parent.right = leftMaxNode.left;
}
//找右子樹(shù)最小的節(jié)點(diǎn)
} else if (p.right != null) {
Node parent = p;
Node rightMinNode = p.right;
while (rightMinNode.left != null) {
parent = rightMinNode;
rightMinNode = rightMinNode.left;
}
p.val = rightMinNode.val;
if (parent.right == rightMinNode) {
parent.right = rightMinNode.right;
} else {
parent.left = rightMinNode.right;
}
//都找不到,意味著二叉樹(shù)只有一個(gè)節(jié)點(diǎn)
} else {
this.root = null;
}
return true;
}
Node pParent = findParent(root, p.val);
//不存在p的父節(jié)點(diǎn),那也不存在節(jié)點(diǎn)p
if (pParent == null) {
return false;
}
return delNode(pParent, p);
}
}
TreeTest.java
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.List;
import java.util.Scanner;
public class TreeTest {
public static void main(String[] args) {
BinarySortTree<Integer> tree = new BinarySortTree<>();
//input.txt的內(nèi)容為:
//15 5 3 12 16 20 23 13 18 10 6 7
Scanner in = getScanner("input.txt");
//測(cè)試插入元素
while (in.hasNext()) {
tree.insert(in.nextInt());
}
//測(cè)試刪除元素
testDelete(tree);
}
private static void testDelete(BinarySortTree<Integer> tree) {
//層次遍歷元素
List<List<Integer>> elements = tree.levelTraverse();
System.out.println(elements);
//測(cè)試刪除根節(jié)點(diǎn)
// tree.delNode(tree.getRoot().val);
// elements = tree.levelTraverse();
// System.out.println(elements);
//測(cè)試刪除帶兩個(gè)孩子節(jié)點(diǎn)的節(jié)點(diǎn)
// tree.delNode(5);
// elements = tree.levelTraverse();
// System.out.println(elements);
// //測(cè)試刪除帶左孩子節(jié)點(diǎn)的節(jié)點(diǎn)
// tree.delNode(10);
// elements = tree.levelTraverse();
// System.out.println(elements);
//測(cè)試刪除帶右孩子節(jié)點(diǎn)的節(jié)點(diǎn)
// tree.delNode(16);
// elements = tree.levelTraverse();
// System.out.println(elements);
//測(cè)試刪除沒(méi)有孩子子節(jié)點(diǎn)的節(jié)點(diǎn)
// tree.delNode(18);
// elements = tree.levelTraverse();
// System.out.println(elements);
//測(cè)試刪除不存在的節(jié)點(diǎn)
// tree.delNode(181);
// elements = tree.levelTraverse();
// System.out.println(elements);
}
//從輸入流讀取輸入數(shù)據(jù)
public static Scanner getScanner(InputStream is) {
return new Scanner(is);
}
//從文件讀取輸入數(shù)據(jù)
public static Scanner getScanner(String fileName) {
try {
return getScanner(new FileInputStream(fileName));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return null;
}
}
