首页 > 代码库 > 线索thread二叉树

线索thread二叉树

2024-08-21 00:46:19   220人阅读

对于一个普通的二叉树

技术分享

我们可以很明显的看到，在一个二叉树中，会有许多的空结点，而这些空结点必然会造成空间的浪费，为了解决这个问题，我们可以引入线索二叉树，把这些空结点利用起来，利用 ‘^’ 记录给定结点的前驱后继，那么问题就来了，该如何建立呢？

 

前面我们说过四种的遍厉方法，我应该用哪种方法来建立线索二叉树呢？

经过逐一的分析，我们发现利用中序遍历方法能够有效地建立起线索二叉树

我们先看一看在上述二叉树中中序遍历的结果

H D I B E A F C G

红色的结点为有空结点

技术分享

在空结点中储存前驱与后继

 

单面对这样的一种二叉树时又怎么办呢？

技术分享

中序遍历为

 F D G B A C E

我们可以看到在b结点与结点 c出只有一个空结点

那机器该如何判断放的是线索还是指针呢？

 

为了解决这种问题，我们可以吧树的每个结点进行扩容

技术分享

ltag : 为0时，表示lchild指向改结点的左孩子； 为1时，表示lchild指向该结点的前驱

rtag：为0时，表示rchild指向该结点的右孩子；为1时，表示rchild指向该结点的后继

 

线索二叉树的代码实现：

#include<iostream>
using namespace std;

typedef char ElemType;

//线索存储标志位
//Link 为0时，表示指向左右孩子的指针
//Thread  为1时，表示指向前驱后继的线索
typedef enum{Link, Thread} PointerTag;

typedef struct BitThrNode
{
	char data;
	struct BitThrNode *lchild, *rchild;
	PointerTag ltag;
	PointerTag rtag;
}BitThrNode, *BitThrTree;

//全局变量，指向刚刚访问过的节点
BitThrTree pre;

//利用前序遍历创建二叉树
void createBitThrTree(BitThrTree *T) //根节点的地址
{
	char c;
	cin >> c;
	if(c ==‘-‘)
	{
		*T=NULL;
	}
	else
	{
		*T=new BitThrNode;
	    (*T)->data=http://www.mamicode.com/c;"中序遍历输出结果为"<<endl;
	InorderTravel(p);
	
        return 0;
}

　　

线索thread二叉树


联系
我们