binary_tree_levelorder.cpp

binary_tree_level_order(二叉树层排序): 输入:数组{1,2,3,4,5,6,7,8,9,10},建立二叉树,再进行层排序. 输出:输出排序结果.

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

#define n 10

typedef struct bitree
{
	int data;
	struct bitree *left;
	struct bitree *right;
}BITREE;

BITREE * root=NULL;

void creat_tree(int *);
void level_order(void);


int main(void)
{
	int a[n]={1,2,3,4,5,6,7,8,9,10};
	creat_tree(a);
    level_order();
	return 0;
}

void creat_tree(int *a)
{
	int i;
	BITREE * newnode,*ptr;
	for(i=0;i<n;++i)
	{
		newnode=(BITREE *)malloc(sizeof(BITREE));
		if(newnode==NULL)
		{
			printf("memory malloc fail\n");
			break;
		}
		if(root==NULL)
		{
			newnode->data=a[i];
			newnode->left=NULL;
			newnode->right=NULL;
			root=newnode;
			continue;
		}
		else
		{
			ptr=root;
			while(1)
			{
				if(ptr->data>=a[i])
				{
					if(ptr->left==NULL)
					{
						newnode->data=a[i];
			            newnode->left=NULL;
			            newnode->right=NULL;
						ptr->left=newnode;
						break;
					}
					else
						ptr=ptr->left;
				}
				else
				{
					if(ptr->right==NULL)
					{
						newnode->data=a[i];
			            newnode->left=NULL;
			            newnode->right=NULL;
						ptr->right=newnode;
						break;
					}
					else
						ptr=ptr->right;
				}
			}
		}
	}
}

void level_order(void)
{
	BITREE *ptr,*pt[n];
	int i,front=-1,rear=0;
	ptr=root;
	for(i=0;i<n;++i)
		pt[i]=NULL;
	if(ptr==NULL)
		printf("there is no data in the binarytree\n");
	else
	{
		while(ptr!=NULL)
		{
			printf("%d ",ptr->data);
			if(ptr->left!=NULL)
				pt[rear++]=ptr->left;
			if(ptr->right!=NULL)
				pt[rear++]=ptr->right;
			if(front!=rear)
				ptr=pt[++front];
		}
	}
}