java数据结构和算法——线索化二叉树

目录

一、二叉树问题分析二、线索二叉树的基本介绍三、中序线索化二叉树思路分析四、中序线索化二叉树代码示例五、遍历线索化二叉树代码示例

一、二叉树问题分析

1、将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树，如下图： 2、问题分析:

当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }但是 6, 8, 10, 14 这几个节点的左右指针，并没有完全的利用上.如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?解决方案------>线索二叉树

二、线索二叉树的基本介绍

n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向 该结点在 某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）这种加上了线索的二叉链表称为线索链表 ，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同， 线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种一个结点的前一个结点，称为前驱结点一个结点的后一个结点，称为后继结点

三、中序线索化二叉树思路分析

四、中序线索化二叉树代码示例

1、代码

package com.rf.springboot01.dataStructure.tree; /** * @description: 中序线索二叉树示例 * @author: xiaozhi * @create: 2020-09-03 22:38 */ public class ThreadedBinaryTreeDemo { public static void main(String[] args) { //创建节点 Nodes root = new Nodes(1); Nodes node2 = new Nodes(3); Nodes node3 = new Nodes(6); Nodes node4 = new Nodes(8); Nodes node5 = new Nodes(10); Nodes node6 = new Nodes(14); //手动创建二叉树 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号节点测试 Nodes leftNode = node5.getLeft(); Nodes rightNode = node5.getRight(); System.out.println("10号结点的前驱结点是 =" + leftNode); //3 System.out.println("10号结点的后继结点是=" + rightNode); //1 } } /** * @Description: 创建ThreadedBinaryTree， 实现了线索化功能的二叉树 * @Param: * @Author: xz * @return: * @Date: 2020/9/3 22:44 */ class ThreadedBinaryTree{ private Nodes root; public void setRoot(Nodes root) { this.root = root; } //重载一把threadedNodes方法 public void threadedNodes() { this.threadedNodes(root); } //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针 //在递归进行线索化时，pre 总是保留前一个结点 private Nodes pre = null; //编写对二叉树进行中序线索化的方法 public void threadedNodes(Nodes nodes){ //如果nodes==null, 不能线索化 if(nodes == null){ return; } //一、先线索化左子树 threadedNodes(nodes.getLeft()); //二、处理当前结点的前驱结点 //以8结点的.left = null , 8结点的.leftType = 1 if(nodes.getLeft() == null) { //让当前结点的左指针指向前驱结点 nodes.setLeft(pre); //修改当前结点的左指针的类型,指向前驱结点 nodes.setLeftType(1); } //三、处理后继结点 if (pre != null && pre.getRight() == null) { //让前驱结点的右指针指向当前结点 pre.setRight(nodes); //修改前驱结点的右指针类型 pre.setRightType(1); } //!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点 pre = nodes; //四、先线索化右子树 threadedNodes(nodes.getRight()); } } /** * @Description: 创建 Nodes 结点 * @Param: * @Author: xz * @return: * @Date: 2020/9/3 22:41 */ class Nodes{ private int no; private Nodes left;//二叉树的左节点，默认null private Nodes right;//二叉树的右节点，默认null private int leftType;//0 表示指向的是左子树;1 表示指向前驱结点 private int rightType;//0 表示指向是右子树;1表示指向后继结点 //构造方法 public Nodes(int no) { this.no = no; } //setter、getter方法 public int getNo() { return no; } public void setNo(int no) { this.no = no; } public Nodes getLeft() { return left; } public void setLeft(Nodes left) { this.left = left; } public Nodes getRight() { return right; } public void setRight(Nodes right) { this.right = right; } 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; } @Override public String toString() { return "Nodes{" + "no=" + no + '}'; } }

2、运行main函数，输出结果如下：

五、遍历线索化二叉树代码示例

1、在ThreadedBinaryTree类中添加遍历线索化二叉树的方法

//遍历线索化二叉树的方法 public void threadedList() { //定义一个变量，存储当前遍历的结点，从root开始 Nodes 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(); } }

2、在ThreadedBinaryTreeDemo类中添加如下调用方法

System.out.println("使用线索化的方式遍历线索化二叉树====="); threadedBinaryTree.threadedList(); //输出： 8, 3, 10, 1, 14, 6

3、输出结果如下