search-the-tree.zip_The Tree

#include<stdio.h> #include<stdlib.h> #define OK 1; #define ERROR 0; typedef char TElemType; typedef char Status; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; typedef BiTree QElemType; typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*Queue; typedef struct{ Queue front; Queue rear; }LinkQueue; Status InitQueue(LinkQueue &Q){//创建队列 Q.front=(Queue)malloc(sizeof(QNode)); if(!Q.front) return ERROR; Q.front->next=NULL; Q.rear=NULL; return OK; } Status DestroyQueue(LinkQueue &Q){ //销毁队列 while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } return OK; } Status CreateBiTree(BiTree &T){//构造新的二叉树 char c; scanf("%c",&c); if(c=='#') T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; T->data=c;//根节点 CreateBiTree(T->lchild);//左子树 CreateBiTree(T->rchild);//右子树 } return OK; } Status EnQueue(LinkQueue &Q,BiTree T){//进列 Queue p; p=(Queue)malloc(sizeof(QNode)); if(!p) return ERROR; p->data=T; p->next=NULL; if(Q.front->next==NULL) Q.front->next=Q.rear=p; else { Q.rear->next=p; Q.rear=p; } return OK; } BiTree DeQueue(LinkQueue &Q,BiTree T){//出列 Queue p; if(Q.front==Q.rear) return ERROR; p=Q.front->next; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); if(Q.front->next!=NULL) return Q.front->next->data; else return NULL; } Status Visit(TElemType c){ //访问节点操作 printf("%c",c); return OK; } Status HierarchyBiTree(BiTree T) { LinkQueue Q; // 保存当前节点的左右孩子的队列 InitQueue(Q); // 初始化队列 if (T == NULL) return ERROR; //树为空则返回 EnQueue(Q, T); Visit(T->data); // 访问根节点 if (T->lchild) EnQueue(Q, T->lchild); // 若存在左孩子，左孩子进队列 if (T->rchild) EnQueue(Q, T->rchild); // 若存在右孩子，右孩子进队列 while (Q.front!=Q.rear) { // 若队列不空，则层序遍历 T=DeQueue(Q, T); // 出队列 if(T){ Visit(T->data); // 访问当前节点 if (T->lchild) EnQueue(Q, T->lchild); // 若存在左孩子，左孩子进队列 if (T->rchild) EnQueue(Q, T->rchild); // 若存在右孩子，右孩子进队列 } } DestroyQueue(Q); // 释放队列空间 } void main() { BiTree T; printf("请输入："); CreateBiTree(T); printf("层序遍历结果:"); HierarchyBiTree(T); printf("\n"); }