順序存儲二叉樹

来源: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
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...