数据结构—线索二叉树的原理以及Java实现案例 1 线索二叉

发表于

「这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战」。

本文介绍了线索二叉树的概念，以及线索二叉树的Java的实现。如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

1 线索二叉树的概述

如果对二叉树的概念不是很了解，可以先看这篇文章：二叉树的入门以及Java实现案例详解。二叉树的概念在此不做赘述。

对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个引用域，所以一共是2n个引用域。而n个结点的二叉树一共有n-1条分支线数，也就是说，其实是存在2n-(n-1)=n＋1个空引用域。这些空间不存储任何事物，白白的浪费着内存的资源。

如下图：

在这里插入图片描述

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的引用，这种方法增加了存储开销，不可取；二是利用二叉树的空链引用。

我们可以考虑利用那些空地址，存放指向结点在某种遍历次序下的前驱和后继结点的地址，空left存放前驱，空right存放后继。我们把这种指向前驱和后继的引用称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

对二叉树以某种遍历方式（如先序、中序、后序或层序）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。 根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

采用中序遍历线索化之后的数据结构如下：

在这里插入图片描述

可以看到，它充分利用了空引用域的空间（这等于节省了空间），又保证了创建时的一次遍历就可以终生受用前驱后继的信息（这意味着节省了时间）。所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

2 节点设计

线索二叉树中的线索能记录每个结点前驱和后继信息。为了区别线索引用和孩子引用，在每个结点中设置两个标志ltag和rtag。

当tag和rtag为0时，left和right分别是指向左孩子和右孩子的指针；否则，left是指向结点前驱的线索(pre)，right是指向结点的后继线索(suc)。由于标志只占用一个二进位，每个结点所需要的存储空间节省很多。

现将二叉树的结点结构重新定义如下：

left ltag data rtag right

其中：ltag=0 时left指向左儿子；ltag=1 时left指向前驱；rtag=0 时right指向右儿子；rtag=1 时right指向后继。

3 中序线索二叉树的构建

现提供中序线索二叉树的构建的完整Java代码，先序、后续线索二叉树的构建和中序的构建基本一致，都是在先、中、后序遍历的方法的基础上改进而来的，如果对关于二叉树的4种遍历方式不了解的，可以看这篇文章：二叉树的4种遍历方式详解以及Java代码的完整演示。

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
java复制代码public class ThreadedBinaryTree<E> {

    /**
     * 外部保存根节点的引用
     */
    private BinaryTreeNode<E> root;

    /**
     * 线索化的时候保存刚刚访问过的前驱节点
     */
    private BinaryTreeNode<E> pre;

    /**
     * 树节点的数量
     */
    private int size;


    /**
     * 内部节点对象
     *
     * @param <E> 数据类型
     */
    public static class BinaryTreeNode<E> {

        //数据域
        E data;
        //左子节点/前驱
        BinaryTreeNode<E> left;
        //右子节点/后继
        BinaryTreeNode<E> right;
        boolean ltag;   //false：指向左子节点、true：前驱线索
        boolean rtag;   //false：指向右子节点、true：后继线索


        public BinaryTreeNode(E data) {
            this.data = data;
        }

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


    /**
     * 空构造器
     */
    public ThreadedBinaryTree() {
    }

    /**
     * 构造器,初始化root节点
     *
     * @param root 根节点数据
     */
    public ThreadedBinaryTree(E root) {
        checkNullData(root);
        this.root = new BinaryTreeNode<>(root);
        size++;
    }

    /**
     * 添加子节点
     *
     * @param parent 父节点的引用
     * @param data   节点数据
     * @param left   是否是左子节点,true 是;false 否
     */
    public BinaryTreeNode<E> addChild(BinaryTreeNode<E> parent, E data, boolean left) {
        checkNullParent(parent);
        checkNullData(data);
        BinaryTreeNode<E> node = new BinaryTreeNode<>(data);
        if (left) {
            if (parent.left != null) {
                throw new IllegalStateException("该父节点已经存在左子节点,添加失败");
            }
            parent.left = node;
        } else {
            if (parent.right != null) {
                throw new IllegalStateException("该父节点已经存在右子节点,添加失败");
            }
            parent.right = node;
        }
        size++;
        return node;
    }

    /**
     * 是否是空树
     *
     * @return true 是 ;false 否
     */
    public boolean isEmpty() {
        return size == 0;
    }


    /**
     * 返回节点数
     *
     * @return 节点数
     */
    public int size() {
        return size;
    }

    /**
     * 获取根节点
     *
     * @return 根节点 ;或者null--表示空树
     */
    public BinaryTreeNode<E> getRoot() {
        return root;
    }

    /**
     * 获取左子节点
     *
     * @param parent 父节点引用
     * @return 左子节点或者null--表示没有左子节点
     */
    public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.left;
    }

    /**
     * 获取右子节点
     *
     * @param parent 父节点引用
     * @return 右子节点或者null--表示没有右子节点
     */
    public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.right;
    }


    /**
     * 数据判null
     *
     * @param data 添加的数据
     */
    private void checkNullData(E data) {
        if (data == null) {
            throw new NullPointerException("数据不允许为null");
        }
    }


    /**
     * 检查父节点是否为null
     *
     * @param parent 父节点引用
     */
    private void checkNullParent(BinaryTreeNode<E> parent) {
        if (parent == null) {
            throw new NoSuchElementException("父节点不能为null");
        }
    }


    /**
     * 将以root为根节点的二叉树线索化  中序法
     *
     * @return true 线索化成功 ;false 线索化失败
     */
    public boolean inThread() {
        if (isEmpty()) {
            return false;
        }
        inThread(getRoot());
        return true;
    }

    /**
     * 将以root为根节点的二叉树线索化  中序法
     *
     * @param root 节点,从根节点开始
     */
    private void inThread(BinaryTreeNode<E> root) {
        BinaryTreeNode<E> left = getLeft(root);
        if (left != null) {
            //如果左子节点不为null,则继续递归遍历该左子节点
            inThread(left);
        }

        /*相比于中序遍历，中间多了如下步骤*/
        else {
            //如果左子节点为null，因为其前驱结点刚刚访问过，将左子节点设置为线索
            //完成前驱结点的线索化
            root.ltag = true;
            root.left = pre;
        }
        //如果前驱没有右子节点，那就把当前节点当作 前驱结点的后继节点
        if (pre != null && null == pre.right) {
            pre.rtag = true;
            pre.right = root;
        }
        //每次将当前节点设置为pre，下一个节点就把该节点当成前驱结点
        pre = root;


        BinaryTreeNode<E> right = getRight(root);
        if (right != null) {
            //如果右子节点不为null,则继续递归遍历该右子节点
            inThread(right);
        }
    }


    /**
     * 中序遍历线索二叉树
     */
    public void inThreadList(BinaryTreeNode<E> root) {
        if (root == null) {
            return;
        }
        //查找中序遍历的起始节点
        while (root != null && !root.ltag) {
            root = root.left;
        }

        while (root != null) {
            System.out.print(root.data + ",");
            // 如果右子节点是线索
            if (root.rtag) {
                root = root.right;
            } else {
                //有右子节点，遍历右子节点
                root = root.right;
                //如果右子节点不为null，并且右子节点的左子结点存在
                while (root != null && !root.ltag) {
                    root = root.left;
                }
            }
        }

    }
}

