|
|
#2
hzh5122010-05-13 20:37
赞楼主,你把二叉树学了个遍。
给你后序遍历的。 程序代码:#include <stdio.h>//测试值:abc@@de@g@@f@@@ #include <stdlib.h> #define Link 0 #define Thread 1 typedef char TElemType; typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild, *rchild, *parent; int LTag,RTag; }BiThrNode,*BiThrTree; //////// BiThrNode *pre;//全局变量 //////// BiThrTree CreatBiThrTree(BiThrNode *par);//先序创建二叉树 void Visit(char data); void AfterThreading(BiThrNode *p);//后序遍历二叉树 BiThrNode* AfterOrderThreading(BiThrNode *T);//后序线索化二叉树 void AfterorderTraverse_Thr(BiThrNode *T);//**后序**遍历线索二叉树 void main() { BiThrNode *t,*thr=NULL; printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n"); printf("<说明:例如参考数据为:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n"); t=CreatBiThrTree(thr); printf("后序线索化二叉树...\n"); thr=AfterOrderThreading(t); printf("后序遍历后序线索二叉树:\n"); AfterorderTraverse_Thr(thr); printf("\n"); } BiThrTree CreatBiThrTree(BiThrNode *par)//先序创建二叉树 { TElemType ch; BiThrTree T; scanf("%c",&ch); if(ch==' ') T=NULL; else { T=(BiThrTree)malloc(sizeof(BiThrNode)); if(!T) exit(0); T->data=ch; T->parent = par; //// T->LTag=Link; T->RTag=Link; /////////////indispensable** T->lchild=CreatBiThrTree(T); T->rchild=CreatBiThrTree(T); } return T; } void AfterThreading(BiThrNode *p)//后序遍历二叉树 { if (p) { AfterThreading(p->lchild); AfterThreading(p->rchild); if (!p->lchild) { p->LTag=Thread; p->lchild=pre; } if (!p->rchild) p->RTag=Thread; if (pre&&pre->RTag==Thread) pre->rchild=p; pre=p; } } BiThrNode* AfterOrderThreading(BiThrNode *T)//后序线索化二叉树 { BiThrNode *Thrt; Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); if(!Thrt) exit(0); Thrt->LTag=Link; Thrt->RTag=Thread; Thrt->rchild=Thrt; if(!T) Thrt->lchild=Thrt; else { Thrt->lchild=T; T->parent=Thrt; pre=Thrt; AfterThreading(T);//后序遍历进行先序线索化 // T->rchild = Thrt; // pre->rchild=Thrt;// // pre->RTag=Thread; // Thrt->rchild=pre; } return(Thrt); printf("*********!\n"); } void AfterorderTraverse_Thr(BiThrNode *T)//**后序**遍历线索二叉树 { //遍历后序线索二叉树 BiThrTree p = T, q; while (p->rchild != NULL) { if (p->RTag == Thread) { p=p->rchild; Visit(p->data); } else { q= p->parent; if (q == T) { break; } else { if (q->RTag == Thread || q->rchild == p) { p = q; Visit(p->data); } else { q = q->rchild; while (q->LTag != Thread) { q = q->lchild; } p=q; Visit(p->data); } } } } } void Visit(char data) { printf("%c",data); } |
#include <stdio.h>//测试值:abc@@de@g@@f@@@
#include <stdlib.h>
#define Link 0
#define Thread 1
typedef char TElemType;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
////////
BiThrNode *pre;//全局变量
////////
BiThrTree CreatBiThrTree()//先序创建二叉树
{
TElemType ch;
BiThrTree T;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!T)
exit(0);
T->data=ch;
////
T->LTag=Link;
T->RTag=Link;
/////////////indispensable**
T->lchild=CreatBiThrTree();
T->rchild=CreatBiThrTree();
}
return T;
}
void Visit(char data)
{
printf("%c",data);
}
/////////////////////////////////////////////////////
void PreThreading(BiThrNode *p)//先遍历二叉树
{
if (p)
{
if (!p->lchild)
{
p->LTag=Thread;
p->lchild=pre;
}
if (!p->rchild)
p->RTag = Thread;
if (pre&&pre->RTag==Thread)
pre->rchild = p;
pre=p;
if (p->LTag==Link)
PreThreading(p->lchild);
if (p->RTag==Link)
PreThreading(p->rchild);
}
}
BiThrNode* PreOrderThreading(BiThrNode *T)//先序线索化二叉树
{
BiThrNode *Thrt;
Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!Thrt)
exit(0);
Thrt->LTag=Link;
Thrt->RTag=Thread;
Thrt->rchild=Thrt;
if(!T)
Thrt->lchild=Thrt;
else
{
Thrt->lchild=T;
pre=Thrt;
PreThreading(T);//先序遍历进行先序线索化
pre->rchild=Thrt;//最后一个结点线索化
pre->RTag=Thread;
Thrt->rchild=pre;
}
return(Thrt);
}
void PreorderTraverse_Thr(BiThrNode *T)//**先序**遍历线索二叉树
{
//遍历先序线索二叉树
BiThrTree p=T->lchild;//
Visit(p->data);
while (p->rchild!=T)//根左右
{
if (p->LTag==Link)
p=p->lchild;
else
p=p->rchild;
Visit(p->data);
}
}
//////////////////////////////////////////////////////////
void InThreading(BiThrNode *p)//中序遍历二叉树
{
if(p)
{
InThreading(p->lchild);//左子树线索化
if(!p->lchild)//前驱线索
{
p->LTag=Thread;
p->lchild=pre;
}
if(!pre->rchild)//后继线索
{
pre->RTag=Thread;
pre->rchild=p;
}
pre=p;//保持pre指向p的前驱
InThreading(p->rchild);//右子树线索化
}
}
BiThrNode* InOrderThreading(BiThrNode *T)//中序线索化二叉树
{
BiThrNode *Thrt;
Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!Thrt)
exit(0);
Thrt->LTag=Link;
Thrt->RTag=Thread;
Thrt->rchild=Thrt;
if(!T)
Thrt->lchild=Thrt;
else
{
Thrt->lchild=T;
pre=Thrt;
InThreading(T);//中序遍历进行中序线索化
pre->rchild=Thrt;//最后一个结点线索化
pre->RTag=Thread;
Thrt->rchild=pre;
}
return(Thrt);
}
void InorderTraverse_Thr(BiThrNode *T)//(forward)中序遍历线索二叉树
{
BiThrNode *p;
p=T->lchild;
while(p!=T)//空树或遍历结束时,p=T
{
while(p->LTag==Link)
p=p->lchild;
Visit(p->data);//访问左子树为空的结点
while(p->RTag==Thread&&p->rchild!=T)//访问后继结点p->rchild!=T
{
p=p->rchild;
Visit(p->data);
}
p=p->rchild;
}
}
void BackInorderTraverse_Thr(BiThrNode *T)//(back)中序遍历线索二叉树
{
BiThrNode *p;
p=T->rchild;
while(p!=T)
{
while(p->LTag==Thread&&p->lchild!=T)
{
Visit(p->data);//访问中序遍历的最后一个结点
p=p->lchild;//直接访问其前驱
}
Visit(p->data);//访问根节点
p=p->lchild;//转向左子树
while(p->RTag==Link)
p=p->rchild;//找到左子树在中序遍历时的最后一个结点,进入下一次循环
}
}
//////////////////////////////////////////////////////
void AfterThreading(BiThrNode *p)//后序遍历二叉树
{
if (p)
{
AfterThreading(p->lchild);
AfterThreading(p->rchild);
if (!p->lchild)
{
p->LTag=Thread;
p->lchild=pre;
}
if (!p->rchild)
p->RTag=Thread;
if (pre&&pre->RTag==Thread)
pre->rchild=p;
pre=p;
}
}
BiThrNode* AfterOrderThreading(BiThrNode *T)//后序线索化二叉树
{
BiThrNode *Thrt;
Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!Thrt)
exit(0);
Thrt->LTag=Link;
Thrt->RTag=Thread;
Thrt->rchild=Thrt;
if(!T)
Thrt->lchild=Thrt;
else
{
Thrt->lchild=T;
pre=Thrt;
AfterThreading(T);//后序遍历进行先序线索化
// pre->rchild=Thrt;//
// pre->RTag=Thread;
// Thrt->rchild=pre;
}
return(Thrt);
printf("*********!\n");
}
void AfterorderTraverse_Thr(BiThrNode *T)//**后序**遍历线索二叉树
{
//遍历后序线索二叉树
BiThrTree p=T->lchild;//
Visit(p->data);
while (p->rchild!=T)//左右根
{
if (p->LTag==Link)
p=p->lchild;
if(p->RTag==Thread)//直接后继结点
{
p=p->lchild;
Visit(p->data);
}
if(p->LTag==Thread&&p->RTag==Link)//左儿子空,右儿子不空,访问右儿子
{
p=p->rchild;
Visit(p->data);
}
if(p->LTag==Thread&&p->RTag==Thread)//左儿子空,右儿子空,访问根结点
Visit(p->data);
}
}
void main()
{
BiThrNode *t,*thr;
printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n");
printf("<说明:例如参考数据为:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n");
t=CreatBiThrTree();
printf("中序线索化二叉树...\n");
thr=InOrderThreading(t);
printf("线索化工作已经完成!\n");
printf("中序(前向)遍历中序线索二叉树:\n");
InorderTraverse_Thr(thr);
printf("\n");
printf("中序(逆向)遍历中序线索二叉树:\n");
BackInorderTraverse_Thr(thr);
printf("\n");
printf("先序线索化二叉树...\n");
thr=PreOrderThreading(t);
printf("先序遍历先序线索二叉树:\n");
PreorderTraverse_Thr(thr);
printf("\n");
printf("后序线索化二叉树...\n");
thr=AfterOrderThreading(t);
printf("后序遍历后序线索二叉树:\n");
AfterorderTraverse_Thr(thr);
printf("\n");
}
程序代码: