线索二叉树的详细讲解

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

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