本例中樹結構、節點權如下圖所示
- 順序存儲是指將二叉樹存儲在一個數組中，通過存儲元素的下標反映元素之間的父子關係。任何一個二叉樹都可以轉換為數組，同理，任何一個數組都可以轉換為二叉樹。
- 順序存儲的二叉樹通常只考慮完全二叉樹（滿二叉樹其實也是一個完全二叉樹）
- 第N個元素的左子節點為：2*N+1
- 第N個元素的右子節點為：2*N+1
- 第N個元素的父節點為：（N-1）/ 2（整數相除得整數）
1. Kotlin 中順序存儲的二叉樹如何創建
1.1 新建順序存儲的二叉樹 Bean：ArrayBianryTree.kt
/**
* @des 順序存儲二叉樹Bean
* @author liyongli 20190220
*
* @param data 準備遍歷的數組，不可為null
* */
data class ArrayBianryTree(var data:IntArray) {}
注意：在 Kotlin 中使用 data class 聲明類時，可以直接創建一個包含 getters、 setters、 equals()、 hashCode()、 toString() 以及 copy() 的 POJO，大大減少了樣板代碼數量，這是 Kotlin 的一大特色！
1.2 新建聲明樹對象並賦值的 Activity： ArrayBinaryTreeActivity.kt
// 定義數組對象 var data:IntArray? = intArrayOf(1,2,3,4,5,6,7) // 初始化順序存儲的二叉樹對象 var arrayBinary:ArrayBianryTree = ArrayBianryTree(data!!)
注意：變量 data 使用 "?" 修飾表示變量值可為空。"ArrayBianryTree(data!!)" 表示當變量 data 為空時拋出NPE異常
2. Kotlin 中順序存儲的二叉樹如何遍歷
2.1 Bean 中創建前序遍歷方法： frontShow(index:Int)
/**
* 順序存儲的二叉樹前序遍歷
*
* @param index 遍歷的起點，不可為null
* */
fun frontShow(index:Int) {
// 注意，此處不做非空判斷是因為：此方法對傳參的要求未加“?”號，即為非空參數！
if(data.size == 0 ){
return
}
// 輸出當前節點值
ArrayBinaryTreeActivity.frontResult.append(" " + data[index] + " , ")
// 遍歷左子節點值（第N個元素的左子節點為：2*N+1）
if(2*index+1 < data.size){
frontShow(2*index+1)
}
// 遍歷右子節點值（第N個元素的右子節點為：2*N+1）
if(2*index+2 < data.size){
frontShow(2*index+2)
}
}
2.2 Activity 中調用遍歷方法 frontShow() 並更新UI
// 從0開始遍歷二叉樹 arrayBinary.frontShow(0) // 更新UI frontTv.text = frontResult
運行結果
貼上兩個類的完整代碼
ArrayBianryTree.kt
/**
* @des 順序存儲二叉樹Bean
* @author liyongli 20190220
*
* @param data 準備遍歷的數組，不可為null
* */
data class ArrayBianryTree(var data:IntArray) {
/**
* 順序存儲的二叉樹前序遍歷
*
* @param index 遍歷的起點，不可為null
* */
fun frontShow(index:Int) {
// 注意，此處不做非空判斷是因為：此方法對傳參的要求未加“?”號，即為非空參數！
if(data.size == 0 ){
return
}
// 輸出當前節點值
ArrayBinaryTreeActivity.frontResult.append(" " + data[index] + " , ")
// 遍歷左子節點值
if(2*index+1 < data.size){
frontShow(2*index+1)
}
// 遍歷右子節點值
if(2*index+2 < data.size){
frontShow(2*index+2)
}
}
}
ArrayBinaryTreeActivity.kt
/**
* @des 創建順序存儲的二叉樹並遍歷
* @author liyongli 20190220
* */
class ArrayBinaryTreeActivity : AppCompatActivity() {
companion object {
// 遍歷結果
var frontResult:StringBuffer = StringBuffer()
}
override fun onCreate(savedInstanceState: Bundle?) {
super.onCreate(savedInstanceState)
setContentView(R.layout.activity_binary_tree)
// 定義數組對象
var data:IntArray? = intArrayOf(1,2,3,4,5,6,7)
// 初始化順序存儲的二叉樹對象
var arrayBinary:ArrayBianryTree = ArrayBianryTree(data!!)
// 從0開始遍歷二叉樹
arrayBinary.frontShow(0)
// 更新UI
frontTv.text = frontResult
}
}
本篇到此完結，更多Kotlin與數據結構原創內容持續更新中~
歡迎您點擊關注或點擊頭像瀏覽更多移動端開發技術乾貨！
分享到:
