#include <stdlib.h>
#include <stdio.h>
#define MAX_TREE_SIZE 100
typedef struct BiTNode {
char data;
struct BiTNode * lchild;
struct BiTNode * rchild;
}BiTNode, *BiTree;
//函数声明
void Print(BiTree &root);
void Selection(int sel,BiTree &root);
void ReadExPreOrder(BiTree &root);
void PrintExPreOrder(BiTree root);
void PostOrderTraverse(BiTree T);
//主函数
void main() {
BiTree root=NULL; //初始化根结点
Print(root);
while (true) {
printf("\nPress enter to continue.........");
getchar();
system("cls");
Print(root);
}
}
void Print(BiTree &root) {
//提示
int sel;
printf("使用说明:本程序可实现二叉链表方式存储的二叉树，输入为扩展先序遍历序列.\n");
printf("---------------------\n");
printf("1.输入扩展先序遍历序列并建立对应的二叉树.\n");
printf("2.打印当前的二叉树的扩展先序遍历序列.\n");
printf("3.后序遍历当前的二叉树并打印遍历序列.\n");
printf("4.按其它任意键退出.\n");
printf("---------------------\n");
printf("请选择你要的操作:");
scanf("%d", &sel);
getchar();
Selection(sel, root);
}
void Selection(int sel, BiTree &root) {
//根据用户输入决定下一步骤
switch (sel) {
case 1: ReadExPreOrder(root);
break;
case 2: PrintExPreOrder(root);
break;
case 3: PostOrderTraverse(root);
break;
default: exit(0);
}
}
void ReadExPreOrder(BiTree &root) {
//先序遍历二叉树，root为指向二叉树（或某一子树）根结点的指针
char ch;
ch = getchar();
if (ch == '.')
root = NULL;
else {
root = (BiTree)malloc(sizeof(BiTNode));
root->data = ch;
ReadExPreOrder(root->lchild);
ReadExPreOrder(root->rchild);
}
}
void PrintExPreOrder(BiTree root) {
char ch;
if (root!=NULL) {
ch = root->data;
printf("%c", ch);
PrintExPreOrder(root->lchild);
PrintExPreOrder(root->rchild);
}
else
printf(".");
}
void PostOrderTraverse(BiTree T) {
BiTree stack[MAX_TREE_SIZE], p;
int tag[MAX_TREE_SIZE],top=0;
p = T;
while(p || top != 0) {
while(p) {
top++;
stack[top]=p;
tag[top]=0;
p=p->lchild;//从根开始，左结点依次入栈
}
if(top> 0) {
if(tag[top]==1){//表示是从该结点的右子树返回，则访问该结//点
p=stack[top];
printf("%c", p->data);
top--;
p=NULL;//将p指向NULL,则下次进入while循环时，不做左子//树入栈操作
}
else{ //表明是从该结点左子树返回，应继续访问其右子树
p=stack[top];
if(top> 0) {
p=p->rchild;
tag[top]=1; //表明该结点的右子树已访问
}
} //end of else
} //end of if
}//end of while
}
No comments:
Post a Comment