順序存儲二叉樹

順序存儲二叉樹的概念

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

要求：

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站看韓順平老師數據結構和演算法的課時的筆記，記錄一下，防止忘記，也希望能幫助各位朋友。