线索二叉树的详细讲解

深夜福利(不对,应该是深夜讲堂),五一劳动节前一天晚上的劳动成果。这个失踪人口回来更新博客了,这次给各位观众姥爷带来的是“线索二叉树”的详细讲解。“二叉树”从名字的定义上来看就是一个类似于树结构的东西。刚刚解释的只是树的概念,那什么是“二叉”呢?二叉就是有两个分叉的意思。那“二叉树”就是一棵每个结点都有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 Qiu 原创并发布在 被遗忘的曙光 技术博客

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

已有 2 条评论

  1. Alberto

    This article was very well-written.

  2. Charleigh

    It is great for the kiddies. They get to watch a nice parade and then, if they hang about in town for long enough, they can roll some drunks.

添加新评论