Skip to content

Latest commit

 

History

History
664 lines (572 loc) · 22.7 KB

12 二叉树线索化.md

File metadata and controls

664 lines (572 loc) · 22.7 KB

#数据结构 #C

[48] 线索二叉树的概念

1.二叉树遍历导致数据关系“线性化”

对二叉树进行遍历，原本的非线性关系，经过遍历之后，得到了线性关系。
例如，如下的二叉树经过中序遍历后，形成了DBEAFCG的线性关系。

需要明确的是，二叉树作为一种数据结构，其本身的一个结点，对应唯一前驱和多个后继。基于遍历序列线性化处理，每个结点只有唯一一个前驱和后继。

【问题】
能否从二叉树的某个指定结点（非根结点）开始，开始遍历序列？例如二叉树如图，给出指向结点G的指针ptr，能否对整个二叉树进行中序遍历？

【回答】
答案很显然是不可以的。因为二叉树的结点的指向是单向，结点的指向是指向它的孩子，而并非指向双亲。对于树的遍历，只能从根结点开始。

2.如何对指定结点求二叉树遍历序列

【问题】

  1. 如何找到指定结点p 在中序遍历序列中的前驱 predecessor？
  2. 如何找到 p 的中序后继successor？

【思路】
从根结点出发，重新进行一次中序遍历，指针 tmp 记录当前访问的结点，指针 pre 记录上一个被访问的结点。

  1. 当tmp == p时，pre为前驱；
  2. 当pre == p时，tmp为后继。

【程序实现】

  1. 从根结点开始中序遍历；
  2. 对每一个结点进行匹配判定；
  3. 当匹配通过的时候，将使用finalNode 保存当前的结点，当匹配不通过的时候，使用pre结点保存tmp结点，因为当前的结点保存后，传入下个结点的匹配，就是下一个结点的pre结点。
  4. 判断finalNode是否为初始值，如果是初始值，则前驱不存在，否则，则为要寻找的那个前驱。

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

BiTree pre = NULL;          // 记录每一轮的当前指针
BiTree finalNode = NULL;    // 记录最后找的结果

// 这里使用全局变量的方法，也可以使用的是二阶指针，会比较难懂
bool CheckMatching(BiTree tmp, int target)
{
    if (tmp->data == target) {
        finalNode = pre;
        return true;
    } else {
        pre = tmp;
        return false;
    }
}

/*  中序遍历：
    每个轮次的操作，都需要将当前结点的数据域与target作对比，检查是否匹配。
    而pre，记录是这次匹配结点的上一个结点 -- 即前驱。
    而上一个结点的匹配是在上一轮进行的，即调用本次函数的位置确定的，
    那么， 就需要将每一次匹配的结点，传到函数里面进行修改，
    因为本轮进行匹配的结点，就是下一轮的pre结点，
    在下一轮匹配完成后，又会再次使用下一个结点，更新pre结点。
    由于每次更新都会使得pre变化，因此，需要第三个变量 final来保存下最终的要求结点
*/
void InOrderTraversal(BiTree tmp, int target)
{
    if (tmp == NULL) {
        return;
    }

    InOrderTraversal(tmp->lchild, target);
    // printf("Node data = [%d], target = [%d] \n", tmp->data, target);
    if (CheckMatching(tmp, target) == true) {
        // printf("--- Matching!!! ---\n", target);
        return;
    }
    InOrderTraversal(tmp->rchild, target);
    return;
}

// 返回前驱是否存在和前驱的值
bool GetPredecessor(BiTree root, int *predecessor)
{
    if (root == NULL || predecessor == NULL) {
        return false;
    }

    int target = *predecessor;          // 结点数据target

    InOrderTraversal(root, target);
    if (finalNode == NULL) {            // 前驱并不存在
        return false;
    }

    *predecessor = finalNode->data;
    return true;
}

寻找后继的方法与以上相同，也可以使用参数传参，不同的检查匹配的判定条件需要改变： 即：如果当target和前驱的值匹配，那么当前的tmp即是要找的后继。

