線索二叉樹
n個節點的二叉樹含有n+1個空指針域。利用這些空指針域，存放指向節點的在某種遍歷次序下的前驅節點及後繼節點的指針，這種附加的指針稱為"線索"，加上了線索的二叉樹就是"線索二叉樹"。
根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹三種。
線索化二叉樹的本質是將一個複雜的非線性結構轉換為線性結構，使每一個節點都有了唯一的前驅節點和後續節點（第一個節點無前驅，最後一個節點無後繼）。
前驅節點：線索化二叉樹時，某節點的前一個節點叫前驅節點
後繼節點：線索化二叉樹時，某節點的後一個節點叫後繼節點
Kotlin 中如何線索化二叉樹
/**
* 中序線索化二叉樹
* */
fun midThreadNodes(node:ThreadTreeNode?){
// 當遞歸到最右側葉子結點則結束
if (null == node){
return
}
// 處理左子樹
midThreadNodes(node?.leftNode)
// ① 處理左指針
if (null == node.leftNode){
// 賦值前驅節點
node.leftNode = preNode
// 改變當前節點左指針類型
node.leftType = 1
}
// ② 處理前驅節點的右指針，如果上一個節點的右子節點為null
if (null != preNode && preNode?.rightNode == null){
// 讓前驅節點的右指針指向當前節點
preNode?.rightNode = node
// 修改前驅節點的右指針類型
preNode?.rightType = 1
}
// ③ 處理右指針，存儲當前節點為下一個節點的前驅節點
preNode = node
// 處理右子樹
midThreadNodes(node?.rightNode)
}
Kotlin 中線索二叉樹如何遍歷
/**
* 遍歷線索二叉樹
* */
fun iterateTree(){
var root:ThreadTreeNode? = rootNode
// 循環遍歷，直到最後一個節點
while (null != root){
// 循環找到最左側節點
while (root?.leftType == 0){
root = root.leftNode
}
// 打印最左側節點的節點權
Log.e("==",""+root?.value)
// 判斷最左側節點是否存在後繼節點，有則持續打印節點權
while (root?.rightType == 1){
root = root?.rightNode
Log.e("==",""+root?.value)
}
// 替換遍歷節點
root = root?.rightNode
}
}
運行結果
國際慣例
貼上完整源碼
ThreadBianryTree.kt
/**
* @des 線索二叉樹Bean
* @author liyongli 20190221
*
* @param rootNode : 二叉樹的根節點
* @param preNode : 臨時存儲的前驅節點
* */
data class ThreadBianryTree(var rootNode: ThreadTreeNode?, var preNode:ThreadTreeNode? = null) {
/**
* 遍歷線索二叉樹
* */
fun iterateTree(){
var root:ThreadTreeNode? = rootNode
// 循環遍歷，直到最後一個節點
while (null != root){
// 循環找到最左側節點
while (root?.leftType == 0){
root = root.leftNode
}
// 打印節點權
ThreadBinaryTreeActivity.afterResult.append(root?.value).append(" ")
// 判斷是否存在後繼節點，有則持續打印節點權
while (root?.rightType == 1){
root = root?.rightNode
ThreadBinaryTreeActivity.afterResult.append(root?.value).append(" ")
}
// 替換遍歷節點
root = root?.rightNode
}
}
/**
* 中序線索化二叉樹
* */
fun threadNodes(){
midThreadNodes(rootNode)
}
/**
* 中序線索化二叉樹
* */
fun midThreadNodes(node:ThreadTreeNode?){
// 當遞歸到最右側葉子結點則結束
if (null == node){
return
}
// 處理左子樹
midThreadNodes(node?.leftNode)
// ① 處理左指針
if (null == node.leftNode){
// 賦值前驅節點
node.leftNode = preNode
// 改變當前節點左指針類型
node.leftType = 1
}
// ② 處理前驅節點的右指針，如果上一個節點的右子節點為null
if (null != preNode && preNode?.rightNode == null){
// 讓前驅節點的右指針指向當前節點
preNode?.rightNode = node
// 修改前驅節點的右指針類型
preNode?.rightType = 1
}
// ③ 處理右指針，存儲當前節點為下一個節點的前驅節點
preNode = node
// 處理右子樹
midThreadNodes(node?.rightNode)
}
}
ThreadBinaryTreeActivity.kt
/**
* @des 線索二叉樹Bean
* @author liyongli 20190221
*
* @param rootNode : 二叉樹的根節點
* @param preNode : 臨時存儲的前驅節點
* */
data class ThreadBianryTree(var rootNode: ThreadTreeNode?, var preNode:ThreadTreeNode? = null) {
/**
* 遍歷線索二叉樹
* */
fun iterateTree(){
var root:ThreadTreeNode? = rootNode
// 循環遍歷，直到最後一個節點
while (null != root){
// 循環找到最左側節點
while (root?.leftType == 0){
root = root.leftNode
}
// 打印節點權
ThreadBinaryTreeActivity.afterResult.append(root?.value).append(" ")
// 判斷是否存在後繼節點，有則持續打印節點權
while (root?.rightType == 1){
root = root?.rightNode
ThreadBinaryTreeActivity.afterResult.append(root?.value).append(" ")
}
// 替換遍歷節點
root = root?.rightNode
}
}
/**
* 中序線索化二叉樹
* */
fun threadNodes(){
midThreadNodes(rootNode)
}
/**
* 中序線索化二叉樹
* */
fun midThreadNodes(node:ThreadTreeNode?){
// 當遞歸到最右側葉子結點則結束
if (null == node){
return
}
// 處理左子樹
midThreadNodes(node?.leftNode)
// ① 處理左指針
if (null == node.leftNode){
// 賦值前驅節點
node.leftNode = preNode
// 改變當前節點左指針類型
node.leftType = 1
}
// ② 處理前驅節點的右指針，如果上一個節點的右子節點為null
if (null != preNode && preNode?.rightNode == null){
// 讓前驅節點的右指針指向當前節點
preNode?.rightNode = node
// 修改前驅節點的右指針類型
preNode?.rightType = 1
}
// ③ 處理右指針，存儲當前節點為下一個節點的前驅節點
preNode = node
// 處理右子樹
midThreadNodes(node?.rightNode)
}
}
本篇到此完結，更多Kotlin與數據結構原創內容持續更新中~
期待您點擊關注或點擊頭像瀏覽更多移動端開發技術乾貨！
分享到:
