广度遍历二叉树和深度遍历二叉树算法

 1 //笔试题：广度遍历二叉树、深度遍历二叉树
 2 
 3 #include<iostream>
 4 #include<queue>
 5 #include<stack>
 6 
 7 using namespace std;
 8 
 9 struct node{
10     int id;
11     node(int x=0):id(x),left(nullptr),right(nullptr){}
12     void visit(){cout<<id<<' ';}
13     node* left,* right;
14 };
15 
16 //构造一个二叉树
17 void buildtree(node* root)
18 {
19     if(root->id > 10) return ;
20     root->left = new node(root->id*2 + 1);
21     root->right = new node(root->id*2 + 2);
22     buildtree(root->left);
23     buildtree(root->right);
24 }
25 
26 //广度优先遍历树
27 
28 queue<node*> qnode;
29 
30 void breadthFirstVisit(node* root)
31 {
32     if(root!=nullptr)
33     {
34         qnode.push(root->left);
35         qnode.push(root->right);
36         root->visit();
37         root = qnode.front();
38         qnode.pop();
39         breadthFirstVisit(root);
40     }
41 }
42 
43 //深度优先遍历树
44 
45 stack<node*> snode;
46 
47 void dumpstack()
48 {
49     cout<<"dump:======="<<endl;
50     while(!snode.empty())
51     {
52         node* t=snode.top();
53         if(t!=nullptr)
54             t->visit();
55         snode.pop();
56     }
57     cout<<endl;
58 }
59 void deepFirstVisit(node* root)
60 {
61     if(root!=nullptr)
62     {
63         snode.push(root->right);
64         snode.push(root->left);
65         root->visit();
66         root = snode.top();
67         snode.pop();
68         deepFirstVisit(root);
69         root = snode.top();
70         snode.pop();
71         deepFirstVisit(root);
72     }
73 }
74 int main()
75 {
76     node* tree = new node;
77     buildtree(tree);
78     breadthFirstVisit(tree);
79     cout<<endl;
80     deepFirstVisit(tree);
81     cout<<endl;
82     cin.get();
83 }