bool CheckMatching(BiTree tmp, int target)
{
    // 必须首先检查pre是否为空，排除首次匹配直接读取空指针
    // 只有在第一次匹配完成后，才知道后继是谁
    if (pre == NULL || pre->data != target) 
    {
        pre = tmp;
        return false;
    }
    // 与上一个结点匹配，那么当前结点就是要找的后继
    else
    {
        finalNode = tmp;
    /* 这里，一定要补上，清空pre结点
       否则，pre保存了之前的数据，下一个结点在匹配的时候，判断是true，
       就会更新改写finalNode，导致寻找后继结点失效 */
        pre = NULL;    
        return true;
    }
}

该方法具有明显的缺点：找前驱、后继很不方便，操作必须从根开始，从头开始遍历，也就是时间复杂度为 $O(N)$。

3.线索二叉树

假如，将遍历序列以线性表的形式存储起来，那么，对于任一个给定的元素，都可以找到该数据结构的其他要素（查询线性表）。
对原普通二叉树观察发现，存储空间内存在很多空链域，这些空链域可以用来指向他们的前驱和后继。可以利用叶子结点的空链域，分别指向他们的前驱和后继。这个过程叫做二叉树的线索化（Threading）。

这个时候，对原二叉树进行改造的产物叫做线索二叉树（Threaded BinaryTree），又叫引线二元树、引线二叉树。
改造后的二叉树，对于某个结点而言，找到其前驱和后继只需要通过前驱线索和后继线索即可。

4.线索二叉树的存储结构

线索二叉树是添加了直接指向结点的前驱和后继的指针的二叉树。

// 二叉树的结点（链式存储）
typedef struct BiTNode {
    ElemType data;
    BiNode *lchild, *rchild;
} BiTNode, *BiTree;

// 线索二叉树的结点
typedef struct ThreadNode {
    ElemType data;
    ThreadNode *lchild, *rchild;
    int ltag, rtag;        // 左、右线索标志
} ThreadNode, *ThreadTree;

当tag == 0，表示指针指向孩子；当tag == 1，表示指针指向线索。
二叉树可以叫做二叉链表，线索二叉树可以叫做线索链表。
上图中的原二叉树，可以直接转化成以下的形式：

同理，中序遍历二叉树序列的线索化，可以推广到先序线索二叉树、后序线索二叉树。

  • 中序线索二叉树 —— 线索指向中序前驱、中序后继；
  • 先序线索二叉树 —— 线索指向先序前驱、先序后继；
  • 后序线索二叉树 —— 线索指向后序前驱、后序后继。

[49] 二叉树的线索化

1.中序线索化

对比对普通二叉树进行某一个结点求其前驱、后继的过程，必须从根结点开始，遍历整个二叉树寻找，时间复杂度为 $O(N)$ 。但是如果使用线索二叉树，如果有结点指向前驱或者后继的话，直接可以得到，时间复杂度转化成为 $O(1)$ 。

那么如果要要得到一个线索二叉树的话，首先需要对原二叉树进行线索化。 【算法思路】：

  1. 中序遍历二叉树每一个结点，遍历visit该结点时，对该结点添加线索；
  2. 左子树为空，左孩子结点添加前驱；
  3. 右子树为空，右孩子结点增加后继。

以中序遍历为例，程序实现：

ThreadNode *pre = NULL;     // 全局变量，指向当前访问结点的前驱

typedef struct ThreadNode {
    ElemType data;
    ThreadNode *lchild, *rchild;
    int ltag, rtag;        // 左、右线索标志
} ThreadNode, *ThreadTree;

// 中序遍历二叉树，一边遍历一边线索化
void InOrderThread(ThreadTree T) 
{
    if (T != NULL) {
        InTread(T->lchild);        // 中序遍历左子树
        visit(T);                  // 访问根结点
        InTread(T->rchild);        // 中序遍历右子树
    }
}

// 线索化 Threading
void visit(ThreadNode *tmp) 
{
    // 左子树是空
    if (tmp->lchild == NULL) {
        tmp->lchild = pre;
        tmp->ltag = 1;          // tag == 1，表示指针指向线索。
    }

    // 前驱不为空，且前驱的右孩子为空，例如二叉树的 B 结点
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = tmp;      // 建立前驱结点的后继线索
        pre->rtag = 1;          // tag == 1，表示指针指向线索。
    }
    // 把pre指状指向下一个结点，依次遍历
    pre = tmp;
}

中序线索化的过程，上层调用InOrderThread函数： 注意在调用该中序遍历的函数的时候，最后要继续检查pre的rchild是否是NULL，如果是的话，令rtag = 1。

