程序员面试100题(算法)之层次遍历二叉树(含二叉树前序创建、层次遍历、前序遍历)

// 程序员面试100题(算法)之层次遍历二叉树(用队列实现)

#include "stdafx.h"
#include <iostream>
#include <deque>

using namespace std;

struct BiTreeNode
{
	BiTreeNode *leftNode;
	BiTreeNode *rightNode;
	int value;
};

BiTreeNode *CreateBiTree(BiTreeNode *&root)
{
	int data = 0;
	cin >> data;

	if(-1 == data)
		return NULL;
	else
	{
		root= (BiTreeNode*)malloc(sizeof(BiTreeNode));
		if(root)
		{
			root->value = data;
			root->leftNode = NULL;
			root->rightNode = NULL;
			CreateBiTree(root->leftNode);
			CreateBiTree(root->rightNode);
		}
		else
		{
			cout << "No space" <<endl;
			return NULL;
		}
	}
	
	return root;
}

void PreTraverseBiTree(BiTreeNode *root)  
{  
   if(root)  
   {  
       cout << root->value << "\t";  
       PreTraverseBiTree(root->leftNode);  
       PreTraverseBiTree(root->rightNode);    
   }  
}  

void LevelTraverse(BiTreeNode *root)
{
	deque<BiTreeNode *> dequeTree;

	if(NULL == root)
		return;

	dequeTree.push_back(root);

	while(!dequeTree.empty())
	{
		BiTreeNode *node = dequeTree.front();
		cout << node->value << "\t";
		dequeTree.pop_front();

		if(node->leftNode)	
			dequeTree.push_back(node->leftNode);

		if(node->rightNode)
			dequeTree.push_back(node->rightNode);
	}

	cout << endl;  
}

int _tmain(int argc, _TCHAR* argv[])
{
	BiTreeNode *root = NULL;

	cout << "Please create the tree with preorder(-1 means NULL):" << endl;  
	CreateBiTree(root);
	cout << "The result of preorder traverse is:" << endl;  
	PreTraverseBiTree(root);
	cout << endl;  
	cout << "The result of level-traverse is:" << endl;  
	LevelTraverse(root);

	return 0;
}