二叉树的前序、中序、后序、层次、线索、遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BiNode{
char data;
struct BiNodelchild,rchild;
int ltag,rtag;
}BINODE,BiTree;
BINODEpre=NULL;
//创建二叉树
void CreateBiTree(BiTree t)
{
char ch;
ch=getchar();
if(ch==’#’) t=NULL;
else
{
t=(BiTree)malloc(sizeof(BINODE));
(t)->data=ch;
(t)->ltag=(t)->rtag=0;
CreateBiTree(&(t)->lchild);
CreateBiTree(&(t)->rchild);
}
}
//先序遍历
void Pre(BiTree T)
{
if(T)
{
printf(“%c”,T->data);
Pre(T->lchild);
Pre(T->rchild);
}
}
//中序遍历
void Mid(BiTree T)
{
if(T)
{
printf(“%c”,T->data);
Mid(T->lchild);
Mid(T->rchild);
}
}
//后序遍历
void Back(BiTree T)
{
if(T)
{
printf(“%c”,T->data);
Back(T->lchild);
Back(T->rchild);
}
}
void level(BiTree T)
{
//用队列
BiTree queue[1000],b;
int beg=0,end=0;
if(T)
{
queue[end++]=T;
while(beg!=end)
{
b=queue[beg++];
printf(“%c”,b->data);
if(b->lchild!=NULL) queue[end++]=b->lchild;
if(b->rchild!=NULL) queue[end++]=b->rchild;
}
}
}
//线索遍历：
//1.以结点p为根的中序线索化
void MidThread(BiTree p)
{
if(p)
{
MidThread(p->lchild);
if(!p->lchild)
{
p->lchild=pre;
p->ltag=1;
}
if(!pre->rchild)
{
pre->rchild=p;
pre->rtag=1;
}
pre=p;
MidThread(p->rchild);
}
}
//将整个二叉树中序线索化
BINIDECreateMidThread(BiTree T)
{
BINODEhead;
head=(BINODE)malloc(szieof(BINODE));
head->rtag=1; //后继
head->rchild=head; //右孩子指向自己
head->ltag=0; //有左孩子
head->lchild=T; //头节点左孩子指向树根
pre=head;
MidThread(t);
pre->rtag=1;
pre->rchild=head;
head->rchild=pre;
return head;
}
//计算二叉树深度
int Depth(BiTree T)
{
if(T==NULL) return 0;
int m,n;
m=Depth(T->lchild);
n=Depth(T->rchild);
if(m>n) return m+1;
else return n+1;
}
int main()
{
BiTree T=NULL;
return 0;
}