二叉树的广度遍历

二叉树的广度遍历

二叉树的广度遍历思想比较简单，即借助于队列对节点进行入队列和出队列，当节点出队列时对左右子节点进行判断，若存在左右子节点，则左右子节点入队列。

具体代码如下：

//建立二叉树，根据左小右大原则，不用递归，用循环
#include <iostream>
#include <assert.h>
using namespace std;

#define MAX   15
//定义结构体
typedef struct tree{
	struct tree *left,*right;
	int data;
}treenode,*b_tree;

typedef struct Qnode
{   treenode *m_treenode;
	struct Qnode *next;
}QNode,*p_QNode;                      /*链队列的结点定义*/ 


typedef struct
{
	p_QNode front ;             /*头指针*/
	p_QNode rear ;              /*尾指针*/
}LiQueue;

b_tree Insert_Tree(b_tree root,int Data)
{
	//声明新节点
	b_tree New;
	b_tree currentnode;

	//初始化新节点
	New = (b_tree)malloc(sizeof(treenode));
	New->data = Data;
	New->left = NULL;
	New->right = NULL;

	if(root == NULL)
		root = New;
	else
	{
		currentnode = root;
		//判断Data位于左子树还是右子树
		while (currentnode != NULL)
		{
			if(Data <= currentnode->data) //左子树
			{
				//判断是否有子树
				if(currentnode->left != NULL)
					currentnode = currentnode->left;
				else
					break;
			}
			else //右子树
				if(currentnode->right != NULL)
					currentnode = currentnode->right;
				else
					break;
		}

		if(Data <= currentnode->data)
			currentnode->left = New;
		else 
			currentnode->right = New;
	}
	return root;
}
//创建二叉树
b_tree Create_Tree(int *array,int len)
{
	assert(array != NULL);
	b_tree root = NULL;
	int i = 0;
	for(; i <len; i++)
		root = Insert_Tree(root,array[i]);
	return root;
}

void print_tree(b_tree root)
{
	if(root == NULL)
		return ;
	else
	{
		printf("%d  ",root->data);
		print_tree(root->left);
		print_tree(root->right);
	}
}

int Depth(b_tree T)
{
	int dep1,dep2;
	int temp;
	if(T==NULL) return(0);
	else
	{
		dep1=Depth(T->left);
		dep2=Depth(T->right);
		temp = max(dep1,dep2);
		return temp+1;
	}
}


void InitQueue(LiQueue &Q)
{
	//构造一个空的Q队列
	Q.front = Q.rear = (p_QNode)malloc(sizeof(Qnode));
	if(!Q.front)
		exit(1);//判断存储是否失败
	Q.front->next = NULL;
}
//入队列操作
void addqueue(LiQueue &Q,b_tree value)
{
	p_QNode new_node;

	new_node = (p_QNode)malloc(sizeof(QNode));
	if(!new_node)
		exit(1);
	new_node->m_treenode = value;
	new_node->next = NULL;

	Q.rear->next = new_node;
	Q.rear = Q.rear->next;
}

//出队列操作
int popqueue(LiQueue &Q)
{
	int temp;
	p_QNode top;
	if(Q.front != NULL)
	{
		temp = Q.front->next->m_treenode->data;
		top = Q.front;
		Q.front = Q.front->next;
		free(top);
	}
	return temp;
}
//广度遍历二叉树 
void layer(b_tree p)
{
	LiQueue root ;
	int temp;

    InitQueue(root);
	addqueue(root,p);
	while(root.front != root.rear)
	{
      //出队列
		temp = popqueue(root);
		printf("%d  ",temp);

		if(root.front->m_treenode->left != NULL)
			addqueue(root,root.front->m_treenode->left);
		if(root.front->m_treenode->right != NULL)
			addqueue(root,root.front->m_treenode->right);
	}
	return;	
}//layer

int main(void)
{
	b_tree root = NULL;
	int hight =0;
	int list[MAX]={0,2,5,9,8,4,7,12,24,3,45,56,21,1,32};
	root = Create_Tree(list,MAX);
	hight = Depth(root);
	printf("hight = %d\n",hight);
	print_tree(root);
	printf("\n广度输出:\n");
	layer(root);
	return 0;
}

输出为：
hight = 8
0  2  1  5  4  3  9  8  7  12  24  21  45  32  56
广度输出:
0  2  1  5  4  9  3  8  12  7  24  21  45  32  56