// 中序线索化二叉树
void CreateInOrderThread(ThreadNode root) 
{
    pre = NULL;                 // pre初始化为NULL
    if (root != NULL) {         // 非空二叉树才能线索化
        InOrderThread(root);    // 中序线索化二叉树
        if (pre->rchild == NULL) {
            pre->rtag = 1;      // 处理遍历的最后一个结点
        }
    }
}

// 调用函数： CreateInOrderThread --> InOrderThread --> visit

总结而言，中序线索化其实就是对树的中序遍历，只不过在visit当中，添加了线索化过程。
【问题】
为什么对于最后一个右孩子的结点前驱进行特殊处理？
【解释】
visit最后一个结点的时候，无法对其后继进行处理，但是本应当对其置空。

线索化完成后，存储结构如下图：

也可以使用将visit操作直接实现写到递归函数内部：

// 中序线索化，这里的pre是一个引用类型
void InOrderThread(ThreadTree p, ThreadTree &pre)
{
    if (p != NULL) {    
        InOrderThread(p->lchild, pre);  // 递归，线索化左子树
        // 处理根结点
        if (p->lchild == NULL) {        // 左子树为空，建立前驱线索
            p->lchild = pre;        
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            // 右子树为空，建立前驱结点的后继线索
            pre->rchild = p;        
            pre->rtag = 1;
        }
        InOrderThread(p->rchild, pre);  // 递归，线索化右子树
    }
}

// 中序线索化二叉树
void CreateInOrderThread(ThreadNode root) 
{
    ThreadTree pre = NULL;      // pre初始化为NULL
    if (root != NULL) {         // 非空二叉树才能线索化
        InOrderThread(root, pre);  // 中序线索化二叉树
        pre->rchild == NULL;
        pre->rtag = 1;      // 处理遍历的最后一个结点
    }
}

【思考】
为什么处理遍历最后一个结点时，不需要判断rchild是否为NULL，直接读其右孩子直接置空？
【解释】
因为中序遍历的最后一个结点右孩子指针必为空。

2.先序线索化

先序线索化与中序线索化相似，唯一一点注意，遍历时对ltag 一定要作判定。 #未完待续

// 全局变量pre, 指向当前访问结点的前驱
ThreadNode *pre = NULL;

// 先序遍历二叉树，一边遍历一边线索化
void PreOrderThread(ThreadTree T)
{
    if (T != NULL) {
        visit(T);            // 先处理根结点
        if (T-> ltag == 0)   // lchild 不是前驱线索
        {
            PreOrderThread(T->lchild);
        }
        PreOrderThread(T->rchild);
    }
}

