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

[cpp] view plaincopy

1. // 程序员面试100题(算法)之层次遍历二叉树(用队列实现)   
2.   
3. #include "stdafx.h"   
4. #include <iostream>   
5. #include <deque>   
6.   
7. using namespace std;  
8.   
9. struct BiTreeNode  
10. {  
11.     BiTreeNode *leftNode;  
12.     BiTreeNode *rightNode;  
13.     int value;  
14. };  
15.   
16. BiTreeNode *CreateBiTree(BiTreeNode *&root)  
17. {  
18.     int data = 0;  
19.     cin >> data;  
20.   
21.     if(-1 == data)  
22.         return NULL;  
23.     else  
24.     {  
25.         root= (BiTreeNode*)malloc(sizeof(BiTreeNode));  
26.         if(root)  
27.         {  
28.             root->value = data;  
29.             root->leftNode = NULL;  
30.             root->rightNode = NULL;  
31.             CreateBiTree(root->leftNode);  
32.             CreateBiTree(root->rightNode);  
33.         }  
34.         else  
35.         {  
36.             cout << "No space" <<endl;  
37.             return NULL;  
38.         }  
39.     }  
40.       
41.     return root;  
42. }  
43.   
44. void PreTraverseBiTree(BiTreeNode *root)    
45. {    
46.    if(root)    
47.    {    
48.        cout << root->value << "\t";    
49.        PreTraverseBiTree(root->leftNode);    
50.        PreTraverseBiTree(root->rightNode);      
51.    }    
52. }    
53.   
54. void LevelTraverse(BiTreeNode *root)  
55. {  
56.     deque<BiTreeNode *> dequeTree;  
57.   
58.     if(NULL == root)  
59.         return;  
60.   
61.     dequeTree.push_back(root);  
62.   
63.     while(!dequeTree.empty())  
64.     {  
65.         BiTreeNode *node = dequeTree.front();  
66.         cout << node->value << "\t";  
67.         dequeTree.pop_front();  
68.   
69.         if(node->leftNode)     
70.             dequeTree.push_back(node->leftNode);  
71.   
72.         if(node->rightNode)  
73.             dequeTree.push_back(node->rightNode);  
74.     }  
75.   
76.     cout << endl;    
77. }  
78.   
79. int _tmain(int argc, _TCHAR* argv[])  
80. {  
81.     BiTreeNode *root = NULL;  
82.   
83.     cout << "Please create the tree with preorder(-1 means NULL):" << endl;    
84.     CreateBiTree(root);  
85.     cout << "The result of preorder traverse is:" << endl;    
86.     PreTraverseBiTree(root);  
87.     cout << endl;    
88.     cout << "The result of level-traverse is:" << endl;    
89.     LevelTraverse(root);  
90.   
91.     return 0;  
92. }