二叉樹查找和刪除指定結點

来源:https://www.cnblogs.com/malinyan/archive/2022/09/25/SearchAndDeleteNode.html
-Advertisement-
Play Games

二叉樹查找指定的節點 前序查找的思路 1.先判斷當前節點的no是否等於要查找的 2.如果是相等,則返回當前節點 3.如果不等,則判斷當前節點的左子節點是否為空,如果不為空,則遞歸前序查找 4.如果左遞歸前序查找,找到節點,則返回,否繼續判斷,當前的節點的右子節點是否為空,如果不為空,則繼續向右遞歸前 ...


二叉樹查找指定的節點

前序查找的思路

1.先判斷當前節點的no是否等於要查找的

2.如果是相等,則返回當前節點

3.如果不等,則判斷當前節點的左子節點是否為空,如果不為空,則遞歸前序查找

4.如果左遞歸前序查找,找到節點,則返回,否繼續判斷,當前的節點的右子節點是否為空,如果不為空,則繼續向右遞歸前序查找。

中序查找思路

1.判斷當前節點的左子節點是否為空,如果不為空,則遞歸中序查找

2.如果找到,則返回,如果沒有找到,就和當前節點比較,如果是則返回當前節點,否則繼續進行右遞歸的中序查找

3.如果右遞歸中序查找,找到就返回,否則返回null

後序查找思路

1.判斷當前節點的左子節點是否為空,如果不為空,則遞歸後序查找

2.如果找到,就返回,如果沒有找到,就判斷當前節點的右子節點是否為空,如果不為空,則右遞歸進行後序查找,如果找到,就返回

3.就和當前節點進行比較,如果是則返回,否則返回null

要求

1.請編寫前序查找,中序查找和後序查找的方法。

2.並分別使用三種查找方式,查找 heroNO = 5 的節點

3.並分析各種查找方式,分別比較了多少次

代碼實現:

先創建HeroNode 結點

class HeroNode {
	private int no;
	private String name;
	private HeroNode left; //預設null
	private HeroNode right; //預設null
	public HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public HeroNode getLeft() {
		return left;
	}
	public void setLeft(HeroNode left) {
		this.left = left;
	}
	public HeroNode getRight() {
		return right;
	}
	public void setRight(HeroNode right) {
		this.right = right;
	}
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}
    //前序遍歷
	public void preOrder() {
		System.out.println(this); //先輸出父結點
		//遞歸向左子樹前序遍歷
		if(this.left != null) {
			this.left.preOrder();
		}
		//遞歸向右子樹前序遍歷
		if(this.right != null) {
			this.right.preOrder();
		}
	}
	//前序遍歷查找
	/**
	 * 
	 * @param no 查找no
	 * @return 如果找到就返回該Node ,如果沒有找到返回 null
	 */
	public HeroNode preOrderSearch(int no) {
		System.out.println("進入前序遍歷");
		//比較當前結點是不是
		if(this.no == no) {
			return this;
		}
		//1.則判斷當前結點的左子節點是否為空,如果不為空,則遞歸前序查找
		//2.如果左遞歸前序查找,找到結點,則返回
		HeroNode resNode = null;
		if(this.left != null) {
			resNode = this.left.preOrderSearch(no);
		}
		if(resNode != null) {//說明我們左子樹找到
			return resNode;
		}
		//1.左遞歸前序查找,找到結點,則返回,否繼續判斷,
		//2.當前的結點的右子節點是否為空,如果不空,則繼續向右遞歸前序查找
		if(this.right != null) {
			resNode = this.right.preOrderSearch(no);
		}
		return resNode;
	}
	
	//中序遍歷查找
	public HeroNode infixOrderSearch(int no) {
		//判斷當前結點的左子節點是否為空,如果不為空,則遞歸中序查找
		HeroNode resNode = null;
		if(this.left != null) {
			resNode = this.left.infixOrderSearch(no);
		}
		if(resNode != null) {
			return resNode;
		}
		System.out.println("進入中序查找");
		//如果找到,則返回,如果沒有找到,就和當前結點比較,如果是則返回當前結點
		if(this.no == no) {
			return this;
		}
		//否則繼續進行右遞歸的中序查找
		if(this.right != null) {
			resNode = this.right.infixOrderSearch(no);
		}
		return resNode;
		
	}
	
	//後序遍歷查找
	public HeroNode postOrderSearch(int no) {
		
		//判斷當前結點的左子節點是否為空,如果不為空,則遞歸後序查找
		HeroNode resNode = null;
		if(this.left != null) {
			resNode = this.left.postOrderSearch(no);
		}
		if(resNode != null) {//說明在左子樹找到
			return resNode;
		}
		
		//如果左子樹沒有找到,則向右子樹遞歸進行後序遍歷查找
		if(this.right != null) {
			resNode = this.right.postOrderSearch(no);
		}
		if(resNode != null) {
			return resNode;
		}
		System.out.println("進入後序查找");
		//如果左右子樹都沒有找到,就比較當前結點是不是
		if(this.no == no) {
			return this;
		}
		return resNode;
	}
	
}

