线索二叉树的实现

妖狐艹你老母 2022-06-08 00:23 167阅读 0赞

线索二叉树的作用是为了加快查找结点的前驱和后继的速度  
线索二叉树实现的是利用每个结点的空指针（如果有）指向左子树指针指向前一个结点（中序遍历顺序，下同）右子树指向后继结点，但是要添加两个方向指针

LTag, RTag，如果LTag = 0，则表示该节点有左孩子，等于1则表示指针为空指向可以指向前驱结点, RTag = 0，则表示该节点有右孩子，等于1则表示指针为空指向可以指向后继结点

![Center][]

![Center 1][]

#include <iostream>
    using namespace std;
    
    #define Elemtype char
    
    typedef enum PointerTag
    {
    	Link, Thread
    };
    
    typedef struct BiThrNode
    {
    	Elemtype data;
    	struct BiThrNode *lchild, *rchild;
    	PointerTag LTag, RTag;
    }BiThrNode,*BiThrTree;
    
    BiThrTree Pre = NULL;//全局变量始终指向刚刚经过的结点；
    
    void CreateTree(BiThrTree *T)//先序的方法创造二叉树
    {
    	char ch;
    	scanf_s("%c",&ch);
    
    	if (' ' == ch)
    	{
    		(*T) = NULL;
    	}
    	else
    	{
    		(*T) = new BiThrNode;
    		(*T)->data = ch;
    		(*T)->LTag = Link;
    		(*T)->RTag = Link;
    		CreateTree(&(*T)->lchild);
    		CreateTree(&(*T)->rchild);
    	}
    	
    }
    
    void InThreading(BiThrTree p)//中序遍历线索化
    {
    	if (p)
    	{
    		InThreading(p->lchild);//左子树线索化
    		
    		if (!p->lchild)//如果p的左子树为空即将LTag设置成1，将lchild指向刚刚访问的结点
    		{
    			p->LTag = Thread;
    			p->lchild = Pre;//左子树指向前驱
    		}
    		if (!Pre->rchild)//如果p的右子树为空即将LTag设置成1，表明下一个结点是他的后继
    		{
    			Pre->RTag = Thread;
    			Pre->rchild = p;//右子树指向后继
    		}
    		Pre = p;//保持pre指向p的前驱
    
    		InThreading(p->rchild);//线索化右子树
    	}
    
    }
    
    void InOrderThreading(BiThrTree *Thrt, BiThrTree T)
    {
    	*Thrt = new BiThrNode;//设置一个头结点
    	(*Thrt)->LTag = Link;//头结点的左标志设置成Link证明他有左子树
    	(*Thrt)->RTag = Thread;//头结点的右标志设置成thread证明他有后继结点
    	(*Thrt)->rchild = *Thrt;//开始先让他的右子树指向自己
    
    	if (!T)//若果二叉树是空树就让头结点的左子树指向头结点
    	{
    		(*Thrt)->lchild = *Thrt;
    	}
    	else
    	{
    		(*Thrt)->lchild = T;//如果树不为空，头结点的左子树指向树的根
    		Pre = *Thrt;//pre指向头结点
    		InThreading(T);//开始中序线索化二叉树
    		Pre->rchild = *Thrt;//收尾工作，让二叉树中序遍历的最后一个结点的右子树指向头结点
    		Pre->RTag = Thread;//
    		(*Thrt)->rchild = Pre;//让头结点的右子树指向前一个结点也就是二叉树中序遍历的最后一个结点
    	}
    
    }
    
    void InOrderTraverse(BiThrTree Thrt)//中序遍历线索化二叉树，非递归
    {
    	BiThrTree p;
    	p = Thrt->lchild;//让p 指向树的根结点
    
    	
    	while (p != Thrt)//如果P不等于头结点说明二叉树非空，或者p还没有指向头结点
    	{
    		while (p->LTag == Link)//如果p->LTag == Link说明p一直有右子树，这个操作是为了找出最左边的结点
    		{
    			p = p->lchild;
    		}
    
    		cout << p->data << " ";//输出结点
    
    		while (p->RTag == Thread && p->rchild != Thrt)//p->RTag == Thread && p->rchild != Thrt如果p有后继结点，并且p的右子树还没有指向头结点，就一直按照线索遍历
    		{
    			p = p->rchild;
    			cout << p->data << " ";
    		}
    
    		p = p->rchild;//收尾工作将P再次指向头结点
    	}
    }
    
    int main()
    {
    	char ch;
    	BiThrTree T, Thrt;
    	CreateTree(&T);
    	InOrderThreading(&Thrt, T);
    	InOrderTraverse(Thrt);
    	system("pause");
    	return 0;
    }

演示结果：

![Center 2][]

[Center]: /images/20220608/0eeaadaad04a4bc7a27a01c81590d35e.png
[Center 1]: /images/20220608/b9cb7bb084104251a888c91d32d076b5.png
[Center 2]: /images/20220608/bde70b25804e48498763ed24c2b719b2.png