顺序存储二叉树
顺序存储二叉树的概念
a.基本说明
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，看下面的示意图。
b. 要求:
- 右图的二叉树的结点，要求以数组的方式来存放arr : [1, 2, 3, 4, 5, 6, 6]
- 要求在遍历数组arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历
c.顺序存储二叉树的特点:
- 顺序二叉树通常只考虑完全二叉树
- 第n 个元素的左子节点为2 * n + 1
- 第n 个元素的右子节点为2 * n + 2
- 第n 个元素的父节点为(n-1) / 2
- n : 表示二叉树中的第几个元素(按0 开始编号如图所示)
顺序存储二叉树遍历
需求: 给你一个数组{1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。前序遍历的结果应当为1,2,4,5,3,6,7
代码实现:
public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {
1, 2, 3, 4, 5, 6, 7 };//创建一个 ArrBinaryTreeArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7}}//编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历class ArrBinaryTree {
private int[] arr;//存储数据结点的数组public ArrBinaryTree(int[] arr) {
this.arr = arr;}//重载preOrderpublic void preOrder() {
this.preOrder(0);}//编写一个方法，完成顺序存储二叉树的前序遍历/*** * @param index 数组的下标 */public void preOrder(int index) {
//如果数组为空，或者 arr.length = 0if(arr == null || arr.length == 0) {
System.out.println("数组为空，不能按照二叉树的前序遍历");}//输出当前这个元素System.out.println(arr[index]); //向左递归遍历if((index * 2 + 1) < arr.length) {
preOrder(2 * index + 1 );}//向右递归遍历if((index * 2 + 2) < arr.length) {
preOrder(2 * index + 2);}}}
顺序存储二叉树应用实例
八大排序算法中的堆排序，就会使用到顺序存储二叉树， 关于堆排序，我们放在<<树结构实际应用>> 章节讲解。
线索化二叉树
先看一个问题
将数列{1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7
问题分析:
- 当我们对上面的二叉树进行中序遍历时，数列为{8, 3, 10, 1, 6, 14 }
- 但是6, 8, 10, 14 这几个节点的左右指针，并没有完全的利用上.
- 如果我们希望充分的利用各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?
- 解决方案-线索二叉树
线索二叉树基本介绍
- n 个结点的二叉链表中含有n+1 【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质
的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种 - 一个结点的前一个结点，称为前驱结点
- 一个结点的后一个结点，称为后继结点
线索二叉树应用案例
应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为{8, 3, 10, 1, 14, 6}
思路分析: 中序遍历的结果：{8, 3, 10, 1, 14, 6}
? 说明: 当线索化二叉树后，Node 节点的属性left 和right ，有如下情况:
- left 指向的是左子树，也可能是指向的前驱节点. 比如① 节点left 指向的左子树, 而⑩ 节点的left 指向的就是前驱节点.
- right 指向的是右子树，也可能是指向后继节点，比如① 节点right 指向的是右子树，而⑩ 节点的right 指向的是后继节点.
遍历线索化二叉树
说明：对前面的中序线索化的二叉树， 进行遍历
分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。
? 代码实现：
public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
// 测试一把中序线索二叉树的功能HeroNode root = new HeroNode(1, "tom");HeroNode node2 = new HeroNode(3, "jack");HeroNode node3 = new HeroNode(6, "smith");HeroNode node4 = new HeroNode(8, "mary");HeroNode node5 = new HeroNode(10, "king");HeroNode node6 = new HeroNode(14, "dim");// 二叉树，后面我们要递归创建, 现在简单处理使用手动创建root.setLeft(node2);root.setRight(node3);node2.setLeft(node4);node2.setRight(node5);node3.setLeft(node6);// 测试中序线索化ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();threadedBinaryTree.setRoot(root);threadedBinaryTree.threadedNodes();// 测试: 以10号节点测试HeroNode leftNode = node5.getLeft();HeroNode rightNode = node5.getRight();System.out.println("10号结点的前驱结点是 =" + leftNode); // 3System.out.println("10号结点的后继结点是=" + rightNode); // 1// 当线索化二叉树后，能在使用原来的遍历方法// threadedBinaryTree.infixOrder();System.out.println("使用线索化的方式遍历 线索化二叉树");threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6}}//定义ThreadedBinaryTree 实现了线索化功能的二叉树
class ThreadedBinaryTree {
private HeroNode root;// 为了实现线索化，需要创建要给指向当前结点的前驱结点的指针// 在递归进行线索化时，pre 总是保留前一个结点private HeroNode pre = null;public void setRoot(HeroNode root) {
this.root = root;}// 重载一把threadedNodes方法public void threadedNodes() {
this.threadedNodes(root);}// 遍历线索化二叉树的方法public void threadedList() {
// 定义一个变量，存储当前遍历的结点，从root开始HeroNode node = root;while (node != null) {
// 循环的找到leftType == 1的结点，第一个找到就是8结点// 后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化// 处理后的有效结点while (node.getLeftType() == 0) {
node = node.getLeft();}// 打印当前这个结点System.out.println(node);// 如果当前结点的右指针指向的是后继结点,就一直输出while (node.getRightType() == 1) {
// 获取到当前结点的后继结点node = node.getRight();System.out.println(node);}// 替换这个遍历的结点node = node.getRight();}}// 编写对二叉树进行中序线索化的方法/*** * @param node 就是当前需要线索化的结点*/public void threadedNodes(HeroNode node) {
// 如果node==null, 不能线索化if (node == null) {
return;}// (一)先线索化左子树threadedNodes(node.getLeft());// (二)线索化当前结点[有难度]// 处理当前结点的前驱结点// 以8结点来理解// 8结点的.left = null , 8结点的.leftType = 1if (node.getLeft() == null) {
// 让当前结点的左指针指向前驱结点node.setLeft(pre);// 修改当前结点的左指针的类型,指向前驱结点node.setLeftType(1);}// 处理后继结点if (pre != null && pre.getRight() == null) {
// 让前驱结点的右指针指向当前结点pre.setRight(node);// 修改前驱结点的右指针类型pre.setRightType(1);}// !!! 每处理一个结点后，让当前结点是下一个结点的前驱结点pre = node;// (三)在线索化右子树threadedNodes(node.getRight());}}//先创建HeroNode 结点
class HeroNode {
private int no;private String name;private HeroNode left; // 默认nullprivate HeroNode right; // 默认null// 说明// 1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点// 2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点private int leftType;private int rightType;public int getLeftType() {
return leftType;}public void setLeftType(int leftType) {
this.leftType = leftType;}public int getRightType() {
return rightType;}public void setRightType(int rightType) {
this.rightType = rightType;}public HeroNode(int no, String name) {
this.no = no;this.name = name;}public int getNo() {
return no;}public void setNo(int no) {
this.no = no;}public String getName() {
return name;}public void setName(String name) {
this.name = name;}public HeroNode getLeft() {
return left;}public void setLeft(HeroNode left) {
this.left = left;}public HeroNode getRight() {
return right;}public void setRight(HeroNode right) {
this.right = right;}@Overridepublic String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";}
}
线索二叉树优势与不足
优势
(1)利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。
(2)任意一个结点都能直接找到它的前驱和后继结点。
不足
(1)结点的插入和删除麻烦，且速度也较慢。
(2)线索子树不能共用。
线索二叉树存在的意义
（来自： https://blog.csdn.net/Tangs_/article/details/83040502）
-
百度，google了二十分钟也没看到关于线索二叉树的应用。
线索二叉树减少了的空指针域的同时又对每个节点增加了两个标志位。
如果要遍历树可以用栈或者队列或者递归，那线索二叉树的意义是什么？莫不是学者们强迫症犯了就为了减少空指针域的个数。
书上写着引入线索二叉树是为了加快查找节点前驱和后继的速度，而个人觉得线索二叉树在建立的时候使得树的建立变得复杂了一点点，从逻辑上去想也变得复杂，觉得有点吃力不讨好。
除了考试时可能会考到线索二叉树，其他的用处暂时没发现，有缘再见线索二叉树吧。
终于，发现了一个实际的应用：
当路由器使用CIDR，选择下一跳的时候，或者转发分组的时候，通常会用最长前缀匹配（最佳匹配）来得到路由表的一行数据，为了更加有效的查找最长前缀匹配，使用了一种层次的数据结构中，通常使用的数据结构为二叉线索。
阔以阔以，先留个悬念，后续详解CIDR以及线索二叉树。