source.cpp

这个简单的程序写的是几种不同的对二叉树的遍历算法

//先序遍历二叉树的非递归算法
#include <stdio.h>
#include<stdlib.h>

typedef struct node
{
	char data;
	struct node *lchild,*rchild;
}BinTNode;

typedef BinTNode *BinTree;
int count;
#define SSize 10 //假定预分配的栈空间最多为10

typedef struct
{
	BinTree data[SSize];
	int top;
}SeqStack;

void InitStack(SeqStack *S) //初始栈
{
	S->top=-1;
}

int StackEmpty(SeqStack *S) //判栈空
{
	return S->top==-1;
}

int StackFull(SeqStack *S) //判栈满
{
	return S->top==SSize-1;
}

void Push(SeqStack *S, BinTree x) //进栈
{
	if(StackFull(S))
		printf("栈已满\n"); //上溢退出
	else
		S->data[++S->top]=x; //栈顶指针加1后将x进栈
}

BinTree Pop(SeqStack *S) //出栈
{
	if (StackEmpty(S))
		printf("Stack underflow"); //下溢退出
	else
		return S->data[S->top--]; //栈顶指针返回后将栈顶指针减1
}

BinTree StackTop(SeqStack *S) //取栈顶元素
{
	if (StackEmpty(S))
	printf("栈已空\n");
	return S->data[S->top];
}


void cre(BinTree *T)
{
	char ch;
	scanf("\n%c",&ch);
	if (ch=='0')
	 *T=NULL;
	else
	{
		*T=(BinTNode*)malloc(sizeof(BinTNode));
		(*T)->data=ch;
		cre(&(*T)->lchild);
		cre(&(*T)->rchild);
	}
}

void PreorderN(BinTree T)
{
	//先序遍历二叉树T的非递归算法
	SeqStack *S = new SeqStack;
	BinTree p;
	//printf("!!!!\n");
	InitStack(S);
	
	Push(S,T); //根指针进栈

	while(!StackEmpty(S))
	{
		while(p=StackTop(S))
		{
			printf("%3c",p->data); //访问入栈结点的数据域
			Push(S,p->lchild); //向左走到尽头
		}
		p=Pop(S); //空指针退栈
		if (!StackEmpty(S)) //输出结点，向右一步
		{
			p=Pop(S);
			// printf("%3c",p->data); 
			Push(S,p->rchild);
		}
	}
}//PreorderN 

void TestPreorder(BinTree T)
{
	if(T)
	{
		printf("%c",T->data);	
		TestPreorder(T->lchild);
		TestPreorder(T->rchild);
	}
}

void main()
{
	BinTree T;
	char ch1,ch2;
	printf("选择：");
	ch1='y';
	while(ch1=='y' || ch1=='Y')
	{
		printf("\nA 二叉树建立");
		printf("\nB 先序遍历(递归)");
		printf("\nC 先序遍历(非递归)");
		printf("\nD 退出\n");
		scanf("\n%c",&ch2);
		switch(ch2)
		{
			case 'A':
			case 'a':
				printf("按二叉树带空指针的先序次序输入结点:\n");
				cre(&T);
				printf("二叉树建立成功\n");
				break;
			case 'B':
			case 'b':
				printf("遍历的结果为:\n");
				TestPreorder(T);
				break;
			case 'C':
			case 'c':
				printf("遍历的结果为:\n");
				PreorderN(T);
				break;
			case 'D':
			case 'd':
				ch1='n';
				break;
			default:ch1='n';
		}
	}
}