ErQi

线索二叉树

发表于 | 分类于

线索二叉树

线索二叉树

在二叉树中有很多空指针没有利用上,例如有n个结点,那么指针数量就是2n,而n个结点的二叉树有n-1条分支线,也就是除了n-1的指针被利用到了,剩下的2n - (n - 1) = n + 1指针都是空指针,这是很大的一种浪费.针对不同遍历方式就可以将这些空指针利用上.

线索二叉树原理

在不用的遍历方式下,若结点左子树为空,那么就将左子树指向上个结点,成为前驱,若右子树为空,那么将右子树指向下一个遍历的结点,称为后继.这样就将大量的空指针利用上了,但是却无法区分究竟是左子树还是前驱了.
这时候就通过添加标记值来进行标记了.

线索二叉树的构造

1
2
3
4
5
6
7
class BinThrNode {
    String data; // 数据
    BinThrNode lchild; // 左指针
    BinThrNode rchild; // 右指针
    boolean ltag; // 左标记
    boolean rtag; // 右标记
}

相对于常规的构造仅仅多了两个前驱后继的标记位而已.

二叉树线索化

线索二叉树核心是利用上空置的指针,原理很简单,若左子树为空就指向上一个结点,若右子树为空则指向下一个结点.
简单的从上面看,似乎需要同时记录三个结点,即前驱结点,当前结点,后继结点,实则不然只需要两个结点即可.一个是在遍历的当前结点(tree),一个全局保存的上一个结点(pre).
进行线索化时,当前结点(tree)左子树为空,指向上一个结点(pre),同时上个一个结点(pre)右子树为空,指向下一个结点(tree),将同一个结点的前驱和后继分成两次来赋值即可.

前序线索二叉树的遍历

首先将二叉树进行前序线索化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
BinThrNode pre; // 全局变量,标记上一个结点
BinThrNode preThreading(BinThrNode tree) {
    if (null == tree) {
        return null;
    }
    if (null == tree.lchild) { // 当前节点没有左子树,替换为前驱
        tree.ltag = true; // 修改标记
        tree.lchild = pre; // 替换前驱
    }
    if (null != pre && null == pre.rchild) { // 上一节点没有右子树
        pre.rtag = true; // 修改标记
        pre.rchild = tree; // 替换后继
    }
    pre = tree; // 更新指针
    if (!tree.ltag) { // 判断是否是左子树,避免进入死循环
        preThreading(tree.lchild);
    }
    if (!tree.rtag) {
        preThreading(tree.rchild);
    }
    return tree;
}

二叉树经过线索化之后遍历就不需要在进行递归了,因为已经形成了一个链表,直接循环即可遍历.
前序遍历概括:不停找左子树,左子树为空就是用右指针,不管是右子树还是后继,然后从头继续不停找左子树.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 前序遍历
public void preOrderTraverse_Thr(BinThrNode tree) {
    if (null == tree) {
        return;
    }
    while (null != tree) {
        System.err.print(tree.data);
        while (!tree.ltag) {
            tree = tree.lchild;
            System.err.print(tree.data);
        }
        tree = tree.rchild;
    }
}

中序线索二叉树的遍历

二叉树的中序线索化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
BinThrNode pre; // 全局变量,标记上一个结点
// 中序二叉树线索化
void inThreading(BinThrNode tree) {
    if (null == tree) {
        return;
    }
    inThreading(tree.lchild); // 递归找到左子树
    if (null == tree.lchild) { // 当前节点没有左子树,替换为前驱
        tree.ltag = true; // 修改标记
        tree.lchild = pre; // 替换前驱
    }
    if (null != pre && null == pre.rchild) { // 上一节点没有右子树
        pre.rtag = true; // 修改标记
        pre.rchild = tree; // 替换后继
    }
    pre = tree; // 更新指针
    inThreading(tree.rchild);
}

中序线索二叉树的遍历概括就是先找到左子树的最终结点,然后不停找后继,没有后继了就用右子树,然后从头再来,找这右子树的左子树最终结点,然后后继..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 中序遍历
public void inOrderTraverse_Thr(BinThrNode tree) {
    if (null == tree) {
        return;
    }
    while (null != tree.lchild && !tree.ltag) { // 先找到左子树的最终结点
        tree = tree.lchild;
    }
    while (null != tree) {
        System.err.print(tree.data);
        if (tree.rtag) { // 有后继直接指向后继
            tree = tree.rchild;
        } else {
            tree = tree.rchild; // 非后继就是右子树,顺着右子树往下找其左子树
            if (null != tree) { // 避免是右子树的最终结点,没有右子树
                while (!tree.ltag) { // 找到右子树下左子树的最终结点
                    tree = tree.lchild;
                }
            }
        }
    }
}

后序线索二叉树的遍历

二叉树的后序线索化之后生成的线索并不构成一个完整的链表,更像糖葫芦一样中间形成了一串串,以二叉树分支作为梗串联在一块….强行加入其它中立结点或其他进行遍历感觉本末倒置,所以略过..
二叉树的后序线索化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
BinThrNode pre; // 全局变量,标记上一个结点
// 后序二叉树线索化
void postThreading(BinThrNode tree) {
    if (null == tree) {
        return;
    }
    postThreading(tree.lchild);
    postThreading(tree.rchild);
    if (null == tree.lchild) { // 当前节点没有左子树,替换为前驱
        tree.ltag = true; // 修改标记
        tree.lchild = pre; // 替换前驱
    }
    if (null != pre && null == pre.rchild) { // 上一节点没有右子树
        pre.rtag = true; // 修改标记
        pre.rchild = tree; // 替换后继
    }
    pre = tree; // 更新指针
}

内容参考大话数据结构