順序存儲二叉樹

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

順序存儲二叉樹的概念 從數據存儲來看,數組存儲方式和樹的存儲方式可以相互轉換,即數組可以轉換成樹,樹也可以轉換成數組, 看下麵的示意圖。 要求: 右圖的二叉樹的結點,要求以數組的方式來存放 arr : [1, 2, 3, 4, 5, 6, 6] 要求在遍曆數組 arr 時,仍然可以以前序遍歷,中序遍 ...


順序存儲二叉樹的概念

從數據存儲來看,數組存儲方式和樹的存儲方式可以相互轉換,即數組可以轉換成樹樹也可以轉換成數組, 看下麵的示意圖。

要求:

  1. 右圖的二叉樹的結點,要求以數組的方式來存放 arr : [1, 2, 3, 4, 5, 6, 6]
  2. 要求在遍曆數組 arr 時,仍然可以以前序遍歷,中序遍歷和後序遍歷的方式完成結點的遍歷

順序存儲二叉樹的特點:

  1. 順序二叉樹通常只考慮完全二叉樹
  2. 第 n 個元素的左子節點為 2 * n + 1
  3. 第 n 個元素的右子節點為 2 * n + 2
  4. 第 n 個元素的父節點為 (n-1) / 2
  5. n : 表示二叉樹中的第幾個元素(按 0 開始編號如圖所示)

順序存儲二叉樹遍歷

需求: 給你一個數組 {1,2,3,4,5,6,7},要求以二叉樹前序遍歷的方式進行遍歷。 前序遍歷的結果應當為1,2,4,5,3,6,7

代碼如下:

package com.atguigu.tree;

public class ArrBinaryTreeDemo {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
		//創建一個 ArrBinaryTree
		ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
		arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
	}

}

//編寫一個ArrayBinaryTree, 實現順序存儲二叉樹遍歷

class ArrBinaryTree {
	private int[] arr;//存儲數據結點的數組

	public ArrBinaryTree(int[] arr) {
		this.arr = arr;
	}
	
	//重載preOrder
	public void preOrder() {
		this.preOrder(0);
	}
	
	//編寫一個方法,完成順序存儲二叉樹的前序遍歷
	/**
	 * 
	 * @param index 數組的下標 
	 */
	public void preOrder(int index) {
		//如果數組為空,或者 arr.length = 0
		if(arr == null || arr.length == 0) {
			System.out.println("數組為空,不能按照二叉樹的前序遍歷");
		}
		//輸出當前這個元素
		System.out.println(arr[index]); 
		//向左遞歸遍歷
		if((index * 2 + 1) < arr.length) {
			preOrder(2 * index + 1 );
		}
		//向右遞歸遍歷
		if((index * 2 + 2) < arr.length) {
			preOrder(2 * index + 2);
		}
	}
	
}

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


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

-Advertisement-
Play Games
更多相關文章
  • 前幾天剛開始對PAT甲級的刷題,首次看到英語的題目,讓原本就菜的我更是頭禿,但第一題叫了n遍以後滿分通過的時候還是蠻爽的,在此僅記錄一下該題的個人解題心路,菜鳥記錄,技術極低。 Calculate a+b and output the sum in standard format -- that i ...
  • Java反射01 1.反射(reflection)機制 1.1反射機制問題 一個需求引出反射 請看下麵問題: 根據配置文件 re.properties 指定信息,創建Cat對象並調用方法hi classfullpath=li.reflection.Cat method=hi 使用現有的技術,你能做的 ...
  • java基礎 以下內容為本人的學習筆記,如需要轉載,請聲明原文鏈接 java常用類: 1.內部類 2.Object類 3.Object類常用方法 4.包裝類 5.String類 6.BigDecimal類 1、內部類 分類: 內部類:成員內部類,靜態內部類, 局部內部類,匿名內部類 概念:在一個類的 ...
  • 2022-09-26 組合數據類型: 列表 字典 集合 元組 拷貝: deep(深拷貝) shallow(淺拷貝) 區別:例如,文件中有一個指針指向另一塊存儲空間,如果是深拷貝則將指向的那一塊文件內容也全部拷貝,如果是淺拷貝那麼不需要將指針指向的內容進行拷貝,只拷貝第一層級的內容。指針指向的內容屬於 ...
  • 分散式ID策略 為什麼要用分散式ID? 在我們業務數據量不大的時候,單庫單表完全可以支撐現有業務,數據再大一點搞個 MySQL 主從同步讀寫分離也能對付。 但隨著數據日漸增長,主從同步也扛不住了,就需要對資料庫進行分庫分表,但分庫分表後需要有一個唯一ID來標識一條數據,資料庫的自增ID顯然不能滿足需 ...
  • 前言 大家早好、午好、晚好吖~ 知識點: 爬蟲基本流程 保存海量漫畫數據 requests的使用 base64解碼 開發環境: 版 本:python 3.8 編輯器:pycharm requests: pip install requests parsel: pip install parsel 如 ...
  • 上一篇文章我們學習了使用註解開發,但還沒有完全脫離xml的配置,現在我們來學習JavaConfig配置來代替xml的配置,實現完全註解開發。 下麵我們用一個簡單的例子來進行學習。 一、首先建立兩個實體類 User: package com.jms.pojo; import org.springfra ...
  • 服務註冊中心 Nacos 官網:home (nacos.io) nacos-server下載地址:Releases · alibaba/nacos (github.com) 第一步:運行nacos-server nacos-server-2.1.1\nacos\bin 目錄下打開命令行視窗,輸入st ...
