查找二叉树的实现-层序，先序非递归实现

参考书目《数据结构与算法分析(c语言描述)》

//接口函数

#ifndef _SEATREE_H#define _SEATREE_Hstruct TreeNode{	int Element;	struct TreeNode *Left;	struct TreeNode *Right;};typedef struct TreeNode *Position;Position MakeEmpty(Position T);Position Find(int X,Position T);Position FindMin(Position T);Position FindMax(Position T);Position Insert(int X,Position T);Position Delete(int X,Position T);void VisitTree(Position T);void ExchangeTree(Position T);void LevelOrder(Position T);void PReOrder1(Position T);void PreOrder2(Position T);#endif
//接口函数实现
#include <stdio.h>#include <stdlib.h>#include "seatree.h"Position Insert(int X,Position T){	if(T==NULL)	{		T=(Position)malloc(sizeof(struct TreeNode));	    T->Element=X;	    T->Left=T->Right=NULL;	}	else if(X>T->Element)		T->Right=Insert(X,T->Right);	else if(X<T->Element)		T->Left=Insert(X,T->Left);	return T;}Position Delete(int X,Position T)  //递归实现树节点的删除{	Position TmpCell;	if(T==NULL)		return NULL;	else if(X>T->Element)		T->Right=Delete(X,T->Right);	else if(X<T->Element)		T->Left=Delete(X,T->Left);	else if(T->Left!=NULL&&T->Right!=NULL)	{		TmpCell=FindMin(T->Right);		T->Element=TmpCell->Element;		T->Right=Delete(T->Element,T->Right);	}	else	{		TmpCell=T;		if(T->Left==NULL)			T=T->Right;		else 			T=T->Left;		free(TmpCell);	}	return T;}Position Find(int X,Position T){	if(T==NULL)		return NULL;	else if(X<T->Element)		return Find(X,T->Left);	else if(X>T->Element)		return Find(X,T->Right);	else 		return T;}Position FindMin(Position T){	if(T==NULL)		return NULL;	else if(T->Left==NULL)		return T;	else 		return FindMin(T->Left);}Position FindMax(Position T){	if(T==NULL)		return NULL;	else if(T->Right==NULL)		return T;	else		return FindMax(T->Right);}Position MakeEmpty(Position T){	if(T!=NULL)	{		MakeEmpty(T->Left);		MakeEmpty(T->Right);		free(T);	}	return NULL;}void VisitTree(Position T){	if(T!=NULL)	{		//printf("%d ",T->Element); //先序遍历		VisitTree(T->Left);		printf("%3d",T->Element);  //中序遍历		VisitTree(T->Right); 	}}void ExchangeTree(Position T) //树的镜像{	Position temp;	if(T)	{		ExchangeTree(T->Left);		ExchangeTree(T->Right);		temp=T->Left;		T->Left=T->Right;		T->Right=temp;	}}void LevelOrder(Position T)  //层序遍历{	Position stack[100];	int front=0;	int rear=1;	stack[0]=T;	while(front<rear)	{		if(stack[front])		{			printf("%3d",stack[front]->Element);			stack[rear++]=stack[front]->Left;			stack[rear++]=stack[front]->Right;			front++;		}		else		front++;	}}void PreOrder1(Position T)  //先序非递归实现{	Position p,stack[100]; //这里最多储存100个元素	int top;	p=T;	if(T!=NULL)	{		top=0;		stack[top++]=p;		while(top>0)		{			p=stack[--top];			printf("%3d",p->Element);		    if(p->Right)		    {			    stack[top++]=p->Right;		    }		    if(p->Left)		    {			    stack[top++]=p->Left;		    }		}	}}void PreOrder2(Position T){	if(T)	{		printf("%3d",T->Element);		PreOrder2(T->Left);		PreOrder2(T->Right);	}}
//main函数入口
#include <stdio.h>#include "seatree.h"int main(int argc, char **argv){	int rands[12]={21,52,5,1,55,32,66,77,90,34,56,86};	int i;	Position Pos;	Pos=NULL; //初始化的重要性	for(i=0;i<12;i++)	{		Pos=Insert(rands[i],Pos);	}	VisitTree(Pos);	printf("/n");	LevelOrder(Pos);	printf("/n");	PreOrder1(Pos);	printf("/n");	PreOrder2(Pos);	printf("/nMin is %d,Max is %d!/n",FindMin(Pos)->Element,FindMax(Pos)->Element);	ExchangeTree(Pos);	VisitTree(Pos);	printf("/n");	LevelOrder(Pos);	printf("/n");	ExchangeTree(Pos);	LevelOrder(Pos);	//VisitTree(Pos);	Pos=MakeEmpty(Pos);	return 0;}
测试结果：先序遍历与非递归实现相同 由中序遍历可看出树的镜像结果