定義BinaryTree 二叉樹

class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}
	
	//前序遍歷查找
	public HeroNode preOrderSearch(int no) {
		if(root != null) {
			return root.preOrderSearch(no);
		} else {
			return null;
		}
	}
	//中序遍歷查找
	public HeroNode infixOrderSearch(int no) {
		if(root != null) {
			return root.infixOrderSearch(no);
		}else {
			return null;
		}
	}
	//後序遍歷查找
	public HeroNode postOrderSearch(int no) {
		if(root != null) {
			return this.root.postOrderSearch(no);
		}else {
			return null;
		}
	}
}

測試:

public class BinaryTreeDemo {

	public static void main(String[] args) {
		//先需要創建一顆二叉樹
		BinaryTree binaryTree = new BinaryTree();
		//創建需要的結點
		HeroNode root = new HeroNode(1, "宋江");
		HeroNode node2 = new HeroNode(2, "吳用");
		HeroNode node3 = new HeroNode(3, "盧俊義");
		HeroNode node4 = new HeroNode(4, "林沖");
		HeroNode node5 = new HeroNode(5, "關勝");
		
		//說明,我們先手動創建該二叉樹,後面我們學習遞歸的方式創建二叉樹
		root.setLeft(node2);
		root.setRight(node3);
		node3.setRight(node4);
		node3.setLeft(node5);
		binaryTree.setRoot(root);
		
		// 前序遍歷
		// 前序遍歷的次數 :4
		System.out.println("前序遍歷方式~~~");
		HeroNode resNode = binaryTree.preOrderSearch(5);
		if (resNode != null) {
			System.out.printf("找到了,信息為 no=%d name=%s", resNode.getNo(), resNode.getName());
		} else {
			System.out.printf("沒有找到 no = %d 的英雄", 5);
		}
		
		/**
			// 中序遍歷查找
			// 中序遍歷3次
			System.out.println("中序遍歷方式~~~");
			HeroNode resNode = binaryTree.infixOrderSearch(5);
			if (resNode != null) {
				System.out.printf("找到了,信息為 no=%d name=%s", resNode.getNo(), resNode.getName());
			} else {
				System.out.printf("沒有找到 no = %d 的英雄", 5);
			}
		*/
		/**
			// 後序遍歷查找
			// 後序遍歷查找的次數 2次
			System.out.println("後序遍歷方式~~~");
			HeroNode resNode = binaryTree.postOrderSearch(5);
			if (resNode != null) {
				System.out.printf("找到了,信息為 no=%d name=%s", resNode.getNo(), resNode.getName());
			} else {
				System.out.printf("沒有找到 no = %d 的英雄", 5);
			}
		*/
		
	}

}

運行結果如圖:

前序遍歷:

中序遍歷:

後序遍歷:

二叉樹刪除指定的節點

要求

1.如果刪除的節點是葉子節點,則刪除該節點

2.如果刪除的節點是非葉子節點,則刪除該子樹.

3.測試,刪除掉 5 號葉子節點

思路:

1.考慮如果樹是空樹root,如果只有一個root節點,則等價將二叉樹置空

2.因為我們的二叉樹是單向的,所以我們是判斷當前節點的子節點是否是需要刪除節點,而不能去判斷當前這個節點是不是需要刪除節點。

3.如果當前節點的左子節點不為空,並且左子節點就是要刪除節點,就將this.left=null;

並且就返回(結束遞歸刪除)

4.如果當前節點的右子節點不為空,並且右子節點就是要刪除節點,就將this.right=null;

並且就返回(結束遞歸刪除)

5.如果3,4步沒有刪除節點,那麼我們就需要向左子樹進行遞歸刪除

6.如果第5步也沒有刪除節點,則應當向右子樹進行遞歸刪除。

代碼實現:

//HeroNode 類增加方法

