[数据结构]先序递归创建二叉树,并对其进行 先序、中序、后序遍历


数据结构的上机作业/参考

//先序递归创建二叉树,并对其进行 先序、中序、后序遍历
#include // malloc()等
#include  // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等
#include // atoi(),exit()
#include   // 数学函数头文件,包括floor(),ceil(),abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode
{
	int data;	// 结点的值
	BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空
void visit(int e)
{
	printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{	// 操作结果:构造空二叉树T
	T=NULL;
}

void CreateBiTree(BiTree &T)
{	// 算法6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
	// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
	int number;
	scanf("%d",&number);// 输入结点的值
	if(number==Nil)		// 结点的值为空
		T=NULL;
	else			// 结点的值不为空
	{
		T=(BiTree)malloc(sizeof(BiTNode));	// 生成根结点
		if(!T)
			exit(OVERFLOW);
		T->data=number;	// 将值赋给T所指结点
		CreateBiTree(T->lchild);// 递归构造左子树
		CreateBiTree(T->rchild);// 递归构造右子树
	}
}

void DestroyBiTree(BiTree &T)
{ // 初始条件:二叉树T存在。操作结果:销毁二叉树T
	if(T) // 非空树
	{
		DestroyBiTree(T->lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
		DestroyBiTree(T->rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
		free(T); // 释放根结点
		T=NULL; // 空指针赋0
	}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{	// 初始条件:二叉树T存在,Visit是对结点操作的应用函数。修改算法6.1
	// 操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
	if(T) // T不空
	{
		Visit(T->data); // 先访问根结点
		PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
		PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
	}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
{	// 初始条件:二叉树T存在,Visit是对结点操作的应用函数
	// 操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次
	if(T)
	{
		InOrderTraverse(T->lchild,Visit);	// 先中序遍历左子树
		Visit(T->data);			// 再访问根结点
		InOrderTraverse(T->rchild,Visit);	// 最后中序遍历右子树
	}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
{	// 初始条件:二叉树T存在,Visit是对结点操作的应用函数
	// 操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
	if(T) // T不空
	{
		PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
		PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
		Visit(T->data); // 最后访问根结点
	}
}

void main()
{
	BiTree T;
	InitBiTree(T);					// 初始化二叉树T
	printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0n");
	CreateBiTree(T);				// 建立二叉树T
	printf("先序递归遍历二叉树:n");
	PreOrderTraverse(T,visit);		// 先序递归遍历二叉树T
	printf("n中序递归遍历二叉树:n");
	InOrderTraverse(T,visit);		// 中序递归遍历二叉树T
	printf("n后序递归遍历二叉树:n");
	PostOrderTraverse(T,visit);		// 后序递归遍历二叉树T
}

发表评论