当Kotlin遇见数据结构丨实现中序线索化二叉树并遍历
线索二叉树
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与数据结构原创内容持续更新中~
期待您点击关注或点击头像浏览更多移动端开发技术干货！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019.02.22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