//遞歸刪除結點
	//1.如果刪除的節點是葉子節點,則刪除該節點
	//2.如果刪除的節點是非葉子節點,則刪除該子樹
	public void delNode(int no) {
		
		//思路
		/*
		 * 	1. 因為我們的二叉樹是單向的,所以我們是判斷當前結點的子結點是否需要刪除結點,而不能去判斷當前這個結點是不是需要刪除結點.
			2. 如果當前結點的左子結點不為空,並且左子結點 就是要刪除結點,就將this.left = null; 並且就返回(結束遞歸刪除)
			3. 如果當前結點的右子結點不為空,並且右子結點 就是要刪除結點,就將this.right= null ;並且就返回(結束遞歸刪除)
			4. 如果第2和第3步沒有刪除結點,那麼我們就需要向左子樹進行遞歸刪除
			5.  如果第4步也沒有刪除結點,則應當向右子樹進行遞歸刪除.

		 */
		//2. 如果當前結點的左子結點不為空,並且左子結點 就是要刪除結點,就將this.left = null; 並且就返回(結束遞歸刪除)
		if(this.left != null && this.left.no == no) {
			this.left = null;
			return;
		}
		//3.如果當前結點的右子結點不為空,並且右子結點 就是要刪除結點,就將this.right= null ;並且就返回(結束遞歸刪除)
		if(this.right != null && this.right.no == no) {
			this.right = null;
			return;
		}
		//4.我們就需要向左子樹進行遞歸刪除
		if(this.left != null) {
			this.left.delNode(no);
		}
		//5.則應當向右子樹進行遞歸刪除
		if(this.right != null) {
			this.right.delNode(no);
		}
	}

//在 BinaryTree 類增加方法

//刪除結點
	public void delNode(int no) {
		if(root != null) {
			//如果只有一個root結點, 這裡立即判斷root是不是就是要刪除結點
			if(root.getNo() == no) {
				root = null;
			} else {
				//遞歸刪除
				root.delNode(no);
			}
		}else{
			System.out.println("空樹,不能刪除~");
		}
	}

//在 BinaryTreeDemo 類增加測試代碼:

//測試一把刪除結點
		System.out.println("刪除前,前序遍歷");
		binaryTree.preOrder(); //  1,2,3,5,4
		binaryTree.delNode(5);
		//binaryTree.delNode(3);
		System.out.println("刪除後,前序遍歷");
		binaryTree.preOrder(); // 1,2,3,4

代碼運行如圖:

