为实习准备的数据结构（7）--线索二叉树

看，未来 · CSDN · · 2021-02-10 19:16

在这里插入图片描述

文章目录

前言

早就想办了这个线索二叉树，但是一直又没什么动力。这次就办了吧、

线索二叉树

在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

在这里插入图片描述

存储结构

上面那张图我也没看太明白，但是这块儿我看的明白：
线索二叉树中的线索能记录每个结点前驱和后继信息。为了区别线索指针和孩子指针，在每个结点中设置两个标志ltag和rtag。
当tag和rtag为0时，leftChild和rightChild分别是指向左孩子和右孩子的指针；否则，leftChild是指向结点前驱的线索(pre)，rightChild是指向结点的后继线索(suc)。由于标志只占用一个二进位，每个结点所需要的存储空间节省很多。

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

lchild	ltag	data	rtag	rchild

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

构建

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
加上线索的二叉树结构是一个双向链表结构，为了便于遍历线索二叉树，我们为其添加一个头结点，头结点左孩子指向原二叉树的根结点，右孩子指针指向中序遍历的最后一个结点。同时，将第一个结点左孩子指针指向头结点，最后一个结点的右孩子指针指向头结点。

中序遍历建立线索二叉树

//中序遍历进行中序线索化
void inThreading(ThrBiTree T, ThrBiTree &pre){  
    if(T){  
        inThreading(T->lchild, pre);//左子树线索化  
  
        if(!T->lchild){//当前结点的左孩子为空  
            T->lTag = Thread;  
            T->lchild = pre;  
        }else{  
            T->lTag = Link;  
        }  
  
        if(!pre->rchild){//前驱结点的右孩子为空  
            pre->rTag = Thread;  
            pre->rchild = T;  
        }else{  
            pre->rTag = Link;  
        }  
        pre = T;          
        inThreading(T->rchild, pre);//右子树线索化  
    }  
}

加上头结点，遍历线索二叉树：

//T指向头结点，头结点的lchild链域指针指向二叉树的根结点  
//中序遍历打印二叉线索树T（非递归算法）  
void inOrderTraversePrint(ThrBiTree T){  
    ThrBiNode *p = T->lchild;//p指向根结点  
      
    while(p != T){//空树或遍历结束时，p == T  
        while(p->lTag == Link){  
            p = p->lchild;  
        }  
        //此时p指向中序遍历序列的第一个结点（最左下的结点）  
  
        printf("%c ", p->data);//打印（访问）其左子树为空的结点  
  
        while(p->rTag == Thread && p->rchild != T){  
            p = p->rchild;  
            printf("%c ", p->data);//访问后继结点  
        }  
        //当p所指结点的rchild指向的是孩子结点而不是线索时，p的后继应该是其右子树的最左下的结点，即遍历其右子树时访问的第一个节点  
        p = p->rchild;  
    }  
    printf("\n");  
}

线索二叉树的用武之地

优势
(1)利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。
(2)任意一个结点都能直接找到它的前驱和后继结点。

不足
(1)结点的插入和删除麻烦，且速度也较慢。
(2)线索子树不能共用。

在这里插入图片描述

原文地址：访问原文地址
快照地址：访问文章快照

分享到微博