順序存盤二叉樹的概念
從資料存盤來看，陣列存盤方式和樹的存盤方式可以相互轉換，即陣列可以轉換成樹，樹也可以轉換成陣列， 看下面的示意圖，
要求：
- 右圖的二叉樹的結點，要求以陣列的方式來存放 arr : [1, 2, 3, 4, 5, 6, 6]
- 要求在遍歷陣列 arr 時，仍然可以以前序遍歷，中序遍歷和后序遍歷的方式完成結點的遍歷
順序存盤二叉樹的特點:
- 順序二叉樹通常只考慮完全二叉樹
- 第 n 個元素的左子節點為 2 * n + 1
- 第 n 個元素的右子節點為 2 * n + 2
- 第 n 個元素的父節點為 (n-1) / 2
- 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站看韓順平老師資料結構和演算法的課時的筆記，記錄一下，防止忘記，也希望能幫助各位朋友，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/509567.html
標籤：其他
上一篇：Python-函式-字串函式
下一篇：SpringCloud 學習總結