順序存儲二叉樹

来源: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
  • 1.部署歷史 猿友們好,作為初來實習的我,已經遭受社會的“毒打”,所以請容許我在下麵環節適當吐槽,3Q! 傳統部署 ​ 回顧以往在伺服器部署webapi項目(非獨立發佈),dotnet環境、守護進程兩個逃都逃不掉,正常情況下還得來個nginx代理。不僅僅這仨,可能牽扯到yum或npm。node等都要 ...
  • 隨著技術的進步,跨平臺開發已經成為了標配,在此大背景下,ASP.NET Core也應運而生。本文主要基於ASP.NET Core+Element+Sql Server開發一個校園圖書管理系統為例,簡述基於MVC三層架構開發的常見知識點,前一篇文章,已經簡單介紹瞭如何搭建開發框架,和登錄功能實現,本篇... ...
  • 這道題只要會自定義cmp恰當地進行排序,其他部分沒有什麼大問題。 上代碼: 1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,s,h1,h2,cnt; 4 struct apple{ 5 int height,ns;//height為蘋 ...
  • 這篇文章主要描述RPC的路由策略,包括為什麼需要請求隔離,為什麼不在註冊中心中實現請求隔離以及不同粒度的路由策略。 ...
  • 簡介: 中介者模式,屬於行為型的設計模式。用一個中介對象來封裝一系列的對象交互。中介者是各對象不需要顯式地相互引用,從而使其耦合鬆散,而且可以獨立地改變他們之間的交互。 適用場景: 如果平行對象間的依賴複雜,可以使用中介者解耦。 優點: 符合迪米特法則,減少成員間的依賴。 缺點: 不適用於系統出現對 ...
  • 【前置內容】Spring 學習筆記全系列傳送門: Spring學習筆記 - 第一章 - IoC(控制反轉)、IoC容器、Bean的實例化與生命周期、DI(依賴註入) Spring學習筆記 - 第二章 - 註解開發、配置管理第三方Bean、註解管理第三方Bean、Spring 整合 MyBatis 和 ...
  • 簡介: 享元模式,屬於結構型的設計模式。運用共用技術有效地支持大量細粒度的對象。 適用場景: 具有相同抽象但是細節不同的場景中。 優點: 把公共的部分分離為抽象,細節依賴於抽象,符合依賴倒轉原則。 缺點: 增加複雜性。 代碼: //用戶類 class User { private $name; fu ...
  • 這次設計一個通用的多位元組SPI介面模塊,特點如下: 可以設置為1-128位元組的SPI通信模塊 可以修改CPOL、CPHA來進行不同的通信模式 可以設置輸出的時鐘 狀態轉移圖和思路與多位元組串口發送模塊一樣,這裡就不給出了,具體可看該隨筆。 一、模塊代碼 1、需要的模塊 通用8位SPI介面模塊 `tim ...
  • AOP-03 7.AOP-切入表達式 7.1切入表達式的具體使用 1.切入表達式的作用: 通過表達式的方式定義一個或多個具體的連接點。 2.語法細節: (1)切入表達式的語法格式: execution([許可權修飾符] [返回值類型] [簡單類名/全類名] [方法名]([參數列表]) 若目標類、介面與 ...
  • 測試一、虛繼承與繼承的區別 1.1 單個繼承,不帶虛函數 1>class B size(8): 1> + 1> 0 | + (base class A) 1> 0 | | _ia //4B 1> | + 1> 4 | _ib //4B 有兩個int類型數據成員,占8B,基類邏輯存在前面 1.2、單個 ...