本文主要是介绍第10周项目实践 线索二叉树的建立及遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
typedef struct node{
Elemtype date;
int ltag,rtag;
struct node lchild;
struct node rchild;
}TBTNode;
TBTNode *pre;//全局变量
void Thread(TBTNode *&p)//对二叉树进行中旭线索化
{
if(p!=NULL)
{
Thread(p->lchild);//左子树线索化
if(p->lchild==NULL)//左孩子不存在,进行前驱结点线索化
{
p->lchild=pre;//建立当前结点的前驱结点
p->ltag=1;//标记当前结点的前驱结点的线索
}
else
p->ltag=0;//p节点的左子树线索话
if(p->rchild==NULL)
{
pre->rchild=p;//对pre后续节点的线索话
pre->rchild=1;
}
else
pre->rtag=0;
pre=p;
Thread(p->rchild);//右子树线索化
}
}
TBTNode *CreateThread(TBTNode *b)//中序线索化二叉树
{
TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode));//建立头节点
root->ltag=0;
root->rtag=1;
root->rchild=b;
if(b!=NULL)
{
root->lchild=b;
pre=root;//pre节点是p的前驱结点
Thread(b);//中序遍历
pre->rchild=root;//最后加入指向头节点的线索
pre->rtag=1;
root->rchild=pre;//头节点右线索话
}
else
root->lchild=root;//b为空,指向其本身,否则root->lchild指向b
return root;
}//
void ThInorder(TBTNode *tb)//中序遍历线索树
{/*在中序遍历树时,开始节点是根节点的最左下节点,(该节点的做指针域为线索,即tag=1,
当找到开始节点后访问他,如果p的右指针是右线索,说明线索指向的就是后继节点,就找到后继节点并访问;
如果节点p的右指针不是右线索,他指向的是右子树,就转向右子树。*/
TBTNode *p=tb->lchild;
while(p!=tb)
{
while(p->lchild==0)
p=p->lchild;
cout<<p->date;
while(p->rtag==1&&p->rchild!=tb)
{
p=p->rchild;
cout<<p->date;
}
p=p->rchild;
}
}
这篇关于第10周项目实践 线索二叉树的建立及遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!