实验4.2 二叉树的非递归遍历
程序员文章站
2022-06-07 20:47:17
...
头文件
#include<dos.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
定义结构体
#define MAX 100
enum BOOL{False,True};
//在后序遍历时指示是否已访问过右子树
enum RVISIT{Rchildnovisit,Rchildvisit};
typedef struct BitNode //定义二叉树节点结构
{
char data; //数据域
struct BitNode* lchild, * rchild; //左右孩子指针域
}BitNode,*BiTree;
typedef struct //定义栈堆结构
{
BiTree elem[MAX]; //栈区
int top; //栈顶指针
}BiTreeStack;
初始化栈
void initial(BiTreeStack& s)
{
s.top = -1;
}
//入栈
BOOL push(BiTreeStack& s, BiTree ch)
{
if (s.top >= MAX - 1)
return False;
else
{
s.top++;
s.elem[s.top] = ch;
return True;
}
}
出栈
BOOL pop(BiTreeStack& s, BiTree& ch)
{
if (s.top <= -1)
return False;
else
{
ch = s.elem[s.top];
s.top--;
return True;
}
}
取栈顶元素值
BOOL gettop(BiTreeStack s, BiTree& ch)
{
if (s.top <= -1)
return False;
else
{
ch = s.elem[s.top];
return True;
}
}
判断栈是否为空
BOOL stackempty(BiTreeStack s)
{
if (s.top <= -1)
return True;
else
return False;
}
生成一颗二叉树
void creatbitree(BiTree& T)
{
char ch;
scanf("%c",&ch);
if (ch == ' ')
T = NULL;
else
{
T = (BitNode*)malloc(sizeof(BitNode));
T->data = ch;
creatbitree(T->lchild);
creatbitree(T->rchild);
}
}
前序
void preorder(BiTree T)
{
BiTreeStack S;
BiTree p;
initial(S);
p = T;
while (p||!stackempty(S)) //指针指向空及栈为空时结束循环
{
if (p)
{
printf("%c", p->data);
push(S, p);
p = p->lchild;
}
else
{
pop(S, p);
p = p->rchild;
}
}
printf("\n");
}
中序
void inorder(BiTree T)
{
BiTreeStack S;
BiTree p;
initial(S);
p = T;
while (p || !stackempty(S))
{
if (p)
{
push(S, p);
p = p->lchild;
}
else
{
pop(S, p);
printf("%c", p->data);
p = p->rchild;
}
}
printf("\n");
}
后序
void postorder(BiTree T)
{
BiTreeStack S;
BiTree p,q;
RVISIT tag;
initial(S);
p = T;
do
{
while(p)
{
push(S,p); //将左节点都入栈
p=p->lchild;
}
q=NULL; //起始的q为null,即叶子节点的下一节点
tag=Rchildvisit; //tag=1
while(!stackempty(S)&&tag) //tag=1&栈不为空
{
gettop(S,p); //取此时的栈顶元素
//初始的p为左侧的叶子节点,叶子结点的右节点为null,等于初始q
//按后序的左右中,将左节点输出
if(p->rchild==q)
{
printf("%c",p->data);
pop(S,p);
q=p;//否则会陷入在右侧叶子节点及其双亲之间的死循环
}
else
{
p=p->rchild; //开始处理右侧结点
tag=Rchildnovisit; //tag=0,退出本次循环,再处理此右节点的左节点,形成完整的循环
}
}
}while(!stackempty(S));
printf("\n");
}
主函数
int main()
{
BiTree T;
char ch, j;
int flag = 1;
BOOL temp;
//--------------------程序解说-----------------
printf("本程序实现二叉树的非递归遍历操作。\n");
printf("可以实现建立二叉树,非递归先序、中序、后序遍历二叉树\n");
//---------------------------------------------
printf("请将先序遍历二叉树的结果输入以建立二叉树。\n");
printf("对于叶子结点以空格表示。\n");
printf("例如:abc de g f (回车),建立如下二叉树:\n");
printf(" a \n");
printf(" / \n");
printf(" b \n");
printf(" / \\ \n");
printf(" c d \n");
printf(" / \\ \n");
printf(" e f \n");
printf(" \\ \n");
printf(" g \n");
creatbitree(T);
getchar();
while (flag)
{
printf("请选择: \n");
printf("1.非递归先序遍历\n");
printf("2.非递归中序遍历\n");
printf("3.非递归后序遍历\n");
printf("4.退出程序\n");
scanf("%c", &j);
getchar();
switch (j)
{
case '1':
if (T)
{
printf("先序遍历二叉树:");
preorder(T);
printf("\n");
}
else
printf("二叉树为空!\n");
break;
case '2':
if (T)
{
printf("中序遍历二叉树:");
inorder(T);
printf("\n");
}
else
printf("二叉树为空!\n");
break;
case '3':
if (T)
{
printf("后序遍历二叉树");
postorder(T);
printf("\n");
}
else
printf("二叉树为空!\n");
break;
default:
flag = 0;
printf("程序运行结束,按任意键结束!\n");
}
}
getch();
}
运行结果
上一篇: 这个东西在smarty的模板中应该如何写
下一篇: pta-7-40 列出叶结点 (25分)