线索二叉树的c++实现代码
#include <iostream>using namespace std;
typedef char ElemType;
typedef enum{Link,Thread} PointerTag;
//Link(0)，Thread(1)
// 0表示存储左右孩子的指针，1表示存放前驱和后继
typedef struct BNode{
ElemType data;
struct BNode *lchild,*rchild;
PointerTag rtag,ltag;//记载线索的两个位置
}BNode,*BTree;
//全局变量始终指向刚刚访问的结点
BTree pre;
//创建树，并且初始化zhizhen
void CreatBiTree(BTree *T){
char ch;
cin>>ch;
if( '#' != ch)
{
*T=new BNode;
(*T)->data=ch;
(*T)->ltag=Link;
(*T)->rtag=Link;
CreatBiTree(&(*T)->lchild);
CreatBiTree(&(*T)->rchild);
}
}
//中序遍历
void InOrder(BTree T) {
if (T)
{
InOrder(T->lchild);
if (!T->lchild) //如果左孩子不存在，将左孩子线索化，指向前趋结点
{
T->ltag = Thread;
T->lchild = pre;
}
if(!pre->rchild)//如果上一个结点的右孩子不存在，就让他指向后继结点
{
pre->rtag=Thread;
pre->rchild=T;
}
pre=T;
InOrder(T->rchild);
}
}
//创建头结点，并且完成左右指针的初始化
void InOrderPre(BTree *p,BTree T){
*p=new BNode;
(*p)->ltag=Link;
(*p)->rtag=Thread;//因为最后这个要指向中序遍历最后一个结点，所以先把他线索化
//(*p)->lchild=T;
(*p)->rchild=*p;//首先让他的右边的指针指向自己
if(!T)
{
(*p)->lchild=*p;//如果是空树，左孩子也指向自己了
}else{
(*p)->lchild=T;
pre=*p;//将pre变成了头指针
InOrder(T);
//下面是将头结点和中序遍历最后一个结点构成循环
pre->rchild=*p;
pre->rtag=Thread;
(*p)->rchild=pre;
}
}
//迭代进行中序遍历，并且打印出结果
void InOrderTraverse(BTree T){
BTree p;
p=T->lchild;
while(p != T)
{
while(p->ltag == Link)
{
p=p->lchild;
}
cout<<p->data<<"\t";
while(p->rtag == Thread && p->rchild != T)
{
p=p->rchild;
cout<<p->data<<"\t";
}
p=p->rchild;
}
}
int main(){
BTree T;
BTree p;
CreatBiTree(&T);
InOrderPre(&p,T);
cout<<"输出中序遍历："<<endl;
InOrderTraverse(p);
//InOrder( T);
return 0;
}
本人亲自调试过了，还加了注释
页:
[1]