利用中序遍历可以解决二叉树中空出来的内存,以及前驱后继的问题。
lchild | ltag | data | rtag | rchild |
——ltag为0时指向该结点的左孩子,为1时指向该结点的前驱。文章来源:https://www.toymoban.com/news/detail-679504.html
——rtag为0时指向该结点的有孩子,为1时指向该结点的后继。文章来源地址https://www.toymoban.com/news/detail-679504.html
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
//线索存储标志
//Link(0):表示指向左右孩子的指针
//thread(1):表示指向前驱后继的线索
typedef enum{Link,Thread} Pointertag;
typedef struct Bithrnode
{
char data;
struct Bithrnode * lchild ,* rchild;
Pointertag ltag;
Pointertag rtag;
}Bithrnode,*Bithrtree;
//创建一棵二叉树,约定用户遵照前序遍历的方式输入数据
Bithrtree pre;
CreateBithree(Bithrtree *t)
{
char c;
scanf("%c",&c);
if(' '== c)
{
*t = NULL;
}
else
{
*t = (Bithrnode*)malloc(sizeof(Bithrnode));
(*t)->data=c;
(*t)->ltag = Link;
(*t)->rtag = Link;
CreateBithree(&(*t)->lchild);
CreateBithree(&(*t)->rchild);
}
}
//中序遍历
Inthreading(Bithrtree t)
{
if(t)
{
Inthreading(t->lchild);//递归左孩子线索化
if(!t->lchild)
{
t->ltag = Thread;
t->lchild = pre;
}
if(!pre->rchild)
{
pre->rtag = Thread;
pre->rchild = t;
}
pre = t;
Inthreading(t->rchild);//递归右孩子线索化
}
}
//中序遍历二叉树,非递归
Inordertraverse(Bithrtree t)
{
Bithrtree p;
p = t->lchild;
while(p!= t)
{
while(p->ltag == Link)
{
p=p->lchild;
}
visit(p->data);
while(p->rtag == Thread && p->rchild != t)
{
p=p->rchild;
visit(p->data);
}
p=p->rchild;
}
}
int main()
{
Bithrtree p,t =NULL;
CreateBithree(&t);
Inthreading(t);
printf("中序遍历输出结果为:");
Inordertraverse(p);
printf("\n");
return 0;
}
到了这里,关于数据结构--树4.2.3(线索二叉树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!