用递归和非递归方法遍历二叉树的前，中，后序代码,C代码库,德仔网

代码语言

代码分类

【C】用递归和非递归方法遍历二叉树的前，中，后序

作者:青田 / 发布于2013/5/6/ 743


	#include<stdio.h>
	#include<stdlib.h>
	#include<string.h>
	#define NULLKY '#'
	#define MAX_NODE 200
	char a[MAX_NODE];
	typedef struct BTNode{
	char data;
	struct BTNode *Lchild,*Rchild;
	int flag;
	}BTNode,*BiTree;
	typedef struct Stack
	{
	BiTree tree[20];
	int top,bottom;
	}Stack,*StackList;
	StackList InitStack()
	{
	StackList Stack;
	Stack=(StackList)malloc(sizeof(Stack));
	if(Stack==NULL)
	{
	 printf("内存分配失败！！");
	 exit(0);
	}
	else
	{
	 Stack->top=0;
	 Stack->bottom=0;
	}
	return Stack;
	}

	//按先序序列创建二叉树
	int CreateBiTree(BiTree &T,int &index,int &n){
	 if(index == n){
	 return 0;
	 }
	 //按先序次序输入二叉树中结点的值（一个字符），&lsquo;#&rsquo;表示空树
	 if(a[index] ==NULLKY){
	 T = NULL;
	 index++;
	 }
	 else{
	 T = (BiTree)malloc(sizeof(BTNode));
	 //生成根结点
	 T->data = a[index];
	 index++;
	 //构造左子树
	 CreateBiTree(T->Lchild,index,n);
	 //构造右子树
	 CreateBiTree(T->Rchild,index,n);
	 }
	 return 0;
	}
	//输出二叉树序列
	void Print(BiTree T)
	{
	if(T->data!=NULLKY)
	 printf("%c ",T->data);
	}
	//递归法先序遍历
	int PreOrder(BiTree T){
	 if(T != NULL){
	 //访问根节点
	 Print(T);
	 //访问左结点
	 PreOrder(T->Lchild);
	
	 //访问右结点
	 PreOrder(T->Rchild);
	 }
	 return 0;
	}
	//递归法中序遍历
	int InOrder(BiTree T){
	 if(T != NULL){
	 //访问左结点
	 InOrder(T->Lchild);
	 //访问根节点
	 Print(T);
	 //访问右结点
	 InOrder(T->Rchild);
	 }
	 return 0;
	}
	//递归法后序遍历
	int PostOrder(BiTree T){
	if(T!=NULL){
	 //访问左结点
	 PostOrder(T->Lchild);
	 //访问右结点
	 PostOrder(T->Rchild);
	 //访问根节点
	 Print(T);
	}
	return 0;
	}
	//非递归法先序遍历
	void PreorderTraverse(BiTree T,StackList Stack){
	while(Stack->top||T){
	 if(T){
	 printf("%c ",T->data);
	 Stack->tree[Stack->top]=T;
	 Stack->top=Stack->top+1;
	 T=T->Lchild;}

	 else{
	 Stack->top--;
	 T=Stack->tree[Stack->top];
	
	 T=T->Rchild;
	 }
	}
	}
	//非递归法中序遍历
	void InorderTraverse(BiTree T,StackList Stack){
	do
	{
	 while(T)
	 {
	 Stack->tree[Stack->top]=T;
	 Stack->top=Stack->top+1;
	 T=T->Lchild;
	 }
	 if(Stack->top)
	 {
	 Stack->top--;
	 T=Stack->tree[Stack->top];
	 printf("%c ",T->data);
	 T=T->Rchild;
	 }
	}while(Stack->top||T);
	}
	//非递归法后序遍历
	void PostorderTraverse(BiTree T,StackList Stack){
	while(T ||Stack->top){
	 if(T){
	 if(T->flag==1 ){
	 T->flag = 2; //此时将flag设置成2可让下一次调用此函数访问此二叉树不受影响
	 printf("%c ",T->data);
	 if(!Stack->top)
	 break;
	 Stack->top--;
	T=Stack->tree[Stack->top];
	
	 }
	 else
	 {
	 T->flag = 1;
	 Stack->tree[Stack->top]=T;
	Stack->top=Stack->top+1;
	
	 Stack->tree[Stack->top]=T->Rchild;
	Stack->top=Stack->top+1;
	
	 T = T->Lchild;
	 }
	 }
	 else
	{Stack->top--;
	 T=Stack->tree[Stack->top];
	
	}
	}
	}

	int main(){
	int length,i;
	while(scanf("%s",a)!=EOF){
	 BiTree T;
	 StackList stack;
	 stack=InitStack();

	 length=strlen(a);
	 i=0;
	 CreateBiTree(T,i,length);
	 printf("递归算法的前，中，后序遍历结果是:\n");
	 PreOrder(T);
	 printf("\n");
	 InOrder(T);
	 printf("\n");
	 PostOrder(T);
	 printf("\n");
	 printf("非递归算法的前，中，后序遍历结果是:\n");
	 PreorderTraverse(T,stack);
	 printf("\n");
	 InorderTraverse(T,stack);
	 printf("\n");
	 PostorderTraverse(T,stack);
	 printf("\n");
	}
	
	system("pause");
	return 0;
	}

试试其它关键字

　递归和非递归　

同语言下

可能有用的

青田贡献的其它代码(1)

.用递归和非递归方法遍历二叉树的前，中，后序