1. 什么是线索二叉树?
n个结点的二叉链表中含有(2n-(n-1)=n+1个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前驱和后继结点的指针
(这种附加的指针称为"线索")。这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树。
2. 为什么要加线索?
① 很多空指针域没有存储任何事物,对内存资源是一种浪费。
② 二叉链表中,我们只能知道每个结点指向其左右孩子结点的地址,却不知道每个结点的前驱是谁,后继是谁。
③线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题。
④ 线索二叉树等于把一棵二叉树转变成了一个双向链表,这样我们插入删除某个结点将非常方便。
3. 什么是线索化?
对二叉树以某种次序遍历使其变成线索二叉树的过程称为线索化,线索化的过程就是在遍历过程中修改空指针的过程。
4. 线索二叉树的结构:
leftChild
|
isLeftTag
|
data
|
isRightTag
|
rightChild
|
isLeftTag为0时leftChild指向该结点的左孩子,为1时leftChild指向该结点的前驱;
isRightTag为0时rightChild指向该结点的右孩子,为1时rightChild指向该结点的后继;
注意:isLeftTag,isRightTag只是存放0或1数字的布尔型变量,isLeftTag用于区分leftChild指向左孩子还是前驱,
isRightTag用于区分rightChild指向右孩子还是后继,其占用的内存空间要小于像leftChild和rightChild这样的指针变量。
5. Java实现线索二叉树:
public class ThreadTree {
private Node root;// 根节点
private Node preNode;// 线索化的时候保存前驱
/**
* 内部节点类
*/
private class Node {
private int data;
private Node leftChild; // 左孩子节点
private Node rightChild; // 右孩子节点
private boolean isLeftTag; // 左孩子标志域
private boolean isRightTag; // 右孩子标志域
public Node(int data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.isLeftTag = false; // leftTag为0时指向该结点的左孩子,为1时指向该结点的前驱
this.isRightTag = false; // rightTag为0时指向该结点的右孩子,为1时指向该结点的后继
}
}
public ThreadTree() {
this.root = null;
this.preNode = null;
}
/**
* 递归创建二叉树
*
* @param node
* @param data
*/
public void buildTree(Node node, int data) {
if (root == null) {
root = new Node(data);
} else {
if (data < node.data) {
if (node.leftChild == null) {
node.leftChild = new Node(data);
} else {
buildTree(node.leftChild, data); // 递归遍历左子树
}
} else {
if (node.rightChild == null) {
node.rightChild = new Node(data);
} else {
buildTree(node.rightChild, data); // 递归遍历右子树
}
}
}
}
/**
* 中序遍历将二叉树线索化
*
* @param node
*/
public void inThreading(Node node) {
if (node != null) {
inThreading(node.leftChild); // 线索化左子树(递归)
if (node.leftChild == null) { // 没有左孩子
node.isLeftTag = true; // 前驱线索
node.leftChild = preNode; // 左孩子指针指向前驱
}
if (preNode != null && preNode.rightChild == null) { // 前驱没有右孩子
preNode.isRightTag = true; // 后继线索
preNode.rightChild = node; // 前驱右孩子指针指向后继
}
preNode = node;
inThreading(node.rightChild); // 线索化右子树(递归)
}
}
/**
* 中序遍历线索二叉树
*
* @param node
*/
public void inOrderThread(Node node) {
if (node != null) {
while (node != null && !node.isLeftTag) { // 如果左孩子不是线索
node = node.leftChild;
}
do {
System.out.print(" " + node.data + " ");
if (node.isRightTag) { // 如果右孩子是线索
node = node.rightChild;
} else { // 有右孩子
node = node.rightChild;
while (node != null && !node.isLeftTag) {
node = node.leftChild;
}
}
} while (node != null);
}
}
/**
* 测试类
* @param args
*/
public static void main(String[] args) {
int[] arr = { 6, 4, 8, 1, 7, 3, 9, 2, 5 };
ThreadTree threadTree = new ThreadTree();
for (int i = 0; i < arr.length; i++) {
threadTree.buildTree(threadTree.root, arr[i]); // 构建一棵二叉树
}
threadTree.inThreading(threadTree.root);// 采用中序遍历将二叉树线索化
threadTree.inOrderThread(threadTree.root);// 中序遍历线索二叉树
}
}
分享到:
相关推荐
数据结构课程设计:平衡二叉树
自己做的线索二叉树,数据结构课设的时候可以参考哦!编译过的cpp文件。欢迎下载!
数据结构实验十:树及二叉树的应用试验
数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏
数据结构树和二叉树遍历二叉树和线索二叉树PPT学习教案.pptx
实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树存储结构 2.求二叉树的先序遍历 3.求二叉树...
本节主要讲述二叉树的线索链表存储结构和相关操作
添加、删除、拷贝、清空、树深度计算、父节点、兄弟节点获取、先中后序递归及非遍历、按层次遍历、中序迭代器(非递归算法)、节点查找、先序和中序序列重建二叉树、数组和二叉链表存储结构相互转换。使用模板偏特化...
线索二叉树的数据结构课程设计 包括需求分析,说明书,源代码
数据结构 课程设计 建立二叉树并求指定结点路径 包含该课程设计的文档、调试报告、以及源代码等
数据结构 树与二叉树 线索二叉树 关于树与二叉树的线索二叉树小节课件
此程序需要完成如下要求:建立线索二叉树,并实现线索二叉树的插入、删除和恢复线索的实现。
数据结构教学课件:第11-2讲 线索二叉树.pdf
南邮数据结构实验使用C++描述,二叉树的基本操作
线索二叉树的数据结构课程设计 包括需求分析,说明书,源代码
东北大学数据结构实验3 树和二叉树 实验报告,有代码。
VC++2012编程演练数据结构《25》线索二叉树
数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,...