线索二叉树
线索二叉树的定义 n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。
为了区分这个指针是指向前驱（或后继）还是指向孩子节点的，我们需要加上标志 lTag，rTag 来区分
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
因为线索二叉树保存了每个节点的前去后继信心，对于需要频繁查询树中节点的前驱，后继的情况，线索二叉树是个不错的选择
Code
[cpp]
#include<stdio.h>
#include<malloc.h>
typedef struct ThreadBiTreeNode
{
char data;
struct ThreadBiTreeNode *lChild;
struct ThreadBiTreeNode *rChild;
int lTag,rTag;
}BiTNode,*BiTree;
void CreateBTree(BiTree &biTree){
char data;
data = getchar();
if(data=='0'){
biTree = NULL;
}
else {
biTree = (BiTree)malloc(sizeof(BiTNode));
biTree->data = data;
CreateBTree(biTree->lChild);
CreateBTree(biTree->rChild);
}
}
void InOrder(BiTree biTree){
if(biTree != NULL){
InOrder(biTree->lChild);
printf("%c ",biTree->data);
InOrder(biTree->rChild);
}return ;
}
void InThreading(BiTree & p,BiTree & pre)
{
if(p){
InThreading(p->lChild,pre);
if(!p->lChild){ //左孩子空，左孩子指针指向前驱
p->lTag=1;
p->lChild=pre;
}
else p->lTag=0;
if(pre && !pre->rChild){ //前驱 的 右孩子空，前驱的右孩子指针指向后继
pre->rTag=1;
pre->rChild=p;
}
pre = p;
pre->rTag = 0;
InThreading(p->rChild,pre);
}
}
BiTree InOrderThreading(BiTree biTree)
{
BiTree threadTree = new BiTNode;
//新加的节点（头节点），树中没有这个点
//中序线索化出的链表的第一个节点的前驱（左孩子指针）指向这个 头节点，
//同时链表最后一个节点的后继（右孩子指针）也指向这个 头结点，
//而这个 头结点的 左孩子指针 指向二叉树的根节点，右孩子指针 指向中序线索化链表的最后一个节点
//类似双向链表
threadTree->lTag = 0; //没有左孩子
threadTree->rTag = 1; //有右孩子
threadTree->rChild = threadTree; //右指针回指
if(!biTree){//空树 左指针 回指
threadTree->lChild = threadTree;
}
else {
threadTree->lChild = biTree;
BiTree pre = threadTree;
InThreading(biTree,pre);//中序线索化
pre->rChild = threadTree;
pre->rTag = 1;
threadTree->rChild = pre;
}
return threadTree;
}
void InOrderTraverse_Thr(BiTree biTree)//中序遍历线索二杈树的非递归算法, biTree 指向头结点
{
BiTree p = biTree->lChild; //p指向根结点
while (p != biTree) //空树或遍历结束时，p == biTree
{
//从根开始寻找第一个结点，中根序列第一个节点是没有左孩子的，也就是lTag = 0
//这点是区分 中序线索化 的标志，同样的，其它的线索化也都根据相应的特点来做
while (p->lTag == 0)
{
p = p->lChild;
}
printf("%c ",p->data);
while (p->rTag == 1 && p->rChild != biTree)//访问后继结点
{
p = p->rChild;
printf("%c ",p->data);
}
p = p->rChild;
}
}
BiTree NewBTree(char x)//构造一个数据域为x的新结点
{
BiTree s = new BiTNode;
s->data = x;
s->lChild = s->rChild = NULL;
s->lTag = s->rTag = 0;
return s;
}
void Insert(BiTree & b, BiTree s)//在二杈排序树中插入新结点s
{
if (b == NULL)
b = s;
//else if(b->data == s->data)//不做任何插入操作
// return;
else if(b->data > s->data)//把s所指结点插入到左子树中
Insert(b->lChild, s);
else //把s所指结点插入到右子树中
Insert(b->rChild, s);
}
int main()
{
BiTree biTree=NULL;
//puts("Input:12300400500");
puts("Input:ABD000CE00F00");
/*********************
A
/ /
B C
/ / /
D E F
*********************/
CreateBTree(biTree);
puts("中根遍历二叉树（递归）：");
InOrder(biTree);puts("");
puts("");
BiTree BT = InOrderThreading(biTree);
puts("中根遍历线索二叉树（非递归）：");
InOrderTraverse_Thr(BT);puts("");
return 0;
}
作者：l04205613
