14、数据结构与算法 - 二叉树(四)线索化二叉树

标签: 数据结构与算法

线索化二叉树


 一个二叉树,如果有n个结点,那么就有n-1个有效路径。如果是非常庞大的二叉树,就会有许多的空间浪费。
 如下图。有10个结点数据,有11个空指针域。
 
 
 如上图,如果我们想知道F 结点的前驱,或者是某个 结点的前驱是谁的时候,这个时候我们就需要变量很多个结点找到其对应关系,才能找到我们想要的对应结点的前驱。这个时候我们就可以利用这些空的指针域,去做一些有用的事情。这就是线索化二叉树产生的背景。
 不是所有结点都能进行线索化,能线索化的结点必须左子树或右子树至少有一个为空。
 规则:
 (1)、结点左子树为空,利用左孩子指针指向它的前驱结点;
 (2)、结点右子树为空,利用右孩子指针指向它的后继结点;
 (3)、注意:所有前驱和后继必须按照某一种遍历逻辑(例如:中序遍历)

 


 如果单存的只是修改前驱后继的指针指向,那么就会存在如下图所示问题。由于指针指向的只是一个地址,所以下图中,E结点左孩子指针,指向到到底是左子树还是前驱我们就不知道了,那么就需要用一个标记来标识。
 
 
 结点增加标记,如果指向前驱或者后继标记为1,指向左子树/右子树 标记为0。
 
 


 2、代码实现

#include <stdio.h>
#include "string.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 //存储空间初始分配量
typedef int Status; //Status 是函数的类型,其值是函数结果状态代码,如OK
typedef char CElemType;

CElemType Nil = '#';
int indexs = 1;
typedef char String[24]; //字符型以空格符为空
String str;
Status StrAssign(String T,char *chars)
{
    int i;
    if (strlen(chars) > MAXSIZE) {
        return ERROR;
    }else{
        T[0] = strlen(chars);
        for (i=1; i<=T[0]; i++) {
            T[i] = *(chars+i-1);
        }
        return OK;
    }
}

定义结点

//Link ==0 表示指向左右孩子指针
//Thread ==1 表示指向前驱或后继的线索
typedef enum{
    Link,Thread
} PointerTag;

typedef struct BiThrNode{
    CElemType data;//数据
    struct BiThrNode *lchild, *rchild;//左/右孩子指针
    
    //标记指向 是左/右 孩子还是 前驱/后继
    PointerTag LTag;
    PointerTag RTag;
}BiThrNode,*BiThrTree;
//1、打印
Status visit(CElemType e){
    printf("%c ",e);
    return OK;
}

//2、构造二叉树
//按照前序输入线索二叉树结点的值,构造二叉树T
Status CreateBiThrTree(BiThrTree *T){
    CElemType h;
    h = str[indexs++];
    
    if (h == Nil) {
        *T = NULL;
    }else{
        *T = (BiThrTree)malloc(sizeof(BiThrNode));
        if (!*T) {
            exit(OVERFLOW);
        }
//        生成根结点(前序)
        (*T)->data = h;
        
//        递归构造左子树
        CreateBiThrTree(&(*T)->lchild);
//        存在左孩子->将标记LTag 设置为Link
        if ((*T)->lchild) {
            (*T)->LTag = Link;
        }
//        递归构造右子树
        CreateBiThrTree(&(*T)->rchild);
//        存在右孩子->将标记RTag设置为Link
        if ((*T)->rchild) {
            (*T)->RTag = Link;
        }
    }
    return OK;
}

遍历二叉树

//3、中序遍历二叉树T,将其中序线索化,Thrt指向头结点
//全局变量,始终指向刚刚访问过的结点
BiThrTree pre;

//中序遍历进行中序线索化
void InThreading(BiThrTree p){
    if (p) {
        InThreading(p->lchild);//递归左子树线索化

        if (!p->lchild) {//无左孩子
            p->LTag = Thread;//前驱线索
            p->lchild = pre;//左孩子指针指向前驱
        }else{
            p->LTag = Link;
        }

        if (!pre->rchild) {//前驱没有右孩子
            pre->RTag = Thread;//后继线索
            pre->rchild = p;//前驱右孩子指针指向后继(当前结点p)
        }else{
            pre->RTag = Link;
        }
        
        pre = p;
        InThreading(p->rchild);
    }
}

 

//中序遍历二叉树T,并将其中序线索化,Thrt指向头结点
Status InOrderThreading(BiThrTree *Thrt, BiThrTree T){
    *Thrt = (BiThrTree)malloc(sizeof(BiThrNode));
    
    if (!*Thrt) {
        exit(OVERFLOW);
    }
    
//    建立头结点;
    (*Thrt)->LTag = Link;
    (*Thrt)->RTag = Thread;
//    右指针回指向
    (*Thrt)->rchild = (*Thrt);
    
//    若二叉树空,则左指针回指
    if (!T) {
        (*Thrt)->lchild = *Thrt;
    }else{
        (*Thrt)->lchild = T;
        pre = (*Thrt);
        
//        中序遍历进行中序线索化
        InThreading(T);
        
//        最后一个结点rchil 右孩子
        pre->rchild = *Thrt;
//        最后一个结点线索化
        pre->RTag = Thread;
        (*Thrt)->rchild = pre;
    }
    
    return OK;
}
//中序遍历二叉树T
Status InOrderTraverse_Thr(BiThrTree T){
    BiThrTree p;
    p=T->lchild;//p指向根结点
    while (p!=T) {
//        空树或遍历结束时,p ==T
        while (p->LTag == Link) {
            p = p->lchild;
        }
        
//        访问其左子树为空的结点
        if (!visit(p->data)) {
            return ERROR;
        }
        while (p->RTag == Thread && p->rchild !=T) {
            p=p->rchild;
            visit(p->data);//访问后续结点
        }
        p=p->rchild;
    }
    return OK;
}

 

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 线索化二叉树!\n");
    BiThrTree H,T;
    
    //StrAssign(str,"ABDH#K###E##CFI###G#J##");
    StrAssign(str,"ABDH##I##EJ###CF##G##");
    
    CreateBiThrTree(&T); /* 按前序产生二叉树 */
    InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
    InOrderTraverse_Thr(H);
    printf("\n\n");
    return 0;
}
Hello, 线索化二叉树!
H D I B J E A F C G 

 

版权声明:本文为shengdaVolleyball原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/shengdaVolleyball/article/details/106292216