数据结构之二叉树篇卷四 -- 二叉树线索化（With Java)
2024-08-31 10:26:38
一、线索二叉树简介
二叉树本身是一种非线性结构，然而当你对二叉树进行遍历时，你会发现遍历结果是一个线性序列。这个序列中的节点存在前驱后继关系。因此，如何将这种前驱后继信息赋予给原本的二叉树呢？这就是二叉树的线索化过程。所以可以通过丰富原有的二叉树构建一棵可以知道结点的前驱后继的新的二叉树，我们叫它线索二叉树。
二、构建线索二叉树
2.1 定义线索二叉树节点
public class ThreadNode<E> {
public E data;
public ThreadNode<E> lnode;
public ThreadNode<E> rnode;
enum tag {CHILD, THREAD};
public tag ltag;
public tag rtag;
public ThreadNode(E data){
this.data = data;
ltag = tag.CHILD;
rtag = tag.CHILD;
}
public ThreadNode(){}
}
为了充分利用二叉树的空指针域，我们可以将结点线索依附在这些空指针中。这样一来，在我们访问根节点的左右节点时，我们必须要区分什么时候是线索，什么时候子女指针。因此为每个节点设置两个标志位。
2.2 建立线索二叉树
在遍历二叉树的时候顺便进行线索化。线索化就是每遇到一个节点存在空指针域就要立即填上它的前驱（左指针空）或者后继（右指针空）。
/**
* 利用中序非递归遍历对二叉树进行线索化
* @author sheepcore
*/
public void createInThread(){
if(root == null)
return;
ThreadNode<E> pre = null;
ThreadNode<E> cur = root;
MyStack<ThreadNode<E>> stack = new MyStack<>();
while (cur != null || !stack.isEmpty()) {
while (cur != null){
stack.push(cur);
cur = cur.lnode;
}
if(!stack.isEmpty()){
cur = stack.pop();
if(cur.lnode == null) { //当前节点的前驱作为线索
cur.lnode = pre;
cur.ltag = ThreadNode.tag.THREAD;
}
if(pre != null && pre.rnode == null){
pre.rnode = cur; //当前节点的前驱的后继节点是当前节点
pre.rtag = ThreadNode.tag.THREAD;
}
pre = cur;
if(cur.rnode != null){
cur = cur.rnode;
}
else
cur = null; } //if
} //while
}
2.3 遍历线索二叉树
以中序线索二叉树的遍历为例。getFirst(root) 和 getNext(root) 分别是获取中序遍历中以 root 为根的第一个访问的节点和 root 的后继节点。这两个辅助函数在最后面的完整代码有实现。
public void inOrder(ThreadNode<E> root){
ThreadNode<E> cur;
for (cur = getFirst(root); cur != null; cur = getNext(cur)) {
visit(cur);
}
}
2.4 完整代码
public class ThreadTree <E> {
private ThreadNode<E> root;
/**
* using for construct a binary tree with its element as an integer
*/
public ArrayList<Integer> list;
public ThreadNode<E> getRoot() { return root; }
public ThreadTree(){
list = new ArrayList<>();
}
/**
* build a binary tree in a preorder way recursively
* @return root
* @author sheepcore
*/
public ThreadNode<E> generate() {
if(list.isEmpty())
return null;
int data = list.get(0);
list.remove(0);
ThreadNode<E> node;
if(data != -1) {
node = (ThreadNode<E>) new ThreadNode<Integer>(data);
node.lnode = generate(); //generate left subtree
node.rnode = generate(); //generate right subtree
return node;
}
else
return null;
}
/**
* build a binary tree in preorder
* @param treeSequence "1 2 -1 -1 3 -1 -1 "
*/
public void preOderBuild(String treeSequence) {
String[] nodes = treeSequence.split("\\s+");
for (int i = 0; i < nodes.length; i++) {
list.add(Integer.parseInt(nodes[i]));
}
root = generate();
}
/**
* 利用中序非递归遍历对二叉树进行线索化
* @author sheepcore
*/
public void createInThread(){
if(root == null)
return;
ThreadNode<E> pre = null;
ThreadNode<E> cur = root;
MyStack<ThreadNode<E>> stack = new MyStack<>();
while (cur != null || !stack.isEmpty()) {
while (cur != null){
stack.push(cur);
cur = cur.lnode;
}
if(!stack.isEmpty()){
cur = stack.pop();
if(cur.lnode == null) { //当前节点的前驱作为线索
cur.lnode = pre;
cur.ltag = ThreadNode.tag.THREAD;
}
if(pre != null && pre.rnode == null){
pre.rnode = cur; //当前节点的前驱的后继节点是当前节点
pre.rtag = ThreadNode.tag.THREAD;
}
pre = cur;
if(cur.rnode != null){
cur = cur.rnode;
}
else
cur = null;
} //if
} //while
}
public ThreadNode<E> getFirst(ThreadNode<E> root){
ThreadNode<E> cur = root;
while (cur != null && cur.ltag == ThreadNode.tag.CHILD){
cur = cur.lnode;
}
return cur;
}
public ThreadNode<E> getLast(ThreadNode<E> root){
ThreadNode<E> cur = root;
while (cur != null && cur.rtag == ThreadNode.tag.CHILD){
cur = cur.rnode;
}
return cur;
}
public ThreadNode<E> getNext(ThreadNode<E> root){
ThreadNode<E> cur = root;
if(cur.rtag == ThreadNode.tag.THREAD)
return cur.rnode;
else
return getFirst(cur.rnode);
}
public ThreadNode<E> getPrior(ThreadNode<E> root){
ThreadNode<E> cur = root;
if(cur.ltag == ThreadNode.tag.THREAD)
return cur.lnode;
else
return getLast(cur.lnode);
}
public void visit(ThreadNode<E> root){
if(root != null && root.data != null){
System.out.print(root.data);
System.out.print("\t");
}
}
/**
* inorder traversal
* @param root
* @author sheepcore
*/
public void inOrder(ThreadNode<E> root){
ThreadNode<E> cur;
for (cur = getFirst(root); cur != null; cur = getNext(cur)) {
visit(cur);
}
}
public static void main(String[] args) {
String str = "0 1 -1 3 -1 -1 2 4 -1 -1 -1";
ThreadTree<Integer> threadTree = new ThreadTree<>();
threadTree.preOderBuild(str);
threadTree.createInThread();
threadTree.inOrder(threadTree.getRoot());
}
}
最新文章
- JQuery中的工具函数总结
- ubuntu无限卡在logo界面
- .NET程序员走向高端必读书单汇总
- SQL Challenge ——快速找到1-100之间缺失的数
- 在没有安装有mvc3的主机上部署asp.net mvc3网站，需要包含的DLL文件
- 信息安全系统设计基础exp_3
- scala言语基础学习
- CentOS6.5安装图形界面
- win7配置nginx + php
- UISearchController的使用。（iOS8＋）
- 使用 Infragistics 的 NetAdvantage 组件时替换部分菜单语言的方法
- NYOJ-104最大和
- 简单概率dp(期望)-zoj-3640-Help Me Escape
- Lombok 使用小结
- 秦俊：开放 DevOps 敏捷开发套件，助力开发者驰骋云端
- 解决ajax跨域访问sessionid不一致问题
- map put值 使用匿名函数
- EF延迟加载和懒加载
- 20155233 《网络对抗》 Exp5 MSF基础应用
- Beta阶段冲刺-6
热门文章
- BZOJ 3667: Rabin-Miller算法 (Pollard-Rho 模板)
- MessagePack Java Jackson 在不关闭输出流（output stream）的情况下序列化多变量
- eclipse打开项目中文件时左侧project explorer同时展开该文件的路径
- fiddler(四)、断点（转）
- BZOJ1123 BLO
- Windows环境下Zookeeper的安装和部署(单机模式和伪集群模式)
- 一、Git的一些命令操作----创建版本库、增加文件到Git库、时光机穿梭、远程仓库
- Druid连接池(无框架)
- 源码分析系列1：HashMap源码分析（基于JDK1.8）
- itertools模块中的product方法