【数据结构与算法】-（10）线索化二叉树

发布日期: 2021-01-17

文章字数: 1.3k

阅读时长: 5 分

阅读次数:

【数据结构与算法】-（1）基础篇

【数据结构与算法】-（2）线性表基础

【数据结构与算法】-（3）循环链表（单向）

【数据结构与算法】-（4）双向链表和双向循环链表

【数据结构与算法】-（5）链表面试题解析

【数据结构与算法】-（6）栈

【数据结构与算法】-（7）队列

【数据结构与算法】-（8）栈之算法题

【数据结构与算法】-（8.1）字符串去重算法

【数据结构与算法】-（8.2）字符串搜索算法和RK&BP算法

【数据结构与算法】-（8.3）KMP算法

【数据结构与算法】-（9）二叉树与顺序表实现

文章字数: 约4k
阅读时长: 20 分钟

一、概念

1.1 线索化二叉树的定义

线索化二叉树(Threaded Binary Tree)是一种特殊的二叉树结构。在普通二叉树中,叶子节点的左右指针往往指向NULL,造成了存储空间的浪费。线索化二叉树的主要思想是利用这些空闲指针,存储该节点在某种遍历序列中的前驱和后继节点的信息,从而加快树的遍历速度。

1.2 线索化二叉树的特点

充分利用空指针域,节省存储空间
可以直接找到任一节点的前驱和后继,而不需要重新遍历
遍历算法变得简单,不再需要使用栈

1.3 线索化二叉树的分类

根据线索化的方式,可以将线索二叉树分为:

前序线索化二叉树
中序线索化二叉树
后序线索化二叉树

本文将主要讨论中序线索化二叉树。

二、线索化二叉树的存储结构

2.1 节点结构

线索化二叉树的节点结构需要在普通二叉树节点的基础上增加两个标志位:

typedef struct ThreadNode {
    ElemType data;              // 数据域
    struct ThreadNode *lchild, *rchild;  // 左右孩子指针
    int ltag, rtag;             // 左右线索标志
} ThreadNode, *ThreadTree;

其中:

ltag为0时指向该节点的左孩子,为1时指向该节点的前驱
rtag为0时指向该节点的右孩子,为1时指向该节点的后继

三、线索化二叉树的实现

3.1 中序线索化

中序线索化的过程实际上就是对二叉树进行中序遍历的过程。在遍历的同时,将空指针改为指向前驱或后继节点。

ThreadNode *pre = NULL;  // 全局变量,始终指向刚刚访问过的节点

void InThread(ThreadTree p) {
    if(p) {
        InThread(p->lchild);  // 递归线索化左子树
        
        if(!p->lchild) {  // 左子树为空,建立前驱线索
            p->ltag = 1;
            p->lchild = pre;
        }
        if(pre && !pre->rchild) {  // 建立前驱节点的后继线索
            pre->rtag = 1;
            pre->rchild = p;
        }
        pre = p;  // 保持pre指向p的前驱
        
        InThread(p->rchild);  // 递归线索化右子树
    }
}

void CreateInThread(ThreadTree T) {
    pre = NULL;
    if(T) {
        InThread(T);
        // 处理最后一个节点
        if(pre->rchild == NULL) {
            pre->rtag = 1;
        }
    }
}

3.2 中序线索二叉树的遍历

利用线索化的特性,我们可以实现非递归的中序遍历:

void InOrderTraverse_Thr(ThreadTree T) {
    ThreadNode *p = T;
    while(p) {
        // 找到中序遍历的起始节点
        while(p->ltag == 0) p = p->lchild;
        printf("%d ", p->data);  // 访问该节点
        // 如果右指针是线索,直接访问后继
        while(p->rtag == 1 && p->rchild) {
            p = p->rchild;
            printf("%d ", p->data);
        }
        // 否则转向右子树
        p = p->rchild;
    }
}

3.3 查找节点的前驱和后继

在线索二叉树中,查找某个节点的前驱和后继变得非常简单:

// 查找中序后继
ThreadNode* InOrderNext(ThreadNode *p) {
    if(p->rtag == 1) return p->rchild;  // 右指针为线索
    p = p->rchild;  // 转向右子树
    while(p->ltag == 0) p = p->lchild;  // 找到右子树的最左节点
    return p;
}

// 查找中序前驱
ThreadNode* InOrderPrev(ThreadNode *p) {
    if(p->ltag == 1) return p->lchild;  // 左指针为线索
    p = p->lchild;  // 转向左子树
    while(p->rtag == 0) p = p->rchild;  // 找到左子树的最右节点
    return p;
}