|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_SIZE 100
typedef char ElemType;
typedef enum {Link,Thread} PointerTag; //Link == 0:指向孩子;Thread == 1:指向线索
//二叉树的结构定义
typedef struct BiThrNode
{
ElemType data;
struct BiThrNode *lchild, *rchild;
PointerTag LTag,RTag; //左右标志
}BiThrNode, *BiThrTree;
BiThrTree pre;
int level;
//创建二叉树,(前序遍历)
void CreateBiTree(BiThrTree T)
{
ElemType c;
scanf("%c",&c);
if(' ' == c )
{
T = NULL;
}
else
{
T = (BiThrTree)malloc(sizeof(BiThrNode));
T->data = c;
T->LTag = Link;
T->RTag = Link;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
//二叉树的线索化
void InTraverse(BiThrTree T)
{
if(T)
{
InTraverse(T->lchild);
if( !T->lchild )
{
T->LTag = Thread;
T->lchild = pre;
}
if( !pre->rchild )
{
pre->RTag = Thread;
pre->rchild = T;
}
pre = T;
InTraverse(T->rchild);
}
}
void InTraversing(BiThrTree temp,BiThrTree T)
{
BiThrTree p;
p = temp;
p = (BiThrTree)malloc(sizeof(BiThrNode));
p->LTag = Link;
p->RTag = Thread;
p->rchild = p;
if( !T )
{
p->lchild = p;
}
else
{
p->lchild = T;
pre = p;
InTraverse(T);
pre->rchild = p;
pre->RTag = Thread;
p->rchild = pre;
}
}
//访问二叉树结点
void visit(ElemType e,int level)
{
printf("%c 在第 %d 层\n",e,level);
}
//遍历二叉树(前序遍历)
void PreOrderTraverse(BiThrTree T,int level)
{
if( T )
{
PreOrderTraverse(T->lchild,level++);
visit(T->data,level);
PreOrderTraverse(T->rchild,level++);
}
}
int main()
{
BiThrTree head,T = NULL;
CreateBiTree(T);
InTraversing(head,T);
PreOrderTraverse(T,level);
system("pause");
return 0;
}
|
|