16 C++ 二叉树遍历 Binary tree traversal

#define _CRT_SECURE_NO_WARNINGS //solve the scanf error problems
#include “function.h”

void preOrder(BiTree p) {
if (p != NULL) {
printf(“%c\t”, p->c);
preOrder(p->lchild);
preOrder(p->rchild);
}
}

void inOrder(BiTree p) {
if (p != NULL) {

	inOrder(p->lchild);
	printf("%c\t", p->c);
	inOrder(p->rchild);
}
1
2
3
4

}

void postOrder(BiTree p) {
if (p != NULL) {

	postOrder(p->lchild);
	printf("%c\t", p->c);
	postOrder(p->rchild);
}
1
2
3
4

}

void InOredr2(BiTree T) {
SqStack S;
Init_stack(S); BiTree p = T;
while (p || !Stack_empty(S)) {
if § {
Push(S, p);
p = p->lchild;
}
else {
Pop(S, p);
printf(“%c\t”, p->c);
p = p->rchild;
}
}
}

void LevelOrder(BiTree T) {
LinkQueue Q;
Init_queue(Q);
BiTree p;
EnQueue(Q,T);
while (!Is_empty(Q)) {
DeQueue(Q, p);
putchar(p->c);
if (p->lchild != NULL) {
EnQueue(Q, p->lchild);
}
if (p->rchild != NULL) EnQueue(Q, p->rchild);
}
}

//void InThread(BiTree& p, BiTree& pre) {
// if (p != NULL) {
// InThread(p->lchild, pre);
// if (p->lchild == NULL) {
// p->lchild = pre;
// p->ltag = 1;
// }
// if (pre != NULL && pre->rchild == NULL) {
// pre->rchild = p;
// pre->rtag = 1;
//
// }
// pre = p;
// InThread(p->rchild, pre);
// }
//}

int main() {
BiTree pnew;
int i, j, pos;
char c;
BiTree tree = NULL;
ptag_t phead = NULL, ptail = NULL, listpnew, pcur=NULL;
while (scanf(“%c”, &c) != EOF) {
if (c==‘\n’) break;
pnew = (BiTree)calloc(1, sizeof(BiTNode));
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;
continue;
}
else {
ptail->pnext = listpnew;
ptail = listpnew;
}
if (pcur->p->lchild == NULL) {
pcur->p->lchild = pnew;
}
else if (pcur->p->rchild == NULL) {
pcur->p->rchild = pnew;
pcur = pcur->pnext;
}
}
printf(“Preorder traversal\n”);
preOrder(tree);
printf(“Mesoorder traversal\n”);
inOrder(tree);
printf(“Posterior order traversal\n”);
postOrder(tree);
printf(“Mesoorder traversal2\n”);
InOredr2(tree);
printf(“Hierarchical traversal\n”);
LevelOrder(tree);

}