快捷導(dǎo)航

java有序二叉樹(shù)的刪除節(jié)點(diǎn)方式

更新時(shí)間：2024年12月17日 08:57:34 作者：Sshm_666

文章描述了在二叉樹(shù)中刪除節(jié)點(diǎn)的三種情況及其對(duì)應(yīng)的操作步驟,通過(guò)遞歸找到節(jié)點(diǎn)及其父節(jié)點(diǎn),并根據(jù)節(jié)點(diǎn)的子樹(shù)情況（無(wú)子樹(shù)、單子樹(shù)、雙子樹(shù)）進(jìn)行相應(yīng)的刪除操作,文章還提供了一個(gè)測(cè)試類來(lái)驗(yàn)證刪除操作的正確性

java有序二叉樹(shù)的刪除節(jié)點(diǎn)

刪除節(jié)點(diǎn)時(shí)會(huì)有三種可能

1、刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)

我們?nèi)绻麆h除為葉子節(jié)點(diǎn)，則步驟應(yīng)該是：

1）先找到要?jiǎng)h除的葉子節(jié)點(diǎn)

2）再找到要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)（考慮是否有父節(jié)點(diǎn)）

3）找到刪除的節(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹(shù)還是右子樹(shù)

4）根據(jù)前面的情況進(jìn)行刪除

2、刪除的節(jié)點(diǎn)只有一個(gè)子樹(shù)

步驟：

1）先找到要?jiǎng)h除的節(jié)點(diǎn)

2）再找到要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)（考慮是否有父節(jié)點(diǎn)）

3）確定刪除的節(jié)點(diǎn)是有左子樹(shù)還是有右子樹(shù)

4）找到刪除的節(jié)點(diǎn)是父節(jié)點(diǎn)的左子樹(shù)還是右子樹(shù)

5）根據(jù)前面的情況進(jìn)行刪除

3、刪除的節(jié)點(diǎn)有兩個(gè)子樹(shù)

步驟：

1）先找到要?jiǎng)h除的節(jié)點(diǎn)

2）再找到要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)（考慮是否有父節(jié)點(diǎn)）

3）找到刪除節(jié)點(diǎn)右子樹(shù)當(dāng)中最小的或左子樹(shù)最大的節(jié)點(diǎn)

4）將3）找到的這個(gè)節(jié)點(diǎn)的值替換掉要?jiǎng)h除的節(jié)點(diǎn)的值

5）刪除找到的3）

通過(guò)上面步驟它們都有一個(gè)共同特點(diǎn)就是需要找到刪除的節(jié)點(diǎn)和要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)，所以我們可以把這兩個(gè)找節(jié)點(diǎn)都寫成方法：

找到刪除節(jié)點(diǎn)代碼如下（通過(guò)遞歸的方式找到要?jiǎng)h除節(jié)點(diǎn)位置并記錄下來(lái)）：

//找到要?jiǎng)h除的節(jié)點(diǎn)
	public TreeNode searchDelnode(TreeNode node,Integer val) {
		if(node==null) {
			return null;
		}
		if(node.val==val) {
			return node;
		}else if(val>node.val){
			if(node.rightNode==null) {
				return null;
			}
			return searchDelnode(node.rightNode, val);
		}else {
			if(node.leftNode==null) {
				return null;
			}
			return searchDelnode(node.leftNode, val);
		}
	}

找被刪除節(jié)點(diǎn)的父節(jié)點(diǎn)代碼如下所示：

//找到要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)
	public TreeNode searchDelpartent(TreeNode node,Integer val) {
		if(node==null) {
			return null;
		}
		if((node.leftNode!=null&&node.leftNode.val==val)||(node.rightNode!=null&&node.rightNode.val==val)) {
			return node;
		}else {
			if(node.leftNode!=null&&val<node.val) {
				return searchDelpartent(node.leftNode, val);
			}else if(node.rightNode!=null&&val>node.val){
				return searchDelpartent(node.rightNode, val);
			}else {
				return null;
			}
		}
	}

我們可以根據(jù)以上步驟寫刪除方法代碼：

//二叉樹(shù)刪除節(jié)點(diǎn)
	public void del(TreeNode node,Integer val) {
		if(node==null) {
			return;
		}
		//1.找到要?jiǎng)h除的節(jié)點(diǎn)
		TreeNode targetNode=searchDelnode(node, val);
		//2.沒(méi)有找到要?jiǎng)h除的節(jié)點(diǎn)
		if(targetNode==null) {
			return;
		}
		//3.找到要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)
		TreeNode parentNode=searchDelpartent(node, val);
		if(node.rightNode==null&&node.leftNode==null) {
			root=null;
			return;
		}
		if(parentNode==null&&(targetNode.rightNode!=null||targetNode.leftNode!=null)) {
			int min=searchRightMin(targetNode.rightNode);
			targetNode.val=min;
			return;
		}
		if(targetNode.leftNode==null&&targetNode.rightNode==null) {
			if(parentNode.rightNode!=null&&parentNode.rightNode.val==targetNode.val) {
				parentNode.rightNode=null;
			}else if(parentNode.leftNode!=null&&parentNode.leftNode.val==val){
				parentNode.leftNode=null;
			}
		}else if(targetNode.leftNode!=null&&targetNode.rightNode!=null) {
//在刪除節(jié)點(diǎn)由左右兩個(gè)子樹(shù)時(shí)，我們選擇找刪除節(jié)點(diǎn)右子樹(shù)的最小值，我們可以寫一個(gè)方法，在這個(gè)方法里不僅找到最小值，并把這個(gè)位置的元素進(jìn)行刪除
			int min=searchRightMin(targetNode.rightNode);
			targetNode.val=min;
		}else {
			if(targetNode.rightNode!=null) {
				if(parentNode.rightNode.val==targetNode.val) {
					parentNode.rightNode=targetNode.rightNode;
				}else {
					parentNode.leftNode=targetNode.rightNode;
				}
			}else{
				if(targetNode.rightNode.val==targetNode.val) {
					parentNode.rightNode=targetNode.leftNode;
				}else {
					parentNode.leftNode=targetNode.leftNode;
				}
			}
		}
	}

在刪除節(jié)點(diǎn)由左右兩個(gè)子樹(shù)時(shí)，我們選擇找刪除節(jié)點(diǎn)右子樹(shù)的最小值，我們可以寫一個(gè)方法，在這個(gè)方法里不僅找到最小值，并把這個(gè)位置的元素進(jìn)行刪除

代碼如下：

public int searchRightMin(TreeNode node) {
		TreeNode temp=node;
		while(temp.leftNode!=null) {
			temp=temp.leftNode;
		}
		del(root, temp.val);
		return temp.val;
	}
}

寫一個(gè)測(cè)試類進(jìn)行測(cè)試：

public class Test {
	public static void main(String[] args) {
		BinaryTree binaryTree=new BinaryTree();
		binaryTree.insert(1);
		binaryTree.insert(2);
		binaryTree.insert(3);
		binaryTree.insert(4);
		binaryTree.insert(5);
		binaryTree.insertDigui(6, binaryTree.root);
		binaryTree.insertDigui(7, binaryTree.root);
		binaryTree.insertDigui(8, binaryTree.root);
		binaryTree.insertDigui(9, binaryTree.root);
		binaryTree.del(binaryTree.root, 2);
		binaryTree.Order();
		System.out.println();
		binaryTree.startErgodic(binaryTree.root);
		System.out.println();
		binaryTree.midErgodic(binaryTree.root);
		System.out.println();
		binaryTree.endErgodic(binaryTree.root);
	}
}

結(jié)果如下圖所示：