数据结构-线索化二叉树

一、先看一个问题

将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7

线索化二叉树 - 图1

问题分析:

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

解决方案-线索二叉树

二、基本介绍

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

三、线索二叉树应用案例

应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}

线索化二叉树 - 图2

思路分析: 中序遍历的结果：{8, 3, 10, 1, 14, 6}

线索化二叉树 - 图3

根据中序遍历的结构 {8, 3, 10, 1, 14, 6}

8 节点 没有前序节点，后继节点为 3 节点

3 节点已经存在左右节点，所以没有前驱节点、后继节点

10 节点的没有左右节点，前驱节点为 3 节点，后继节点为 1 节点

1 节点已经存在左右节点，所以没有前驱节点、后继节点

14 节点没有左右节点，有前驱节点 1 节点，后继节点 6 节点

6 节点有左节点 14 节点，没有右节点，没有前驱节点、后继节点

说明:

当线索化二叉树后，Node 节点的 属性 left 和 right ，有如下情况:

left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的 就是前驱节点.

right 指向的是右子树，也可能是指向后继节点，比如 ① 节点 right 指向的是右子树，而⑩ 节点的 right 指向 的是后继节点

代码实现：

  1. public class ThreadedBinaryTreeDemo {
  2.     public static void main(String[] args) {
  3.         //测试一把中序线索二叉树的功能
  4.         HeroNode root = new HeroNode(1, "tom");
  5.         HeroNode node2 = new HeroNode(3, "jack");
  6.         HeroNode node3 = new HeroNode(6, "smith");
  7.         HeroNode node4 = new HeroNode(8, "mary");
  8.         HeroNode node5 = new HeroNode(10, "king");
  9.         HeroNode node6 = new HeroNode(14, "dim");
  11.         //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
  12.         root.setLeft(node2);
  13.         root.setRight(node3);
  14.         node2.setLeft(node4);
  15.         node2.setRight(node5);
  16.         node3.setLeft(node6);
  18.         //测试中序线索化
  19.         ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
  20.         threadedBinaryTree.setRoot(root);
  21.         threadedBinaryTree.threadedNodes();
  23.         //测试: 以 10 号节点测试
  24.         HeroNode leftNode = node5.getLeft();
  25.         HeroNode rightNode = node5.getRight();
  26.         System.out.println("10 号结点的前驱结点是 =" + leftNode); //3
  27.         System.out.println("10 号结点的后继结点是=" + rightNode); //1
  28.     }
  29. }
  31. //定义 ThreadedBinaryTree 实现了线索化功能的二叉树
  32. class ThreadedBinaryTree {
  33.     private HeroNode root;
  34.     //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
  35.     //在递归进行线索化时，pre 总是保留前一个结点
  36.     private HeroNode pre = null;
  37.     public void setRoot(HeroNode root) {
  38.         this.root = root;
  39.     }
  40.     //重载一把 threadedNodes 方法
  41.     public void threadedNodes() {
  42.         this.threadedNodes(root);
  43.     }
  44.     //编写对二叉树进行中序线索化的方法
  45.     /**
  46.     *
  47.     * @param node 就是当前需要线索化的结点
  48.     */
  49.     public void threadedNodes(HeroNode node) {
  50.         //如果 node==null, 不能线索化
  51.         if(node == null) {
  52.             return;
  53.         }
  54.         //(一)先线索化左子树
  55.         threadedNodes(node.getLeft());
  56.         //(二)线索化当前结点[有难度]
  57.         //处理当前结点的前驱结点
  58.         //以 8 结点来理解
  59.         //8 结点的.left = null , 8 结点的.leftType = 1
  60.         if(node.getLeft() == null) {
  61.             //让当前结点的左指针指向前驱结点
  62.             node.setLeft(pre);
  63.             //修改当前结点的左指针的类型,指向前驱结点
  64.             node.setLeftType(1);
  65.         }
  66.         //处理后继结点
  67.         if (pre != null && pre.getRight() == null) {
  68.             //让前驱结点的右指针指向当前结点
  69.             pre.setRight(node);
  70.             //修改前驱结点的右指针类型
  71.             pre.setRightType(1);
  72.         }
  73.         //!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点
  74.         pre = node;
  75.         //(三)在线索化右子树
  76.         threadedNodes(node.getRight());
  77.     }
  79. }
  81. //先创建 HeroNode 结点
  82. class HeroNode {
  83.     private int no;
  84.     private String name;
  85.     private HeroNode left; //默认 null
  86.     private HeroNode right; //默认 null
  87.     //说明
  88.     //1. 如果 leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
  89.     //2. 如果 rightType == 0 表示指向是右子树, 如果 1 表示指向后继结点
  90.     private int leftType;
  91.     private int rightType;
  92.     public int getLeftType() {
  93.         return leftType;
  94.     }
  95.     public void setLeftType(int leftType) {
  96.         this.leftType = leftType;
  97.     }
  98.     public int getRightType() {
  99.         return rightType;
  100.     }
  101.     public void setRightType(int rightType) {
  102.         this.rightType = rightType;
  103.     }
  104.     public HeroNode(int no, String name) {
  105.         this.no = no;
  106.         this.name = name;
  107.     }
  108.     public int getNo() {
  109.         return no;
  110.     }
  111.     public void setNo(int no) {
  112.         this.no = no;
  113.     }
  114.     public String getName() {
  115.         return name;
  116.     }
  117.     public void setName(String name) {
  118.         this.name = name;
  119.     }
  120.     public HeroNode getLeft() {
  121.         return left;
  122.     }
  123.     public void setLeft(HeroNode left) {
  124.         this.left = left;
  125.     }
  126.     public HeroNode getRight() {
  127.         return right;
  128.     }
  129.     public void setRight(HeroNode right) {
  130.         this.right = right;
  131.     }
  132.     @Override
  133.     public String toString() {
  134.         return "HeroNode [no=" + no + ", name=" + name + "]";
  135.     }
  136. }