程序员面试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;}