数据结构——二叉树的遍历

二叉树的先序遍历、中序遍历和后序遍历的递归算法，二叉树的非递归算法。

1、括号表示法创建二叉树

2、实现二叉树的递归遍历算法和非递归遍历算法(非递归算法选做)，依次输出二叉树的先序、中序和后序遍历序列

3、二叉树的遍历遍历二叉树，输出结点值大于C的结点，而小于等于C的结点用*替代

4、遍历二叉树，输出结点值小于D的结点，而大于等于D的结点用*替代

main.cpp

#include <malloc.h>
#include <stdio.h> 
#include <iostream>
using namespace std;

typedef char ElemType;

//Visit函数，对每个节点进行的访问
//需设置函数返回值类型
typedef void Status; 
Status DispLargeThanC(ElemType e)//该函数输出树中大于C的字符 
{
	if(e>'C') 
	{
		printf("%2c",e);
	}
	else
	{
		printf("%2c",'*');
	}
}

Status DispLessThanD(ElemType e)//该函数输出树中小于D的字符 
{
	if(e<'D') 
	{
		printf("%2c",e);
	}
	else
	{
		printf("%2c",'*');
	}
}

#include "BiTree.h" 

int main(int argc, char** argv) {
	
	BTNode *T;
	char str[]="A(B(D(,G)),C(E,F))"; 
	
	CreateBTNode(T,str);
	printf("二叉树：");
	DispBTNode(T);
	
	printf("\n\n------------递归遍历-----------");
	printf("\n\n先序遍历为：");
	PreOrder(T);
	printf("\n中序遍历为：");
	InOrder(T);
	printf("\n后序遍历为：");
	PostOrder(T);
	
	printf("\n\n------------非递归遍历---------");
	printf("\n\n先序遍历为：");
	NonRecurPreOrder(T);
	printf("\n中序遍历为：");
	NonRecurInOrder(T);
	printf("\n后序遍历为：");
	NonRecurPostOrder(T);
	
	cout<<endl<<endl<<endl<<"---------------------------"<<endl;
	
	cout<<"以下输出树中大于C的字符";
	cout<<endl<<"先序："; 
	PreOrderTraverse(T,DispLargeThanC);
	cout<<endl<<"中序："; 
	InOrderTraverse(T,DispLargeThanC);
	cout<<endl<<"后序："; 
	PostOrderTraverse(T,DispLargeThanC);
	
	cout<<endl<<endl<<endl<<"---------------------------"<<endl;
	cout<<"以下输出树中小于D的字符";
	cout<<endl<<"先序："; 
	PreOrderTraverse(T,DispLessThanD);
	cout<<endl<<"中序："; 
	InOrderTraverse(T,DispLessThanD);
	cout<<endl<<"后序："; 
	PostOrderTraverse(T,DispLessThanD);
		
	return 0;
}

BiTree.h

#include <malloc.h>
#include <stdio.h> 

#define MaxSize 50 

typedef struct node
{  
	ElemType  data ;
    struct node  *lchild , *rchild ;
    bool rightSubTreeVisited;	//非递归后序遍历时用 
}BTNode; //二叉树结点类型定义 

void CreateBTNode(BTNode *&b,char *str)
{
	BTNode *St[MaxSize],*p=NULL;
    int top=-1,k,j=0;  
    char ch;
    b=NULL;				//建立的二叉树初始时为空
    ch=str[j];
    while (ch!='\0')   //str未扫描完时循环
	{  
		switch(ch) 
        {
	    	case '(':
				top++;
				St[top]=p;
				k=1; 
				break;	   //为左孩子节点
	 		case ')':
			 	top--;
				break;
	 		case ',':
			 	k=2;
				break;     //为孩子节点右节点
			default:
       			p=(BTNode *)malloc(sizeof(BTNode));
	 			p->data=ch;
	 			p->rightSubTreeVisited=false;//非递归后序遍历时用 
				p->lchild=p->rchild=NULL;
	 			if (b==NULL)    	//p为二叉树的根节点
	     			b=p;
	 			else    		//已建立二叉树根节点
       			{
				   switch(k) 
          		   {
	    				case 1:
							St[top]->lchild=p;
							break;
						case 2:
							St[top]->rchild=p;
							break;
	    			}
       			}
     	}
     	j++;
		ch=str[j];
   }
}

void DispBTNode(BTNode *b) 
{
	if (b!=NULL)
    {  
		printf("%c",b->data);
	 	if (b->lchild!=NULL || b->rchild!=NULL)
	 	{  
		 	printf("(");
	    	DispBTNode(b->lchild);//递归处理左子树
	    	if (b->rchild!=NULL) 
				printf(",");
	    	DispBTNode(b->rchild);//递归处理右子树
	    		printf(")");
	 	}
   }
}

