8.cpp

BiTNode二叉树的递归和非递归遍历(包括中序先序后序)

//库函数和常量定义：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef char TElemType;
typedef  int Status;


//（1）二叉树存储结构定义：
typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

//（2）二叉树递归遍历算法
//1）	先序递归遍历
/*void dDLR(BiTree T)
{//先序遍历二叉树的递归算法
	if (T)
	{	printf("%c ",T->data);
		dDLR(T->lchild);
		dDLR(T->rchild);
	}
}
*/


Status PrintElement(TElemType e)//打印结点
{
	printf("%c ",e);
	return OK;
}
Status PreOrderTraverse(BiTree T,Status (*Visit)(TElemType e))
{//采用二叉链表存储结构，
//先序遍历二叉树T的递归算法，对每个元素进行遍历；
    if(T){
		if((*Visit)(T->data))
			if(PreOrderTraverse(T->lchild,Visit))
				if (PreOrderTraverse(T->rchild,Visit))    
             return OK;
		return ERROR;
	}else return OK;
}//PreOrderTraverse


//2）	中序递归遍历
/*void dLDR(BiTree T)
{//中序遍历二叉树的递归算法
	if (T)
	{	
		dLDR(T->lchild);
		 printf("%c ",T->data);
                dLDR(T->rchild);
	}
}
*/

Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e))
{//采用二叉链表存储结构，中序遍历二叉树T的递归算法，对每个元素进行遍历；
    if(T){
		if(InOrderTraverse(T->lchild,Visit))
			if((*Visit)(T->data))
				if (InOrderTraverse(T->rchild,Visit)) 
                                                                return OK;
		return ERROR;
	}else return OK;
}//InOrderTraverse



//3）	后序递归遍历
/*void dLRD (BiTree T)
{//后序遍历二叉树的递归算法
	if (T)
	{	
		dLRD (T->lchild);
		dLRD (T->rchild);
                printf("%c ",T->data);
	}
}
*/


Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e))
{//采用二叉链表存储结构，后序遍历二叉树T的递归算法，对每个元素进行遍历；
    if(T){
		if(PostOrderTraverse(T->lchild,Visit))
			if(PostOrderTraverse(T->rchild,Visit))
				if ((*Visit)(T->data)) return OK;
		return ERROR;
	}else return OK;
}//PostOrderTraverse

//（3）二叉树创建递归算法
Status CreateBiTree(BiTree &T)
{
	char m;
	scanf("%c",&m);
	if(m=='#')
		T=NULL;
	else
	{
		T=(BiTree)malloc(sizeof(BiTNode));
		if(!T)
			exit(OVERFLOW);
		T->data=m;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}

//（4）按层次遍历写出二叉树创建的非递归算法
BiTree LevelCreateTree(BiTree T)//输入序列：将二叉树视满二叉树或完全二树。
{	BiTree q[100],p,k;//q为队列，f表示队头，w表示队尾。
	int f=0,w=0,n=0;char ch;//n为计数器
	scanf("%c",&ch);
	if (ch=='#'||ch=='@') T=NULL;//空树时
	else{//1
		T=(BiTree)malloc(sizeof(BiTNode));//二叉树根结点的创建
		T->data=ch;
		T->lchild=NULL;
		T->rchild=NULL;//99
		q[w++]=T;
		scanf("%c",&ch);
		while(ch!='@')
		{   n=n%2;
			if (ch!='#')
			{   p=(BiTree)malloc(sizeof(BiTNode));
			    p->data=ch;
p->lchild=NULL;
		        p->rchild=NULL; //99
				q[w++]=p;
				n++;
				if (n==1) {k=q[f];k->lchild=p;}
				else if(n==2)
				{k=q[f++];k->rchild=p;}
				
			}else {p=NULL;
				n++;
				if (n==1) {k=q[f];k->lchild=p;}
				else if(n==2)
				{k=q[f++];k->rchild=p;}
				}
			scanf("%c",&ch);
		}//while
	}//1	
    return T;	
	
}//LevelOrder

void main()
{
    BiTree B;
	CreateBiTree(B);
	printf("\n按先序输出为:\n");
	PreOrderTraverse(B,PrintElement);
	printf("\n按中序输出为:\n");
	InOrderTraverse(B,PrintElement);
	printf("\n按后序输出为:\n");
	PostOrderTraverse(B,PrintElement);
}



/*




void main()
{

InOrderTraverse(T,PrintElement);



}*/