目录

线索二叉树

基本介绍

二叉树可以使用两种存储结构:顺序存储和二叉链表。在使用二叉链表的存储结构的过程中,会存在大量的空指针域,为了充分利用这些空指针域,引申出了“线索二叉树”。回顾一下二叉链表存储结构,如下图: https://gitee.com/lienhui68/picStore/raw/master/null/20200627155902.png

观察上图可知n个节点有2n个指针,除了根节点外每个节点使用一个指针,剩余2n-(n-1)=n+1个指针,从存储空间的角度来看,这n+1个空指针域浪费了内存资源。 从另外一个角度来分析,如果我们想知道按中序方式遍历二叉链表时B节点的前驱节点或者后继节点时,必须要按中序方式遍历二叉链表才能够知道结果,每次需要结果时都需要进行一次遍历,是否可以考虑提前存储这种前驱和后继的关系来提高时间效率呢? 综合以上两方面的分析,可以通过充分利用二叉链表中的空指针域,存放节点在某种遍历方式下的前驱和后继节点的指针。我们把这种指向前驱和后继的指针成为线索,加上线索的二叉链表成为线索链表,对应的二叉树就成为“线索二叉树(Threaded Binary Tree)” 。

根据线索性质 的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 一个结点的前一个结点,称为前驱结点,一个结点的后一个结点,称为后继结点。

构建线索二叉树过程

以中序遍历为例,先将所有的节点右子节点为空的指针域指向它的后继节点,再将这颗二叉树的所有节点左指针为空的指针指向它的前驱节点。结果如下: https://gitee.com/lienhui68/picStore/raw/master/null/20200627160608.png

通过观察上图(蓝色虚线代表后继、绿色虚线代表前驱),可以看出,线索二叉树,等于是把一棵二叉树转变成了一个“特殊的双向链表“,这样对于我们的新增、删除、查找节点带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。如下图: https://gitee.com/lienhui68/picStore/raw/master/null/20200627163543.png

仔细分析上面的双向链表,与线索化之后的二叉树相比,比如节点D与后继节点I,在完成线索化之后,并没有直接线索指针,而是存在父子节点的指针;节点A与节点F,在线索化完成之后,节点A并没有直接指向后继节点F的线索指针,而是通过父子节点遍历可以找到最终的节点F,前驱节点也存在同样的问题,正因为很多节点之间不存在直接的线索,所以我将此双向链表称做“特殊的双向链表”,再使用过程中根据指针是线索指针还是子节点指针来分别处理,所以在每个节点需要标明当前的左右指针是线索指针还是子节点指针,这就需要修改节点的数据结构。修改后的数据结构如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
     * 指针类型
     */
    enum POINTER_TYPE {
        NODE,// 父子节点指针
        THREAD; // 线索指针
    }

    /**
     * 定义节点
     *
     * @param <T>
     */
    static class Node<T> {
        T data;
        Node left;
        Node right;
        POINTER_TYPE leftPointerType; // 左指针类型
        POINTER_TYPE rightPointerType; // 右指针类型

        public Node(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

代码实现

中序线索化及前驱遍历和后继遍历

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
package com.eh.ftd.dsa.ds;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/27 16:38
 */
public class ThreadedBinaryTree {
    // 临时指针,在前序/中序/后序 遍历时用来表示当前节点的前一个节点
    Node pre;

    /**
     * 指针类型
     */
    enum POINTER_TYPE {
        NODE,// 父子节点指针
        THREAD; // 线索指针
    }

    /**
     * 定义节点
     *
     * @param <T>
     */
    static class Node<T> {
        T data;
        Node left;
        Node right;
        POINTER_TYPE leftPointerType; // 左指针类型
        POINTER_TYPE rightPointerType; // 右指针类型

        public Node(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    /**
     * 根据数组构建一个完全二叉树
     *
     * @param arr
     * @param index
     * @return
     */
    private Node createBinaryTreeByArray(int[] arr, int index) {
        if (index >= arr.length) {
            return null;
        }
        Node left = createBinaryTreeByArray(arr, 2 * index + 1);
        Node right = createBinaryTreeByArray(arr, 2 * index + 2);
        Node node = new Node(arr[index]);
        node.left = left;
        node.right = right;
        return node;
    }

    /**
     * 中序线索化二叉树
     *
     * @param node
     */
    private void inOderThreadBinaryTree(Node node) {
        if (node == null) {
            return;
        }
        // 处理左子树
        inOderThreadBinaryTree(node.left);
        // 如果左指针为空则将左指针指向前驱节点
        if (node.left == null) {
            node.left = pre;
            node.leftPointerType = POINTER_TYPE.THREAD;
        }
        // 如果前驱节点右指针为空,则将前驱节点右指针指向自己
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightPointerType = POINTER_TYPE.THREAD;
        }
        // 更新当前节点的前一个节点为自己
        pre = node;
        // 处理右子树
        inOderThreadBinaryTree(node.right);
    }

    /**
     * 遍历中序线索化二叉树(从前驱节点开始遍历)
     *
     * @param node
     */
    private void listInOderThreadBinaryTreeASC(Node node) {
        // 找到最前边一个节点
        while (node.left != null && node.leftPointerType != POINTER_TYPE.THREAD) {
            node = node.left;
        }
        System.out.print(node + " ");
        // 从前往后遍历
        while (node.right != null) {
            if (node.rightPointerType == POINTER_TYPE.THREAD) {
                node = node.right;
            } else {
                node = node.right;
                // 找到最前边一个节点
                while (node.left != null && node.leftPointerType != POINTER_TYPE.THREAD) {
                    node = node.left;
                }
            }
            System.out.print(node + " ");
        }
        System.out.println();
    }

    /**
     * 遍历中序线索化二叉树(从后继节点开始遍历)
     *
     * @param node
     */
    private void listInOderThreadBinaryTreeDESC(Node node) {
        // 找到最后边一个节点
        while (node.right != null && node.rightPointerType != POINTER_TYPE.THREAD) {
            node = node.right;
        }
        System.out.print(node + " ");
        // 从后往前遍历
        while (node.left != null) {
            if (node.leftPointerType == POINTER_TYPE.THREAD) {
                node = node.left;
            } else {
                node = node.left;
                // 找到最前边一个节点
                while (node.right != null && node.rightPointerType != POINTER_TYPE.THREAD) {
                    node = node.right;
                }
            }
            System.out.print(node + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 构建一个二叉树
        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        Node root = tree.createBinaryTreeByArray(arr, 0);
        // 线索化
        tree.inOderThreadBinaryTree(root);
        // 遍历(前驱)验证 8,4,9,2,10,5,1,6,3,7
        tree.listInOderThreadBinaryTreeASC(root);
        // 遍历(后继)验证 7,3,6,1,5,10,2,9,4,8
        tree.listInOderThreadBinaryTreeDESC(root);
    }
}

前序线索化及前驱遍历和后继遍历

后序线索化及前驱遍历和后继遍历

参考

线索二叉树原理及前序、中序线索化(Java实现)