順序存儲二叉樹

来源: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
  • 背景 在瀏覽器中訪問本地靜態資源html網頁時,可能會遇到跨域問題如圖。 是因為瀏覽器預設啟用了同源策略,即只允許載入與當前網頁具有相同源(協議、功能變數名稱和埠)的內容。 WebView2預設情況下啟用了瀏覽器的同源策略,即只允許載入與主機相同源的內容。所以如果我們把靜態資源發佈到iis或者通過node ...
  • 最近看幾個老項目的SQL條件中使用了1=1,想想自己也曾經這樣寫過,略有感觸,特別拿出來說道說道。編寫SQL語句就像炒菜,每一種調料的使用都會影響菜品的最終味道,每一個SQL條件的加入也會影響查詢的執行效率。那麼 1=1 存在什麼樣的問題呢?為什麼又會使用呢? ...
  • 好久不見,我又回來了。 給大家分享一個我最近使用c#代碼操作ftp伺服器的代碼示例: 1 public abstract class FtpOperation 2 { 3 /// <summary> 4 /// FTP伺服器地址 5 /// </summary> 6 private string f ...
  • 一:背景 1. 講故事 過年喝了不少酒,腦子不靈光了,停了將近一個月沒寫博客,今天就當新年開工寫一篇吧。 去年年初有位朋友找到我,說他們的系統會偶發性崩潰,在網上也發了不少帖子求助,沒找到自己滿意的答案,讓我看看有沒有什麼線索,看樣子這是一個牛皮蘚的問題,既然對方有了dump,那就分析起來吧。 二: ...
  • 自己製作的一個基於Entity Framework Core 的資料庫操作攔截器,可以列印資料庫執行sql,方便開發調試,代碼如下: /// <summary> /// EF Core 的資料庫操作攔截器,用於在資料庫操作過程中進行日誌記錄和監視。 /// </summary> /// <remar ...
  • 本文分享自華為雲社區《Go併發範式 流水線和優雅退出 Pipeline 與 Cancellation》,作者:張儉。 介紹 Go 的併發原語可以輕鬆構建流數據管道,從而高效利用 I/O 和多個 CPU。 本文展示了此類pipelines的示例,強調了操作失敗時出現的細微之處,並介紹了乾凈地處理失敗的 ...
  • 在上篇文章中,我們介紹到在多線程環境下,如果編程不當,可能會出現程式運行結果混亂的問題。出現這個原因主要是,JMM 中主記憶體和線程工作記憶體的數據不一致,以及多個線程執行時無序,共同導致的結果。 ...
  • 1、下載安裝包首先、進入官網下載安裝包網址:https://www.python.org/downloads/windows/下載步驟:進入下載地址,根據自己的電腦系統選擇相應的python版本 選擇適配64位操作系統的版本(查看自己的電腦操作系統版本), 點擊下載安裝包 也可以下載我百度雲分享的安 ...
  • 簡介 git-commit-id-maven-plugin 是一個maven 插件,用來在打包的時候將git-commit 信息打進jar中。 這樣做的好處是可以將發佈的某版本和對應的代碼關聯起來,方便查閱和線上項目的維護。至於它的作用,用官方說法,這個功能對於大型分散式項目來說是無價的。 功能 你 ...
  • 序言 在數字時代,圖像生成技術正日益成為人工智慧領域的熱點。 本討論將重點聚焦於兩個備受矚目的模型:DALL-E和其他主流AI繪圖方法。 我們將探討它們的優勢、局限性以及未來的發展方向。通過比較分析,我們期望能夠更全面地瞭解這些技術,為未來的研究和應用提供啟示。 Q: 介紹一下 dall-e Ope ...