#include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define QueueElementType BitTree
typedef int DataType;
typedef struct BitNode
{
DataType data;
struct BitNode LChild;
struct BitNode *RChild;
}BitNode,*BitTree;
typedef struct Node
{QueueElementType data;
struct Node *next;
}LinkQueueNode;
typedef struct BitTree
{LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
int InitQueue(LinkQueue *Q)/将Q初始化为一个空的链队列*/
{Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
if(Q->front!=NULL)
{Q->rear=Q->front;
Q->front->next=NULL;
return(TRUE);
}
else return(FALSE);/*溢出*/
}
int EnterQueue(LinkQueue Q,QueueElementType x)
{LinkQueueNode *NewNode;
NewNode=(LinkQueueNode)malloc(sizeof(LinkQueueNode));
if(NewNode!=NULL)
{NewNode->data=x;
NewNode->next=NULL;
Q->rear->next=NewNode;
Q->rear=NewNode;
return(TRUE);
}
else return(FALSE);/*溢出*/
}
int DeleteQueue(LinkQueue Q,QueueElementType *x)
{LinkQueueNode *p;
if(Q->front==Q->rear)
return(FALSE);
p=Q->front->next;
Q->front->next=p->next;/队头元素出队*/
if(Q->rear==p)
Q->rear=Q->front;
x=p->data;
free(p);
return(TRUE);
}
int IsEmpty(LinkQueue *Q)
{if((Q->front)==(Q->rear))
return TRUE;
else
return FALSE;
}
int CreatBiTree(BitTree *bt)/用扩展先序遍历序列创建二叉树，如果是#当前树根置为空，否则申请一个新节点*/
{
char ch;
do
{scanf("%c",&ch);
}while(ch=='\n');
if(ch=='0') bt=NULL;
else
{
*bt=(BitTree)malloc(sizeof(BitNode));
(*bt)->data=ch;
CreatBiTree(&((*bt)->LChild));
CreatBiTree(&((*bt)->RChild));
}
return OK;
}
void Visit(char ch)/访问根节点*/
{
printf("%c",ch);
}
void PreOrder(BitTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/
{
if (root!=NULL)
{
Visit(root ->data); /*访问根结点*/
PreOrder(root ->LChild); /*先序遍历左子树*/
PreOrder(root ->RChild); /*先序遍历右子树*/
}
}
void InOrder(BitTree root)
/*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/
{
if (root!=NULL)
{
InOrder(root ->LChild); /*中序遍历左子树*/
Visit(root ->data); /*访问根结点*/
InOrder(root ->RChild); /*中序遍历右子树*/
}
}
void PostOrder(BitTree root)
/* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/
{
if(root!=NULL)
{
PostOrder(root ->LChild); /*后序遍历左子树*/
PostOrder(root ->RChild); /*后序遍历右子树*/
Visit(root ->data); /*访问根结点*/
}
}
int LayerOrder(BitTree bt)
{LinkQueue Q;
BitTree p;
InitQueue(&Q);/*初始化队列*/
if(bt==NULL) return ERROR;/*二叉树为空树则结束遍历*/
EnterQueue(&Q,bt);/*二叉树非空则根节点bt入队，开始层次遍历*/
while(IsEmpty(&Q)!=1) /*若队列非空则遍历继续*/
{DeleteQueue(&Q,&p);/*对头元素出对并访问*/
Visit(p->data);
if(p->LChild!=NULL) EnterQueue(&Q,p->LChild);/*若p的左孩子非空则入队*/
if(p->RChild!=NULL) EnterQueue(&Q,p->RChild);
}
return OK;
}
void path(BitTree root,char r)
{BitNode *p,*q;
int i,top=0;
BitTree s[50];
q=NULL;
p=root;
while(p!=NULL||top!=0)
{while(p!=NULL)
{top++;
if(top>=50)
exit(0);
s[top]=p;
p=p->LChild;
}
if(top>0)
{p=s[top];
if(p->RChild==NULL||p->RChild==q)
{if(p->data==r)
{for(i=1;i<=top;i++)
printf("%c",s[i]->data);
return ;
}
else
{q=p;
top--;
p=NULL;
}
}
else p=p->RChild;
}
}
}
int main()
{
BitTree T;
int h,x;
char *r;
printf("请选择一下内容：\n");
printf("1.建立二叉树的存储结构。\n");
printf("2.求二叉树先序遍历序列。\n");
printf("3.求二叉树中序遍历序列。\n");
printf("4.求二叉树后序遍历序列。\n");
printf("5.求二叉树的层序遍历序列。\n");
printf("6.求根节点到指定节点的路径。\n");
do{
printf("请做出选择：");
scanf("%d",&h);
switch(h)
{case 1:printf("请输入二叉树中的元素(以扩展先序遍历序列输入,其中.代表空子树):\n");
CreatBiTree(&T);break;
case 2:printf("先序遍历序列为:");
PreOrder(T);break;
case 3:printf("\n中序遍历序列为:");
InOrder(T);break;
case 4:printf("\n后序遍历序列为:");
PostOrder(T);break;
case 5:printf("\n层序遍历序列为:");
LayerOrder(T);
break;
case 6:printf("\n根节点到指定节点的路径：");
scanf("%c",&r);
path(T,r);
break;
}
}while(h!=0);
printf("退出");
}
[Warning] passing arg 2 of `path' makes integer from pointer without a cast 这个警告怎么处理啊！！！
