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