//=========================递归遍历算法=========================
void PreOrder(BTNode *b)
{  
	if (b!=NULL)  
    {  
		printf("%c ",b->data); //访问根节点
	    PreOrder(b->lchild);
	    PreOrder(b->rchild);
    }
}
void InOrder(BTNode *b)
{  
	if (b!=NULL)  
    {  
		InOrder(b->lchild);
	 	printf("%c ",b->data); //访问根节点
	 	InOrder(b->rchild);
    }
 }
void PostOrder(BTNode *b) 
{  
	if (b!=NULL)  
    {  
		PostOrder(b->lchild);
	 	PostOrder(b->rchild);
	 	printf("%c ",b->data); //访问根节点
    }
}

//=========================非递归遍历算法=========================
typedef BTNode* SElemType;
#include "SqStack.h"
void NonRecurPreOrder(BTNode *b)
{
	SqStack *S;
	InitStack(S);	//初始化为空栈
	BTNode *p=b;
	
	while(p||!StackEmpty(S)) 
	{
		if(p)	//碰到一个节点
		{
			printf("%c ",p->data);//访问该节点 
			Push(S,p);//节点进栈 
			p=p->lchild; //进入左子树 
		} 
		else
		{
			Pop(S,p);
			p=p->rchild;
		}
	}	
} 

void NonRecurInOrder(BTNode *b)
{
	SqStack *S;
	InitStack(S);	//初始化为空栈
	BTNode *p=b;
	
	while(p||!StackEmpty(S))
	{
		if(p)
		{
			Push(S,p);
			p=p->lchild;
		}
		else
		{
			Pop(S,p);
			printf("%c ",p->data);//访问该节点 
			p=p->rchild;
		}
	} 
}

bool NonRecurPostOrder(BTNode *b)
{
	SqStack *S;
	InitStack(S);	//初始化为空栈
	BTNode *p=b;
	
	while(p||!StackEmpty(S)) 
	{
		while(p)	//找到最左的节点 
		{
			Push(S,p);
			p=p->lchild;
		}
		Pop(S,p);
		while(p->rightSubTreeVisited == true)//右子树已遍历
		{
			printf("%c ",p->data);//访问该节点
			if(!StackEmpty(S))
				Pop(S,p);
			else
				return true;
		} 
		//右子树未访问，遍历右子树 
		p->rightSubTreeVisited=true; 
		Push(S,p);
		p=p->rchild;
	} 	
}

//======递归遍历算法（对二叉树中每个结点调用Visit函数）========================= 
void PreOrderTraverse(BTNode *b,Status(* Visit)(ElemType e))
{
	if (b!=NULL)  
    {  
		Visit(b->data);     //访问根节点
	    PreOrderTraverse(b->lchild,Visit);
	    PreOrderTraverse(b->rchild,Visit);
    }
}//PreOrderTraverse先序遍历，递归 

void InOrderTraverse(BTNode *b,Status(* Visit)(ElemType e))
{
	if (b!=NULL)  
    {  
		InOrderTraverse(b->lchild,Visit);
	 	Visit(b->data);    //访问根节点
	 	InOrderTraverse(b->rchild,Visit);
    }
}//InOrderTraverse中序遍历，递归 

void PostOrderTraverse(BTNode *b,Status(* Visit)(ElemType e))
{
	if (b!=NULL)  
    {  
		PostOrderTraverse(b->lchild,Visit);
	 	PostOrderTraverse(b->rchild,Visit);
	 	Visit(b->data);    //访问根节点
    }
}//PostOrderTraverse后序遍历，递归 

SqStack.h

#include <malloc.h>
#include <stdio.h> 

//----- 栈的顺序存储表示 -----
#define MaxSize 50
typedef struct 
{
	SElemType data[MaxSize]; 
    int top;		//栈顶指针
}SqStack;

void InitStack(SqStack *&s)
{  
	s=(SqStack *)malloc(sizeof(SqStack));
    s->top=-1;
} 
void DestroyStack(SqStack *&s)
{
	free(s);
}
bool StackEmpty(SqStack *s)
{
	return(s->top==-1);
}
bool Push(SqStack *&s,SElemType e)
{
	if (s->top==MaxSize-1)  //栈满的情况，即栈上溢出
		return false;
    s->top++;		   //栈顶指针增1
    s->data[s->top]=e;	   //元素e放在栈顶指针处
    return true;
}
bool Pop(SqStack *&s,SElemType &e)
{
    if (s->top==-1)	//栈为空的情况，即栈下溢出
		return false;
    e=s->data[s->top];	//取栈顶指针元素的元素
    s->top--;		//栈顶指针减1
    return true;
}
bool GetTop(SqStack *s,SElemType &e)
{
	if (s->top==-1)	//栈为空的情况，即栈下溢出    
    	return false;
    e=s->data[s->top];	//取栈顶指针元素的元素
    return true;
}
int StackLength(SqStack *s)
{
	return s->top+1;
}

void DispStack(SqStack *S)
{
//	printf("\n栈长为：%d",StackLength(S)); 
//	printf("\n当前栈为：");
	
	for(int i=0;i<StackLength(S);i++)
	{
		printf("%c ",S->data[i]);  
	}

}