欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

实验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();
}

运行结果

实验4.2 二叉树的非递归遍历