// 线索化
void visit(ThreadNode *q) 
{
    // 左子树是空，建立前驱线索
    if (q->lchild == NULL) {
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = q;    // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    // 把pre指状指向下一个结点，依次遍历
    pre = q;
}

// 先序线索化二叉树
void CreatePreOrderThread(ThreadNode T) 
{
    pre = NULL;             // pre初始化为NULL
    if (T != NULL) {        // 非空二叉树才能线索化
        PreOrderThread(T);        // 中序线索化二叉树
        if (pre->rchild == NULL){
            pre->rtag = 1;    // 处理遍历的最后一个结点
        }
    }
}

在先序二叉树线索化过程中，如果不采取if (T-> ltag == 0)判定的话，对其指向结点访问，有可能访问前驱结点，造成死循环问题。

3.后序线索化

后序线索化，与前两者类似。

// 全局变量pre, 指向当前访问结点的前驱
ThreadNode *pre = NULL;

// 后序遍历二叉树，一边遍历一边线索化
void PostOrderThread(ThreadTree T) 
{
    if (T != NULL) {
        PostOrderThread(T->lchild);         // 后序遍历左子树
        PostOrderThread(T->rchild);         // 后序遍历右子树
        visit(T);                           // 访问根结点
    }
}

// 线索化
void visit(ThreadNode *q) 
{
    // 左子树是空，建立前驱线索
    if (q->lchild == NULL) {
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = q;    // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    // 把pre指状指向下一个结点，依次遍历
    pre = q;
}

// 后序线索化二叉树T
void CreatePostOrderThread(ThreadNode T) 
{
    pre = NULL;                // pre初始化为NULL
    if (T != NULL) {        // 非空二叉树才能线索化
        PostOrderThread(T);        // 中序线索化二叉树
        if (pre->rchild == NULL){
            pre->rtag = 1;    // 处理遍历的最后一个结点
        }
    }
}

后序线索化并不会出现类似先序线索化的“死循环”问题。

[50] 在线索二叉树中找前驱后继

二叉树的线索化，最终目的时为了找到遍历序列的前驱和后继。在完成二叉树线索化的前提下，以下讲着重探讨在不同类型的线索二叉树下，怎么找前驱和后继。

1.中序线索二叉树找中序后继

【问题】
中序线索二叉树，如何找到指定结点 *p 的中序后继 next？

【解答】

  1. 若 p->rtag == 1，则next = p->rchild;
    • 因为中序遍历：左-->根--> 右，
    • 如果rtag值表示1，即表示该叶子结点有后继线索，直接赋值即可;
  2. 若 p->rtag == 0，表示这个结点一定是有右孩子的，那么后继next 指向 p的右子树中最左下的结点。

#未完待续

代码实现：

typedef struct ThreadNode {
    ElemType data;
    ThreadNode *lchild, *rchild;
    int ltag, rtag;        // 左、右线索标志
} ThreadNode, *ThreadTree;

// 函数调用：InOrder --> NextNode --> FirstNode
// 对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
void InOrder(ThreadNode *T)
{
    for(ThreadNode *p = FirstNode(T); p != NULL; 
        p = NextNode(p)){
        visit(p);
    }
}

// 中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p)
{
    // 右子树中最左下结点
    if (p->rtag == 0){
        return FirstNode(p->rchild);
    } else {
        // rtag == 1 直接返回后继线索。
        return p->rchild;
    }
}

// 找到以P为根的子树，第一个被中序遍历的结点
ThreadNode *FirstNode(ThreadNode *p)
{
    // 循环找到最左下结点(不一定是叶结点)
    while (p->ltag == 0){
        p = p->lchild;
    }
    return p;
}

2.中序线索二叉树找中序前驱

【问题】 中序线索二叉树，如何找到指定结点 *p 的中序前驱 pre？

【解答】

  1. 若 p->ltag == 1，则pre = p->lchild;
    • 中序遍历：左-->根--> 右，
    • 如果ltag值表示1，即表示该叶子结点有前驱线索，直接赋值即可;
  2. 若 p->ltag == 0，表示这个结点一定是有左孩子的，前驱pre 指向 p 的左子树中最右下的结点。

代码实现：

// 对中序线索二叉树进行逆向中序遍历(利用线索实现的非递归算法)
void ReverseInOrder(ThreadNode *T)
{
    for(ThreadNode *p = LastNode(T); p != NULL; 
        p = PreNode(p)){
        visit(p);
    }
}

// 中序线索二叉树中找到结点p的前驱结点
ThreadNode *PreNode(ThreadNode *p)
{
    // 左子树中最右下结点
    if (p->ltag == 0){
        return LastNode(p->lchild);
    } else {
        // ltag == 1 直接返回后继线索。
        return p->lchild;
    }
}

// 找到以P为根的子树，最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p)
{
    // 循环找到最右下结点(不一定是叶结点)
    while (p->rtag == 0){
        p = p->rchild;
    }
    return p;
}

3.先序线索二叉树找先序后继

【问题】 先序线索二叉树（根结点--> 左孩子 --> 右孩子），如何找到指定结点 *p 的先序后继 next？

【解答】

  1. 若 p->rtag == 1，同理，则next = p->rchild;
  2. 若 p->rtag == 0，表示这个结点一定是有右孩子的，这个时候，需要对这个结点的左孩子情况进行讨论。
    • 如果有左孩子，那么先序后继为左孩子；
    • 如果有没有左孩子，那么先序后继为右孩子。

算法实现：

// 找先序线索二叉树p的后继
ThreadNode *FindPreOrderNext(ThreadNode *p){
    if (p->rtag == 1){
        return p->rchild;
    } else if (p->ltag == 0){
        return p->lchild;
    } else {
        return p->rchild;
    }
}

4.先序线索二叉树找先序前驱

【问题】 先序线索二叉树（根结点--> 左孩子 --> 右孩子），如何找到指定结点 *p 的先序前驱 pre？

【解答】 在先序遍历中，某一个结点的左右子树只可能是它的后继，均不可能是它的前驱，所以，如果要求其前驱，有两种方法：

  1. 可以使用最原始的方式从根结点依次遍历，但是浪费时间，时间复杂度 $O(N)$ 。
  2. 采取三叉链表的数据结构，分配一个指针，用于指向该结点的父结点。
typedef struct BiTNode {
    ElemType data;                
    struct BiTNode *lchild, *rchild;    // 左、右孩子指针
    struct BiTNode *parent;             // 父结点指针
} BiTNode, *BiTree;                     // 三叉链表，方便找父结点

如果采取后者，就需要对具体情况进行分类逐个讨论了：

  • 情形1:
    如果能找到p的父结点，且p是左孩子。父结点是前驱。
if (p->parent != NULL && p = p->parent->lchild) {
    pre = p->parent;
}
  • 情形2：
    如果能找到p的父结点，且p是右孩子，其左兄弟为空。父结点是前驱。
if (p->parent != NULL && p = p->parent->rchild && p->parent->lchild == NULL) {
    pre = p->parent;
}
  • 情形3：
    如果能找到p的父结点，且p是右孩子且左孩子不为空。左兄弟子树最后一个被先序遍历的结点是前驱。
BiTNode* pre == NULL;
// visit 操作函数写入pre
void visit(BiNode *T)
{
    pre = T;
    return;
}

if (p->parent != NULL && p = p->parent->rchild && p->parent->lchild != NULL) {
    // 先序遍历，并将变量存储在pre中
    PreOrder(p->parent->lchild);
    return pre;
}
  • 情形4：
    没有父结点。没有前驱。
if (p->parent == NULL) {
    pre = NULL;
}

5.后序线索二叉树找后序前驱

【问题】
后序线索二叉树（左孩子 --> 右孩子-->根结点 ），如何找到指定结点 *p 的后序前驱 pre？

【解答】

  1. 若 p->ltag == 1，则pre = p->lchild（同理）;
  2. 若 p->ltag == 0，表示这个结点一定是有左孩子的。这个时候，需要对这个结点的左孩子情况进行讨论。
    • 如果有右孩子，那么后序前驱为右孩子；
    • 如果没有右孩子，那么后序前驱为左孩子；

// 找后序线索二叉树p的前驱
ThreadNode *FindPostOrderPre(ThreadNode *p){
    if (p->rtag == 1){
        return p->lchild;
    } else if (p->rtag == 0){
        return p->rchild;
    } else {
        return p->lchild;
    }
}

6.后序线索二叉树找后序后继

【问题】
后序线索二叉树（左孩子 --> 右孩子-->根结点 ），如何找到指定结点 *p 的后序后继 next？

【解答】
后序遍历中，某一个结点的左右子树只可能是它的前驱，均不可能是它的后继，所以，如果要求其后继，有两种方法：

  1. 使用最原始的方式从根结点依次遍历，时间复杂度 $O(N)$。
  2. 或者采取三叉链表的数据结构，分配一个指针，用于指向该结点的父结点。
typedef struct BiTNode {
    ElemType data;                
    struct BiTNode *lchild, *rchild;    // 左、右孩子指针
    struct BiTNode *parent;             // 父结点指针
} BiTNode, *BiTree;                     // 三叉链表，方便找父结点

如果采取后者，同样需要对具体情况进行分类逐个讨论了：

  • 情形1：
    如果能找到p的父结点，且p是右孩子。父结点是后继。
if (p->parent != NULL && p = p->parent->rchild) {
    next = p->parent;
}
  • 情形2：
    如果能找到p的父结点，且p是左孩子，其右兄弟为空。父结点是后继。
if (p->parent != NULL && p = p->parent->lchild && p->parent->rchild == NULL) {
    next = p->parent;
}
  • 情形3：
    如果能找到p的父结点，且p是左孩子且右孩子不为空。右兄弟子树第一个被后序遍历的结点是后继。
BiTNode* next == NULL;
// visit 操作函数条件判定, next == NULL，写入NULL，否则不要写入
void visit(BiNode *T)
{
    if (next == NULL) {
        next = T;
    } 
    return;
}

if (p->parent != NULL && p = p->parent->lchild && p->parent->rchild != NULL) {
    // 后序遍历，并将变量存储在next中
    PostOrder(p->parent->rchild);
    return next;
}
  • 情形4：
    没有父结点。没有后继。
if (p->parent == NULL) {
    next = NULL;
}