因?yàn)閺臄?shù)據(jù)存儲(chǔ)的角度來看，數(shù)組存儲(chǔ)方式和樹的存儲(chǔ)方式是可以互相轉(zhuǎn)換的，即數(shù)組可以轉(zhuǎn)換為樹，而樹也可以轉(zhuǎn)換成數(shù)組。

八大排序算法中的堆排序，就會(huì)使用到順序存儲(chǔ)二叉樹，后面在堆排序算法中會(huì)體現(xiàn)出來。

1. 什么叫作順序存儲(chǔ)二叉樹

當(dāng)一顆二叉樹滿足如下兩個(gè)條件時(shí)，就是順序存儲(chǔ)二叉樹：

二叉樹是以數(shù)組的方式存放數(shù)據(jù)的。如下圖所示：

在遍歷數(shù)組時(shí)，仍然可以按照前序遍歷、中序遍歷和后序遍歷的方式來完成節(jié)點(diǎn)的遍歷

2. 順序存儲(chǔ)二叉樹的特點(diǎn)

順序二叉樹通常只考慮完全二叉樹

第n個(gè)元素的左子節(jié)點(diǎn)在數(shù)組中對(duì)應(yīng)的下標(biāo)是2*n + 1

第n個(gè)元素的右子節(jié)點(diǎn)在數(shù)組中對(duì)應(yīng)的下標(biāo)是2*n + 2

第n個(gè)元素的父節(jié)點(diǎn)在數(shù)組中對(duì)應(yīng)的下標(biāo)是(n - 1)/2

其中n表示二叉樹中的第幾個(gè)元素(按照數(shù)組中的下標(biāo)0開始)。

結(jié)合順序二叉樹的示意圖說明：

例如上面二叉樹中的2這個(gè)節(jié)點(diǎn)：

• 節(jié)點(diǎn)2—>在數(shù)組中對(duì)應(yīng)的下標(biāo)是1—>那么它的左子節(jié)點(diǎn)的下標(biāo)為2*1 + 1 = 3，就是節(jié)點(diǎn)4這個(gè)對(duì)象，它的右子節(jié)點(diǎn)的下標(biāo)為2x1+2 = 4，就是節(jié)點(diǎn)5這個(gè)對(duì)象。

• 節(jié)點(diǎn)3—>在數(shù)組中對(duì)應(yīng)的下標(biāo)是2—>那么它的左子節(jié)點(diǎn)的下標(biāo)為2*2 + 1 = 5，就是節(jié)點(diǎn)6這個(gè)對(duì)象，它的右子節(jié)點(diǎn)的下標(biāo)為2x2+2 = 6，就是節(jié)點(diǎn)7這個(gè)對(duì)象。

• 節(jié)點(diǎn)5—>在數(shù)組中對(duì)應(yīng)的下標(biāo)是4—>那么他的父節(jié)點(diǎn)的下標(biāo)為(4-1)/2 = 1，即它的父節(jié)點(diǎn)在數(shù)組中的下標(biāo)為1

3. 順序存儲(chǔ)二叉樹前序、中序、后序遍歷

代碼實(shí)現(xiàn)

//編寫一個(gè)ArrayBinaryTree，實(shí)現(xiàn)順序存儲(chǔ)二叉樹遍歷 class ArrayBinaryTree {private int[] arr;public ArrayBinaryTree(int[] arr) {this.arr = arr;}//重載preOrder方法public void preOrder() {this.preOrder(0);}/*** 順序存儲(chǔ)二叉樹的前序遍歷* @param index 數(shù)組的下標(biāo)*/public void preOrder(int index) {if (arr == null || arr.length == 0) {System.out.println("數(shù)組為空，不能按照二叉樹的前序遍歷");return;}//1. 輸出當(dāng)前這個(gè)元素System.out.print(arr[index] + "\t");//2. 向左遞歸遍歷if ((index * 2 + 1) < arr.length) {preOrder(index * 2 + 1);}//3. 向右遞歸遍歷if ((index * 2 + 2) < arr.length) {preOrder(index * 2 + 2);}}/*** 順序存儲(chǔ)二叉樹的中序遍歷* @param index 數(shù)組的下標(biāo)*/public void infixOrder(int index) {if (arr == null || arr.length == 0) {System.out.println("數(shù)組為空，不能按照二叉樹的中序遍歷");return;}//1. 向左遞歸遍歷if ((index * 2 + 1) < arr.length) {infixOrder(index * 2 + 1);}//2. 輸出當(dāng)前這個(gè)元素System.out.print(arr[index] + "\t");//3. 向右遞歸遍歷if ((index * 2 + 2) < arr.length) {infixOrder(index * 2 + 2);}}/*** 順序存儲(chǔ)二叉樹的后序遍歷* @param index 數(shù)組的下標(biāo)*/public void postOrder(int index) {if (arr == null || arr.length == 0) {System.out.println("數(shù)組為空，不能按照二叉樹的后序遍歷");return;}//1. 向左遞歸遍歷if ((index * 2 + 1) < arr.length) {postOrder(index * 2 + 1);}//2. 向右遞歸遍歷if ((index * 2 + 2) < arr.length) {postOrder(index * 2 + 2);}//3. 輸出當(dāng)前這個(gè)元素System.out.print(arr[index] + "\t");} }

測(cè)試代碼

public class ArrayBinaryTreeDemo {public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 5, 6, 7};//創(chuàng)建一個(gè)ArrayBinaryTreeArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);System.out.println("順序存儲(chǔ)二叉樹前序遍歷");arrayBinaryTree.preOrder();System.out.println("\n順序存儲(chǔ)二叉樹中序遍歷");arrayBinaryTree.infixOrder(0);System.out.println("\n順序存儲(chǔ)二叉樹后序遍歷");arrayBinaryTree.postOrder(0);} }

運(yùn)行結(jié)果

非常感謝您的耐心閱讀，希望我的文章對(duì)您有幫助。歡迎點(diǎn)評(píng)、轉(zhuǎn)發(fā)或分享給您的朋友或技術(shù)群。

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的数据结构——顺序存储二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。