二叉树的基本操作及遍历

时间：2022-11-16 17:31:29
#include<stdio.h>
#include<stdlib.h>
#define LENGTH 100//初始分配栈的长度
#define ADD_LEN 10//栈长增量
typedef struct BiTNode
{//构造二叉树结点类型
char data;
struct BiTNode *LChild,*RChild;
}BiTNode, *BiTree;
typedef struct 
{//构造栈的数据类型 
BiTNode *base;
BiTNode *top;
int stacksize;
}SqStack;
typedef struct QNode
{//构造队列结点类型
BiTNode data;
struct QNode *next;
}*QueuePtr;
typedef struct 
{QueuePtr front;
QueuePtr rear;
}LinkQueue;
void Print(char e)
{//遍历输出函数
printf("%c",e);
}
void CreateStack(SqStack &S);//初始化一个栈
void PushStack(SqStack &S,BiTNode &e);//e进栈
void PopStack(SqStack &S,BiTNode &e);//栈顶元素出栈
int StackEmpty(SqStack &S);//判断栈是否为空
int GetTop(SqStack &S,BiTNode &e);//获取栈头元素
void CreateQueue(LinkQueue &Q);//创建队列
void EnQueue(LinkQueue &Q,BiTNode &e);//插入元素进队
void DeQueue(LinkQueue &Q,BiTNode &e);//删除并输出队头元素
int QueueEmpty(LinkQueue &Q);//判断队列是否为空
void CreateBiTree(BiTree &T);//创建树
void PreOrderTraverse(BiTree T,void (*Visit)(char e));
void InOrderTraverse(BiTree T,void (*Visit)(char e));
void PostOrderTraverse(BiTree T,void (*Visit)(char e));
void LevelOrderTraverse(BiTree T,void (*Visit)(char e));
void InsertChild(BiTree T);//插入树结点
void DeleteChild(BiTree T);//删除树结点
void main()//修改的是树的根结点的左右孩子，每次修改树结点后进行层序遍历输出
{BiTree T;
printf("用先序输入二叉树并以#表示为空的子树\n");
printf("例如：若想输入二叉树     a\n");
printf("                      b     c\n");
printf("则应该输入:ab##c##\n");
printf("Please input the tree:");
CreateBiTree(T);
getchar();//去掉遗留的回车，否则会影响下个二叉树的创建
printf("先序遍历输出：");
PreOrderTraverse(T,Print);
printf("\n");
printf("中序遍历输出：");
InOrderTraverse(T,Print);
printf("\n");
printf("后序遍历输出：");
PostOrderTraverse(T,Print);
printf("\n");
printf("层序遍历输出：");
LevelOrderTraverse(T,Print);
printf("\n");
InsertChild(T);
printf("层序遍历输出：");
LevelOrderTraverse(T,Print);
printf("\n");
DeleteChild(T);
printf("层序遍历输出：");
LevelOrderTraverse(T,Print);
printf("\n");
}
void CreateStack(SqStack &S)
{S.base=(BiTNode *)malloc(LENGTH*sizeof(BiTNode));
if(!S.base)
{printf("Fail to create stack!\n");
return;
}
S.top=S.base;
S.stacksize=LENGTH;
}
void PushStack(SqStack &S,BiTNode &e)
{if(S.top-S.base>=S.stacksize)//考虑栈是否已满，如满，则从新分配空间
{S.base=(BiTNode *)realloc(S.base,(S.stacksize+ADD_LEN)*sizeof(BiTNode));
if(!S.base)
return;
S.top=S.base+S.stacksize;
S.stacksize+=ADD_LEN;
}
*S.top=e;
S.top++;
} 
void PopStack(SqStack &S,BiTNode &e)
{if(S.top==S.base)
{printf("The stack is empty!\n");
return;
}
S.top=S.top-1;
e=*S.top;
}
int StackEmpty(SqStack &S)
{if(S.top==S.base)
return 1;
return 0;
}
int GetTop(SqStack &S,BiTNode &e)
{if(S.base==S.top)
return 0;
e=*(S.top-1);
return 1;
}
void CreateQueue(LinkQueue &Q)
{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
{printf("Fail to create queue!\n");
return;
}
Q.front->next=NULL;
}
void EnQueue(LinkQueue &Q,BiTNode &e)
{QueuePtr p;
if(!(p=(QueuePtr)malloc(sizeof(QNode))))
{printf("Fail to insert element!\n");
return;
}
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
void DeQueue(LinkQueue &Q,BiTNode &e)
{QueuePtr q;
BiTNode x;
if(Q.rear==Q.front)
{printf("the queue is empty!\n");
return;
}
q=Q.front->next;
x=q->data;
Q.front->next=q->next;
if(Q.rear==q)
Q.rear=Q.front;
e=q->data;
free(q);
}
int QueueEmpty(LinkQueue &Q)
{if(Q.rear==Q.front)
return 1;
return 0;
}
void CreateBiTree(BiTree &T)
{//用先序次序创建并输入二叉树
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{if(!(T=(BiTree)malloc(sizeof(BiTNode))))
{printf("ERROR!\n");
return;
}
T->data=ch;
CreateBiTree(T->LChild);
CreateBiTree(T->RChild);
}
}
void PreOrderTraverse(BiTree T,void (*Visit)(char e))
{//先序遍历的的递归算法
if(T)
{Visit(T->data);
PreOrderTraverse(T->LChild,Visit);
PreOrderTraverse(T->RChild,Visit);
}
}
void InOrderTraverse(BiTree T,void (*Visit)(char e))
{//中序遍历的的递归算法
if(T)
{InOrderTraverse(T->LChild,Visit);
Visit(T->data);
InOrderTraverse(T->RChild,Visit);
}
}
/*void InOrderTraverse(BiTree T,void (*Visit)(char e))
{//中序遍历的的非递归算法
BiTNode p;
SqStack S;
CreateStack(S);
PushStack(S,*T);
while(!StackEmpty(S))
{while(GetTop(S,p)&&p.data)
{if(p.LChild!=NULL)
PushStack(S,*p.LChild);
else
{S.top->data=0;
S.top++;
}
}
PopStack(S,p);
if(!StackEmpty(S))
{PopStack(S,p);
if(!Visit(p.data))
return 0;
if(p.RChild!=NULL)
PushStack(S,*p.RChild);
else
{S.top->data=0;
S.top++;
}
}
}
}*/
void PostOrderTraverse(BiTree T,void (*Visit)(char e))
{//后序遍历的的递归算法
if(T)
{PostOrderTraverse(T->LChild,Visit);
PostOrderTraverse(T->RChild,Visit);
Visit(T->data);
}
}
void LevelOrderTraverse(BiTree T,void (*Visit)(char e))
{//层序遍历的的非递归算法
LinkQueue Q;
BiTNode p;
if(!T)
return;
CreateQueue(Q);
EnQueue(Q,*T);
while(!QueueEmpty(Q))
{DeQueue(Q,p);
Visit(p.data);
if(p.LChild)
EnQueue(Q,*p.LChild);
if(p.RChild)
EnQueue(Q,*p.RChild);
}
}
void InsertChild(BiTree T)
{BiTNode *p;
p=T;
int LR;
BiTree C;
printf("Please input a tree without rchild:");
CreateBiTree(C);
printf("0->As a LChild to insert\n");
printf("1->As a RChild to insert\n");
printf("Please input the value of LR:");
scanf("%d",&LR);
if(LR==0)
{C->RChild=p->LChild;
p->LChild=C;
}
else if(LR==1)
{C->RChild=p->RChild;
p->RChild=C;
}
}
void DeleteChild(BiTree T)
{BiTNode *p;
int LR;
p=T;
printf("0->Delete the LChild of P.\n");
printf("1->Delete the RChild of P.\n");
printf("Please input the value of LR:");
scanf("%d",&LR);
if(LR==0)
p->LChild=NULL;
else if(LR==1)
p->RChild=NULL;
}

标签：

相关文章