5 traversebitree_digui.cpp

数据结构的必做编程题

#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>	
#define NULL 0
#define OVERFLOW 0			
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;		
}*BiTree;		


void CreateBiTree(BiTree &T)	//先序扩展序列建立二叉树的递归算法:521**43***76**8*9**
{  
	char ch;
	scanf("%c",&ch);
	if (ch=='*') 
	{
		T = NULL;		
	}
	else 
	{ 
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
		{
			exit(OVERFLOW);
		}
		T->data=ch;
		CreateBiTree(T->lchild); 
		CreateBiTree(T->rchild); 
	}  
} 


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

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

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



void main()
{
	BiTree a;
	printf("请按先序扩展序列输入二叉树,空用*表示\n");
	CreateBiTree(a);	//调用先序扩展序列建立二叉树的递归算法的函数，建立一个二叉树
	
	printf("\n先序遍历二叉树的结果：");
	PreOrder (a);		//先序遍历二叉树
	
	printf("\n中序遍历二叉树的结果：");
	InOrder(a);			//中序遍历二叉树
	
	printf("\n后序遍历二叉树的结果：");
	LastOrder(a);		//后序遍历二叉树

	printf("\n");
}