128 lines
3.1 KiB
C++
128 lines
3.1 KiB
C++
template<class DT>
|
|
struct ThrBTNode
|
|
{
|
|
DT data; // 数据域
|
|
int lflag; // 左标志域
|
|
int rflag; // 右标志域
|
|
ThrBTNode *lchild; // 左指针域
|
|
ThrBTNode *rchild; // 右指针域
|
|
};
|
|
|
|
|
|
template <class DT> // 创建二叉树
|
|
void CreateBiTree(ThrBTNode<DT> *&bt)
|
|
{ // 按先序序列的顺序输入二叉树,#为空指针域标志;
|
|
char ch;
|
|
cin>>ch; // 输入根结点的数据
|
|
if(ch=='#') // # 表示指针为空，说明树为空
|
|
bt=NULL ;
|
|
else
|
|
{
|
|
bt=new ThrBTNode<DT>; // 新建结点
|
|
if(!bt)
|
|
{
|
|
cout<<"申请内存失败！"<<endl;
|
|
exit(-1); // 申请内存失败退出
|
|
}
|
|
bt->lflag=0; // 非线索
|
|
bt->rflag=0; // 非线索
|
|
bt->data=ch;
|
|
CreateBiTree(bt->lchild); // 递归创建根结点左子树
|
|
CreateBiTree(bt->rchild); // 递归创建根结点右子树
|
|
}
|
|
return;
|
|
}
|
|
|
|
ThrBTNode<char> *pre;
|
|
|
|
//算法5.13 中序线索化二叉树
|
|
template <class DT>
|
|
void InThread(ThrBTNode<DT> *&p)
|
|
{
|
|
|
|
if(p!=NULL) // 结点非空
|
|
{
|
|
InThread(p->lchild); // 中序线索化左子树
|
|
if(p->lchild==NULL) // 结点无左孩子
|
|
{
|
|
p->lflag=1; // 设置前驱线索标识
|
|
p->lchild=pre; // 左孩子指向结点遍历前驱
|
|
}
|
|
if(pre->rchild==NULL) // 结点无右孩子
|
|
{
|
|
pre->rflag=1; // 设置后继线索标识
|
|
pre->rchild=p; // 右孩子指向结点遍历后继
|
|
}
|
|
pre=p; // 前驱指向当前结点
|
|
InThread(p->rchild); // 中序线索化右子树
|
|
}
|
|
}
|
|
|
|
|
|
template<class DT> // 构建中序线索二叉树
|
|
ThrBTNode<DT> * CreateInThread(ThrBTNode<DT> *&bt)
|
|
{
|
|
ThrBTNode<DT> *root;
|
|
root=new ThrBTNode<DT>; // 创建头结点
|
|
root->lflag=0;
|
|
root->rflag=1;
|
|
root->rchild=bt;
|
|
if(bt==NULL)
|
|
root->lchild=root;
|
|
else
|
|
{
|
|
root->lchild=bt;
|
|
pre=root;
|
|
InThread(bt); // 中序线索化二叉树
|
|
pre->rchild=root; // 设置循环链表
|
|
pre->rflag=1;
|
|
root->rchild=pre;
|
|
}
|
|
return root;
|
|
}
|
|
|
|
//算法5.15 中序遍历中序线索二叉树
|
|
template<class DT>
|
|
void InThrBiTree( ThrBTNode<DT> * bt)
|
|
{
|
|
ThrBTNode<DT> *p;
|
|
p=bt->lchild; // 从根结点开始
|
|
while(p!=bt) // 结点非空
|
|
{
|
|
while (p->lflag==0) // 有左孩子
|
|
p=p->lchild; // 一路左行
|
|
cout<<p->data; // 访问结点
|
|
while(p->rflag==1 && p->rchild!=bt) // 有后继线索且非空
|
|
{
|
|
p=p->rchild; // 转向后继
|
|
cout<<p->data<<" "; // 访问后继结点
|
|
}
|
|
p=p->rchild; // 无后继线索，转向右子树
|
|
}
|
|
}
|
|
|
|
template <class DT> // 显示线索二叉树
|
|
void DispBiTree(ThrBTNode<DT> * bt,int level)
|
|
{
|
|
if(bt) // 空二叉树不显示
|
|
{ DispBiTree(bt->rchild,level+1); // 显示右子树
|
|
cout<<endl; // 显示新行
|
|
for(int i=0;i<level-1;i++)
|
|
cout<<" "; // 确保在第level列显示节点
|
|
cout<<bt->data; // 显示节点
|
|
DispBiTree(bt->lchild,level+1); // 显示左子树
|
|
cout<<endl;
|
|
}//if
|
|
}//DisplayBTree
|
|
|
|
//算法5.9 销毁线索二叉树
|
|
template <class DT>
|
|
void DestroyThrBiTree(ThrBTNode<DT> *&bt)
|
|
{
|
|
if(bt)
|
|
{
|
|
DestroyThrBiTree(bt->lchild);
|
|
DestroyThrBiTree(bt->rchild);
|
|
delete bt;
|
|
}
|
|
} |