3.1 测试

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
java复制代码public class ThreadTreeTest {
    /**
     * 构建二叉树,添加根节点r
     */
    ThreadedBinaryTree<String> integerThreadedBinaryTree = new ThreadedBinaryTree<>("r");

    /**
     * 构建二叉树
     */
    @Before
    public void buildTree() {
        /*构建二叉树*/
        ThreadedBinaryTree.BinaryTreeNode<String> r = integerThreadedBinaryTree.getRoot();
        //添加r根节点的左子结点a
        ThreadedBinaryTree.BinaryTreeNode<String> a = integerThreadedBinaryTree.addChild(r, "a", true);
        //添加r根节点的右子结点b
        ThreadedBinaryTree.BinaryTreeNode<String> b = integerThreadedBinaryTree.addChild(r, "b", false);
        //添加a节点的左子结点c
        ThreadedBinaryTree.BinaryTreeNode<String> c = integerThreadedBinaryTree.addChild(a, "c", true);
        //添加a节点的右子结点d
        ThreadedBinaryTree.BinaryTreeNode<String> d = integerThreadedBinaryTree.addChild(a, "d", false);
        //添加b节点的左子结点e
        ThreadedBinaryTree.BinaryTreeNode<String> e = integerThreadedBinaryTree.addChild(b, "e", true);
        //添加b节点的右子结点f
        ThreadedBinaryTree.BinaryTreeNode<String> f = integerThreadedBinaryTree.addChild(b, "f", false);
        //添加c节点的左子结点g
        ThreadedBinaryTree.BinaryTreeNode<String> g = integerThreadedBinaryTree.addChild(c, "g", true);
        //添加c节点的右子结点h
        ThreadedBinaryTree.BinaryTreeNode<String> h = integerThreadedBinaryTree.addChild(c, "h", false);
        //添加d节点的左子结点i
        ThreadedBinaryTree.BinaryTreeNode<String> i = integerThreadedBinaryTree.addChild(d, "i", true);
        //添加f节点的左子结点j
        ThreadedBinaryTree.BinaryTreeNode<String> j = integerThreadedBinaryTree.addChild(f, "j", true);
    }


    /**
     * 中序线索二叉树
     */
    @Test
    public void test2() {
        //线索化
        System.out.println(integerThreadedBinaryTree.inThread());
        //线索化之后进行遍历,效率更高
        integerThreadedBinaryTree.inThreadList(integerThreadedBinaryTree.getRoot());
        //g   c   h   a   i   d   r   e   b   j   f
    }
}

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%