Java教程

二叉树删除结点

本文主要是介绍二叉树删除结点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.删除的规定(剩下的后面补充)

  1. 如果删除的是叶子结点,则删除该结点;
  2. 如果删除的结点是非叶子结点,则删除该子树

2.删除思路

  1. 首先,考虑如果树是空树root,或者只有一个结点,则等价于二叉树置空。
  2. 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除,而不能去判断当前这个结点是不是需要删除该结点
  3. 如果当前结点的左子结点不为空,并且左子结点就是要删除的结点,就将this.left=null;并且返回结束递归;
  4. 如果当前结点的右子结点不为空,并且右子结点就是要删除的结点,就是将this.right=null;并且返回,结束递归;
  5. 如果第3步和第4步没有删除结点,那么需要向左子树进行递归删除
  6. 如果第5步也没有删除结点,则应当向右子树进行递归删除。

3.代码实现

3.1 在下图HeroNode位置增加删除方法

// 递归删除结点
	public void delNode(int no){
		// 如果当前结点的左子结点不为空,并且左子结点就是要删除的结点,就将this.left=null;并且返回结束递归;
		if (this.left != null && this.left.no==no) {
			this.left = null;
			return;
		}
		// 如果当前结点的右子结点不为空,并且右子结点就是要删除的结点,就是将this.right=null;并且返回,结束递归;
		if (this.right != null && this.right.no == no) {
			this.right = null;
			return;
		}
		// 前面的步骤都没有删除,继续向左递归删除
		if (this.left != null) {
			this.left.delNode(no);
		}
		// 前面的步骤都没有删除,继续向右递归删除
		if (this.right != null) {
			this.right.delNode(no);
		}
		
	}

3.2在二叉树BinaryTree位置增加删除方法

// 删除结点
	public void delNode(int no){
		if (root == null) {
			System.out.println("空树,不能删除");
		} else {
			//不是空树,可以进行删除操作
			//如果只有一个root结点,判断是不是要删除的结点
			if (root.getNo() == no) {
				root = null;
			} else {
				// 不止一个结点
				// 递归删除
				root.delNode(no);
			}
		}
	}

3.3测试方法

//测试删除结点操作
		System.out.println("删除前,前序遍历");
		binaryTree.preOrder();
		binaryTree.delNode(4);
		System.out.println("删除后,前序遍历");
		binaryTree.preOrder();

3.4测试结果

这篇关于二叉树删除结点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!