一周排行
    -Advertisement-
    Play Games
  • 在C#中使用SQL Server實現事務的ACID(原子性、一致性、隔離性、持久性)屬性和使用資料庫鎖(悲觀鎖和樂觀鎖)時,你可以通過ADO.NET的SqlConnection和SqlTransaction類來實現。下麵是一些示例和概念說明。 實現ACID事務 ACID屬性是事務處理的四個基本特征, ...
  • 我們在《SqlSugar開發框架》中,Winform界面開發部分往往也用到了自定義的用戶控制項,對應一些特殊的界面或者常用到的一些局部界面內容,我們可以使用自定義的用戶控制項來提高界面的統一性,同時也增強了使用的便利性。如我們Winform界面中用到的分頁控制項、附件顯示內容、以及一些公司、部門、菜單的下... ...
  • 在本篇教程中,我們學習瞭如何在 Taurus.MVC WebMVC 中進行數據綁定操作。我們還學習瞭如何使用 ${屬性名稱} CMS 語法來綁定頁面上的元素與 Model 中的屬性。通過這些步驟,我們成功實現了一個簡單的數據綁定示例。 ...
  • 是在MVVM中用來傳遞消息的一種方式。它是在MVVMLight框架中提供的一個實現了IMessenger介面的類,可以用來在ViewModel之間、ViewModel和View之間傳遞消息。 Send 接受一個泛型參數,表示要發送的消息內容。 Register 方法用於註冊某個對象接收消息。 pub ...
  • 概述:在WPF中,通過EventHandler可實現基礎和高級的UI更新方式。基礎用法涉及在類中定義事件,併在UI中訂閱以執行更新操作。高級用法藉助Dispatcher類,確保在非UI線程上執行操作後,通過UI線程更新界面。這兩種方法提供了靈活而可靠的UI更新機制。 在WPF(Windows Pre ...
  • 概述:本文介紹了在C#程式開發中如何利用自定義擴展方法測量代碼執行時間。通過使用簡單的Action委托,開發者可以輕鬆獲取代碼塊的執行時間,幫助優化性能、驗證演算法效率以及監控系統性能。這種通用方法提供了一種便捷而有效的方式,有助於提高開發效率和代碼質量。 在軟體開發中,瞭解代碼執行時間是優化程式性能 ...
  • 概述:Cron表達式是一種強大的定時任務調度工具,通過配置不同欄位實現靈活的時間規定。在.NET中,Quartz庫提供了簡便的方式配置Cron表達式,實現精準的定時任務調度。這種靈活性和可擴展性使得開發者能夠根據需求輕鬆地制定和管理定時任務,例如每天備份系統日誌或其他重要操作。 Cron表達式詳解 ...
  • 概述:.NET提供多種定時器,如System.Windows.Forms.Timer適用於UI,System.Web.UI.Timer用於Web,System.Diagnostics.Timer用於性能監控,System.Threading.Timer和System.Timers.Timer用於一般 ...
  • 問題背景 有同事聯繫我說,在生產環境上,訪問不了我負責的common服務,然後我去檢查common服務的health endpoint, 沒問題,然後我問了下異常,timeout導致的System.OperationCanceledException。那大概率是客戶端的問題,會不會是埠耗盡,用ne ...
  • 前言: 在本篇 Taurus.MVC WebMVC 入門開發教程的第四篇文章中, 我們將學習如何實現數據列表的綁定,通過使用 List<Model> 來展示多個數據項。 我們將繼續使用 Taurus.Mvc 命名空間,同時探討如何在視圖中綁定並顯示一個 Model 列表。 步驟1:創建 Model ...