main.cpp
#include "function.h"
void PreOrder(BiTree p) {if (p != NULL) {printf("%c ", p->c);PreOrder(p->lchild);PreOrder(p->rchild);}
}
void InOrder(BiTree p) {if (p != NULL) {InOrder(p->lchild);printf("%c ", p->c);InOrder(p->rchild);}
}
void PostOrder(BiTree p) {if (p != NULL) {PostOrder(p->lchild);PostOrder(p->rchild);printf("%c ", p->c);}
}
void LevelOrder(BiTree T){LinkQueue Q; InitQueue(Q);BiTree p;EnQueue(Q,T);while (!IsEmpty(Q)){DeQueue(Q,p);putchar(p->c);if(p->lchild){EnQueue(Q,p->lchild);}if(p->rchild){EnQueue(Q,p->rchild);}}
}int main() {BiTree pnew; BiTree tree = NULL; ptag_t phead = NULL, ptail = NULL, listpnew = NULL, pcur = NULL;char c;int i = 0;while (scanf("%c", &c)) { if (c == '\n') {break; }pnew = (BiTree) calloc(1, sizeof(BiNode));pnew->c = c;listpnew = (ptag_t) calloc(1, sizeof(tag_t));listpnew->p = pnew;if (tree == NULL) {tree = pnew; phead = listpnew; ptail = listpnew; pcur = listpnew; } else {ptail->pnext = listpnew;ptail = ptail->pnext; if (pcur->p->lchild == NULL) {pcur->p->lchild = pnew;} else if (pcur->p->rchild == NULL) {pcur->p->rchild = pnew;pcur = pcur->pnext;}}}printf("------------PreOrder------------------\n");PreOrder(tree);printf("\n------------InOrder------------------\n");InOrder(tree);printf("\n------------PostOrder------------------\n");PostOrder(tree);printf("\n------------LevelOrder------------------\n");LevelOrder(tree);return 0;
}
queue.cpp
#include "function.h"void InitQueue(LinkQueue &Q) {Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));Q.front->next = NULL;
}bool IsEmpty(LinkQueue Q) {return Q.front==Q.rear;
}void EnQueue(LinkQueue &Q, ElemType x) {LinkNode *pnew = (LinkNode *) malloc(sizeof(LinkNode));pnew->data = x;pnew->next = NULL;Q.rear->next = pnew;Q.rear = Q.rear->next;
}
bool DeQueue(LinkQueue &Q, ElemType &x) {if (Q.rear == Q.front) return false;LinkNode *q = Q.front->next;Q.front->next = q->next;x = q->data;if (Q.rear == q) {Q.rear = Q.front;}free(q);return true;
}
function.h
#ifndef UNTITLED_FUNCTION_H
#define UNTITLED_FUNCTION_H#endif #include <stdio.h>
#include <stdlib.h>typedef char BiElemType;
typedef struct BiNode {BiElemType c;struct BiNode *lchild;struct BiNode *rchild;
} BiNode, *BiTree;
typedef struct tag {BiTree p;struct tag *pnext;
} tag_t, *ptag_t;
typedef BiTree ElemType;
typedef struct LinkNode {ElemType data;struct LinkNode *next;
} LinkNode;typedef struct {LinkNode *front, *rear;
} LinkQueue;void InitQueue(LinkQueue &Q);
bool IsEmpty(LinkQueue Q);
void EnQueue(LinkQueue &Q, ElemType x);
bool DeQueue(LinkQueue &Q, ElemType &x);