线索二叉树的详细讲解

深夜福利（不对，应该是深夜讲堂），五一劳动节前一天晚上的劳动成果。这个失踪人口回来更新博客了，这次给各位观众姥爷带来的是“线索二叉树”的详细讲解。“二叉树”从名字的定义上来看就是一个类似于树结构的东西。刚刚解释的只是树的概念，那什么是“二叉”呢？二叉就是有两个分叉的意思。那“二叉树”就是一棵每个结点都有2个孩子结点的树。（由于深夜的关系，所以这次就不画图了）

然后说一下什么是“线索二叉树”，它是一种由普通二叉树改进过来的数据结构，是让空出来的结点加入索引功能的二叉树。这样的做法让空闲的空间得以利用（例如最下层的结点，它的孩子都是空指针。一个指针就占了4字节的空间，如果有大量的空指针，那将浪费了大量的空间），而且加快了遍历的速度，这是一种很好的做法。

下面直接上代码详细讲解，二叉树与详细二叉树的实现代码：

#include <iostream>

using namespace std;

enum Type{
    Link,    //链表模式
    Thread    //线索模式
};

struct Node{
    char Data;
    Node *LChild;
    Type LType;
    Node *RChild;
    Type RType;
};

void CreateTree(Node *&Tree);
void CreateThread(Node *&p, Node *&Tree);
void ThreadAction(Node *&Tree);
void VisitedTree(char Data);
void SelectTree(Node *Tree);
void SelectThreadTree(Node *Tree);

Node *Pre = nullptr;    //全局变量 临时存放前驱结点

int main(){
    Node *Tree = nullptr, *p = nullptr;
    
    //创建二叉树
    CreateTree(Tree);

    //一般二叉树
    SelectTree(Tree);    //遍历
    cout << endl;
    
    //线索二叉树
    CreateThread(p, Tree);    //线索化
    SelectThreadTree(p);    //遍历
    cout << endl;

    system("pause");
    return 0;
}

void CreateTree(Node *&Tree){    //前序递归创建二叉树
    char in;
    cin >> in;

    if(in != '*'){    //分隔符
        Tree = new Node;
        Tree->Data = in;    //设置数据
        Tree->LType = Link;    //默认为链表模式
        Tree->RType = Link;    //默认为链表模式
        CreateTree(Tree->LChild);    //创建左孩子
        CreateTree(Tree->RChild);    //创建右孩子

    }else{
        Tree = nullptr;    //创建空结点
    }
}

void CreateThread(Node *&p, Node *&Tree){
    p = new Node;    //初始化头指针
    p->LType = Link;
    p->RType = Thread;
    p->RChild = p;    //先让右孩子指向自己，因为要实现循环的效果

    if(!Tree){    //若为空树
        p->LChild = p;    //让左孩子指向自己
    }else{
        p->LChild = Tree;    //左孩子指向树
        Pre = p;    //将头结点保存到临时结点，作为根结点的前驱

        ThreadAction(Tree);    //处理二叉树的结点状态

        Pre->RChild = p;    //将头结点存放到临时结点的右孩子
        Pre->RType = Thread;    //然后将临时结点右孩子的状态设置为线索
        p->RChild = Pre;    //头结点的右孩子指向临时节点，让头结点和尾结点相连
    }
}

void ThreadAction(Node *&Tree){
    if(Tree){    //判断是否是空树
        ThreadAction(Tree->LChild);    //先处理左孩子

        if(!Tree->LChild){    //若左孩子为空
            Tree->LType = Thread;    //改为线索模式
            Tree->LChild = Pre;    //将左孩子指向临时结点获取前驱结点
        }
        if(!Pre->RChild){    //若右孩子为空
            Pre->RType = Thread;    //改为线索模式
            Pre->RChild = Tree;    //将右孩子指向树的根节点，让树循环
        }
        Pre = Tree;    //用临时结点保存当前结点

        ThreadAction(Tree->RChild);    //最后处理右孩子
    }
}

void VisitedTree(char Data){
    cout << Data;
}

void SelectThreadTree(Node *Tree){
    Node *p = Tree->LChild;    //指针指向树的左孩子

    while(p != Tree){    //指针与树的头结点不相同
        while(p->LType == Link){    //若左孩子为链表模式，则一层一层地循环进入
            p = p->LChild;
        }
        VisitedTree(p->Data);    //访问数据

        while(p->RType == Thread && p->RChild != Tree){    //右孩子为显示 且 右孩子不是树的头指针
            p = p->RChild;    //循环进入最深处的右孩子
            VisitedTree(p->Data);    //访问数据
        }

        p = p->RChild;    //处理完这层的左孩子就处理右孩子
    }
}

void SelectTree(Node *Tree){    //中序遍历二叉树
    if(Tree){
        SelectTree(Tree->LChild);
        VisitedTree(Tree->Data);
        SelectTree(Tree->RChild);
    }
}

标签：计算机, 程序, 设计, 常用, 算法, 线索, 二叉树, 详细, 讲解

该文章由 Shiqi 原创并发布在 被遗忘的曙光 技术博客

转载请标明来源：https://blog.fdawn.com/CPP/23.html