必威体育Betway必威体育官网
当前位置:首页 > IT技术

线索二叉树浅析

时间:2019-09-11 09:11:04来源:IT技术作者:seo实验室小编阅读:65次「手机版」
 

线索二叉树

1、线索二叉树原理

   n个结点的二叉链表中含有n+1(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")。

例如:

二叉树T有10个结点,其中有11个空指针域(空指针域用"^"表示),这样会造成一定的浪费。

建立线索二叉树的规则:

(1)如果ptr->lchild为空,则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱;

(2)如果ptr->rchild为空,则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继;

显然,在决定lchild是指向左孩子还是前驱,rchild是指向右孩子还是后继,需要一个区分标志的。因此,我们在每个结点再增设两个标志域ltag和rtag,注意ltag和rtag只是区分0或1数字的布尔型变量,其占用内存空间要小于像lchild和rchild的指针变量。

结点结构如下图所示:

其中:

(1)ltag为0时指向该结点的左孩子,为1时指向该结点的前驱;

(2)rtag为0时指向该结点的右孩子,为1时指向该结点的后继;

2、实现的详细代码如下:

#include<iOStream>
#include<stdlib.h> 
using namespace std;

typedef char ElemType;
//线索存储标志位
//Link(0) 表示指向左右孩子的指针
typedef enum { Link, Thread } PointerTag;

//线索二叉树结构定义
typedef struct BiThrNode
{
	ElemType data;
	struct BiThrNode *lchild, *rchild;
	PointerTag ltag;
	PointerTag rtag;
}BiThrNode, *BiThrTree;


//全局变量,始终指向刚刚访问过的节点
BiThrTree pre;
//创建一颗二叉树 ,约定用户遵照前序遍历的方式输入数据
void CreatBiThrTree(BiThrTree* T)
{
	ElemType c;
	cin >> c;
	if ('#' == c) {
		*T = NULL;
	}
	else
	{
		*T = (BiThrNode *)malloc(sizeof(BiThrNode));
		(*T)->data = c;
		(*T)->ltag = Link;
		(*T)->rtag = Link;

		CreatBiThrTree(&(*T)->lchild);
		CreatBiThrTree(&(*T)->rchild);
	}
}

//进行线索化
void InThreading(BiThrTree T) {
	if (T)
	{
		InThreading(T->lchild);	//递归左孩子线索化

		//节点处理
		if (!T->lchild) {
			T->ltag = Thread;
			T->lchild = pre;
		}
		if (!pre->rchild) {
			pre->rtag = Thread;
			pre->rchild = T;
		}
		pre = T;
		InThreading(T->rchild);	//递归右孩子线索化
	}
}

//建立头结点,并对全局变量pre 进行初始化
void InorderThreading(BiThrTree* p, BiThrTree T) {
	*p = (BiThrNode *)malloc(sizeof(BiThrNode));
	(*p)->ltag = Link;
	(*p)->rtag = Thread;
	(*p)->rchild = *p;
	if (!T) {
		(*p)->lchild = *p;
	}
	else {
		(*p)->lchild = T;
		pre = *p;
		InThreading(T);
		pre->rchild = *p;
		pre->rtag = Thread;
		(*p)->rchild = pre;
	}

}
//中序遍历二叉树,非递归
//void visit(char c) {
//	cout << c;
//}

void InOrderTraverse(BiThrTree T) {
	BiThrTree p;
	p = T->lchild;
	while (p != T) {
		while (p->ltag == Link) {
			p = p->lchild;
		}
		cout << p->data;
	//	visit(p->data);
		while (p->rtag == Thread && p->rchild != T) {
			p = p->rchild;
			//visit(p->data);
			cout << p->data;
		}
		p = p->rchild;
	}
}

int main()
{
	BiThrTree P, T = NULL;
	CreatBiThrTree(&T);

	//	preOrder(T);	
	InOrderThreading(&P, T);

	cout << "中序遍历输出结果为:";
	InOrderTraverse(P);
	cout << endl;

	system("pause");
	return 0;
}

结果如下:

代码解析:

1)初始化阶段:

对应的代码:

*p = (BiThrNode *)malloc(sizeof(BiThrNode));
	(*p)->ltag = Link;
	(*p)->rtag = Thread;
	(*p)->rchild = *p;
	if (!T) {
		(*p)->lchild = *p;
	}
	else {
		(*p)->lchild = T;
		pre = *p;

此处建立了一个头结点p,并将ltag置为0,rtag置为1,rchild指针预先指向自身,全局变量pre指向头结点。

2)线索化构造

对应代码:

//进行线索化
void InThreading(BiThrTree T) {
	if (T)
	{
		InThreading(T->lchild);	//递归左孩子线索化

		//节点处理
		if (!T->lchild) {
			T->ltag = Thread;
			T->lchild = pre;
		}
		if (!pre->rchild) {
			pre->rtag = Thread;
			pre->rchild = T;
		}
		pre = T;
		InThreading(T->rchild);	//递归右孩子线索化
	}
}

上图显示了线索化的第一步,由代码可知,首先递归到H节点,检测到H->lchild为空,则ltag置为Thread,lchild指向pre,由于pre的rchild指针不为空,因此不进行操作。

第二步如下:

上图中,当前节点为D,pre指向了H节点,则节点H的rtag为1,并且rchild指向了节点D。

最终的线索化如下:

相关阅读

【数据结构】线索二叉树(构造与遍历)

主要内容 基本概念 构造线索二叉树 遍历线索二叉树   基本概念 遍历二叉树是对非线性结构结点的线性化过程,由此得到的遍历

线索二叉树

线索二叉树:(不经常用,就是把空指针利用起来) 顺便说一下遍历二叉树的方法(递归,用栈,线索二叉树,还有二叉排序树) 提出问题: 线索二叉树的

线索二叉树的理解

为什么要有线索二叉树? 为了解决无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题 但是同时出现了二叉链表找左、右孩子

分享到:

栏目导航

推荐阅读

热门阅读