這篇博客是我在B站看韓順平老師數據結構和演算法的課時的筆記,記錄一下,防止忘記,也希望能幫助各位朋友。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Stream流呢,以前我也有所瞭解,像一些面試題中也出現過,Java8的新特性,有一塊就是這個Stream操作集合,而且在看一些項目中也使用的比較多。但總感覺自己學的一知半解,所以今天打算系統的過一下,再鞏固鞏固。 ###概念 Stream是JDK8 API中的新成員,它允許以聲明性方式處理集合。 ...
  • 一、開發背景 您好,我是 @馬哥python說 ,這是我獨立開發的Python可視化大屏,看下演示效果: 截圖: 視頻演示效果: https://www.zhihu.com/zvideo/1556218745923821568 這個大屏,是通過pyecharts可視化開發框架實現。 下麵詳細介紹,這 ...
  • 來源:https://www.linuxmi.com/50-million-pc-linux.html 開源社區的一大勝利! 繼德國之後,中國現在想在 5000 萬台 PC 上拋棄 Windows 並運行 Linux! 如果您一直密切關註 Linux 新聞,您可能聽說過德國去年在超過 25000 台 ...
  • ###一、Scrapy 介紹 Scrapy是一個Python編寫的開源和協作的框架。起初是用於網路頁面抓取所設計的,使用它可以快速、簡單、可擴展的方式從網站中提取所需的數據。 Scrapy也是通用的網路爬蟲框架,爬蟲界的django(設計原則很像),可用於數據挖掘、監測和自動化測試、也可以應用在獲取 ...
  • 2022-09-25 首先,要安裝好虛擬環境,之後要切換到虛擬環境中,使用的命令 workon 創建好的虛擬環境的名稱 之後,創建一個Django項目使用的命令: django-admin startproject 項目名稱 進入到該項目的目錄下,創建一個子應用,使用的命令: python mana ...
  • 拉格朗日插值原理及實現(Python) 一. 前言 Lagrange插值是利用n次多項式來擬合**(n+1)個數據點**從而得到插值函數的方法。(註意n次多項式的定義是未知數最高次冪為n,但是多項式繫數有n+1個,因為還有個常數項) **Lagrange插值和Newton插值本質上相同,都是用(n- ...
  • ###一、背景知識 爬蟲的本質就是一個socket客戶端與服務端的通信過程,如果我們有多個url待爬取,只用一個線程且採用串列的方式執行,那隻能等待爬取一個結束後才能繼續下一個,效率會非常低。 需要強調的是:對於單線程下串列N個任務,並不完全等同於低效,如果這N個任務都是純計算的任務,那麼該線程對c ...
  • ##Invalid bound statement (not found)出現原因和解決方法 ###前言: 想必各位小伙伴在碼路上經常會碰到奇奇怪怪的事情,比如出現Invalid bound statement (not found),那今天我就來分析以下出現此問題的原因。 其實出現這個問題實質就是 ...
一周排行
    -Advertisement-
    Play Games
  • 經常看到有群友調侃“為什麼搞Java的總在學習JVM調優?那是因為Java爛!我們.NET就不需要搞這些!”真的是這樣嗎?今天我就用一個案例來分析一下。 昨天,一位學生問了我一個問題:他建了一個預設的ASP.NET Core Web API的項目,也就是那個WeatherForecast的預設項目模 ...
  • 很多軟體工程師都認為MD5是一種加密演算法,然而這種觀點是不對的。作為一個 1992 年第一次被公開的演算法,到今天為止已經被髮現了一些致命的漏洞。本文討論MD5在密碼保存方面的一些問題。 ...
  • Maven可以使我們在構建項目時需要用到很多第三方類jar包,如下一些常用jar包 而maven的出現可以讓我們避免手動導入jar包出現的某些問題,它可以自動下載那須所需要的jar包 我們只需要在創建的maven項目自動生成的pom.xml中輸入如下代碼 <dependencies> <!--ser ...
  • 來源:https://developer.aliyun.com/article/694020 非同步調用幾乎是處理高併發Web應用性能問題的萬金油,那麼什麼是“非同步調用”? “非同步調用”對應的是“同步調用”,同步調用指程式按照定義順序依次執行,每一行程式都必須等待上一行程式執行完成之後才能執行;非同步調 ...
  • 1.面向對象 面向對象編程是在面向過程編程的基礎上發展來的,它比面向過程編程具有更強的靈活性和擴展性,所以可以先瞭解下什麼是面向過程編程: 面向過程編程的核心是過程,就是分析出實現需求所需要的步驟,通過函數一步一步實現這些步驟,接著依次調用即可,再簡單理解就是程式 從上到下一步步執行,從頭到尾的解決 ...
  • 10瓶毒藥其中只有一瓶有毒至少需要幾隻老鼠可以找到有毒的那瓶 身似浮雲,心如飛絮,氣若游絲。 用二分查找和二進位位運算的思想都可以把死亡的老鼠降到最低。 其中,二進位位運算就是每一隻老鼠代表一個二進位0或1,0就代表老鼠存活,1代表老鼠死亡;根據數學運算 23 = 8、24 = 16,那麼至少需要四 ...
  • 一、Kafka存在哪些方面的優勢 1. 多生產者 可以無縫地支持多個生產者,不管客戶端在使用單個主題還是多個主題。 2. 多消費者 支持多個消費者從一個單獨的消息流上讀取數據,而且消費者之間互不影響。 3. 基於磁碟的數據存儲 支持消費者非實時地讀取消息,由於消息被提交到磁碟,根據設置的規則進行保存 ...
  • 大家好,我是陶朱公Boy。 前言 上一篇文章《關於狀態機的技術選型,最後一個真心好》我跟大家聊了一下關於”狀態機“的話題。從眾多技術選型中我也推薦了一款阿裡開源的狀態機—“cola-statemachine”。 於是就有小伙伴私信我,自己項目也考慮引入這款狀態機,但網上資料實在太少,能不能系統的介紹 ...
  • 使用腳本自動跑實驗(Ubuntu),將實驗結果記錄在文件中,併在實驗結束之後將結果通過郵件發送到郵箱,最後在windows端自動解析成excel表格。 ...
  • 話說在前面,我不是小黑子~ 我是超級大黑子😏 表弟大周末的跑來我家,沒事幹天天騷擾我,搞得我都不能跟小姐姐好好聊天了,於是為了打發表弟,我決定用Python做一個小游戲來消耗一下他的精力,我思來想去,決定把他變成小黑子,於是做了一個坤坤打籃球的游戲,沒想到他還挺愛玩的~ 終於解放了,於是我把游戲寫 ...