欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的创建与四种遍历之递归版本

程序员文章站 2022-07-05 09:20:32
...

#include <stdio.h>
#include <stdlib.h>

#define maxValue 1000
struct binTreeNode{
	int data;
	binTreeNode * left,*right;
};
binTreeNode * root;
/*
	递归创建二叉树,返回根节点指针
	输入要求:类似先根遍历的输入顺序,如果哪个节点的孩子为空,那么输入0
	例如针对
				1
			2		3
		4		5 6		7
	输入顺序为:
	1	2	4	0	0	5	0	0	3	6	0	0	7	0	0
	针对			1
			2		3
		4		5 0		7
	输入顺序为:
	1	2	4	0	0	5	0	0	3	0	7	0	0
*/
binTreeNode * recCreateBinTree()
{
	int _data = 0;
	binTreeNode * r;
	scanf("%d",&_data);
	
	if(_data == 0)
		r = NULL;
	else
	{
		r = (binTreeNode*)malloc(sizeof(binTreeNode));
		r->data = _data;
		r->left = recCreateBinTree();
		r->right = recCreateBinTree();
	}
	return r;
}

/*
递归版本的先根遍历
*/
void recPreOrder(binTreeNode *root)
{
	if(root != NULL)
	{
		printf("%d\n",root->data);
		recPreOrder(root->left);
		recPreOrder(root->right);
	}
}
/*
递归版本的中根遍历
*/
void recInOrder(binTreeNode *root)
{
	if(root != NULL)
	{	
		recInOrder(root->left);
		printf("%d\n",root->data);
		recInOrder(root->right);
	}
}
/*
递归版本的后根遍历
*/
void recPostOrder(binTreeNode *root)
{
	if(root != NULL)
	{	
		recPostOrder(root->left);		
		recPostOrder(root->right);
		printf("%d\n",root->data);
	}
}
/*
层次遍历
利用数组模拟队列
但是当元素多于1000时候,不可处理
*/
void leverOrder(binTreeNode * root)
{
	binTreeNode * queue[1000];
	binTreeNode *tmp;
	int head = 0;
	int tail = 0;
	if(root != NULL)
	{
		queue[tail] = root; //队列操作,while前边先压入首元素
		tail ++ ;
		while(tail > head) 
		{
			tmp = queue[head]; //弹出队列头元素
			head ++;
			printf("%d\n",tmp->data); //针对首元素的操作
			//压入后继元素
			if(tmp->left != NULL) 
			{
				queue[tail] = tmp->left;
				tail ++ ;
			}			
			if(tmp->right != NULL)
			{
				queue[tail] = tmp->right;
				tail ++;
			}
		}
	}	
}
/*
层次遍历
利用数组模拟队列
而且利用取余,模拟循环队列
*/
void leverOrder2(binTreeNode * root)
{
	binTreeNode * queue[maxValue];
	binTreeNode *tmp;
	int head = 0;
	int tail = 0;
	if(root != NULL)
	{
		queue[tail] = root; //队列操作,while前边先压入首元素
		tail ++ ;
		while(tail != head) 
		{
			tmp = queue[head]; //弹出队列头元素
			head = (head + 1) % maxValue;
			printf("%d\n",tmp->data); //针对首元素的操作
			
			//压入后继元素
			if(tmp->left != NULL) 
			{
				queue[tail] = tmp->left;
				tail = (tail + 1)% maxValue;
			}			
			if(tmp->right != NULL)
			{
				queue[tail] = tmp->right;
				tail = (tail + 1)% maxValue;
			}
		}
	}	
}
int main()
{
	freopen("in.txt","r",stdin);
	root = recCreateBinTree();
	fclose(stdin);
	printf("preOrder:\n");
	recPreOrder(root);	
	printf("inOrder:\n");
	recInOrder(root);
	printf("postOrder:\n");
	recPostOrder(root);
	printf("leverOrder:\n");
	leverOrder2(root);
	return 0;
}