首页 > 代码库 > 线索thread二叉树
线索thread二叉树
对于一个普通的二叉树
我们可以很明显的看到，在一个二叉树中，会有许多的空结点，而这些空结点必然会造成空间的浪费，为了解决这个问题，我们可以引入线索二叉树，把这些空结点利用起来，利用 ‘^’ 记录给定结点的前驱后继，那么问题就来了，该如何建立呢？
前面我们说过四种的遍厉方法，我应该用哪种方法来建立线索二叉树呢？
经过逐一的分析，我们发现利用中序遍历方法能够有效地建立起线索二叉树
我们先看一看在上述二叉树中中序遍历的结果
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二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。