对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。以上面二叉树为例，深度优先搜索的顺序
为：ABDECFG。怎么实现这个顺序呢 ？深度优先搜索二叉树是先访问根结点，然后遍历左子树接着是遍历右子树，因此我们可以利用堆栈的先进后出的特点，
现将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历。
广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，上面二叉树的遍历顺序为：ABCDEFG.
可以利用队列实现广度优先搜索。
下面给出二叉树dfs和bfs的具体代码：
1#include 2#include 3#include 4#include 5usingnamespace std; 6 7struct BitNode 8{ 9int data;10BitNode *left, *right;11BitNode(intx) :data(x), left(0), right(0){}12};1314voidCreate(BitNode *&root)15{16int key;17cin >> key;18if(key == -1)19root = NULL;20else21? ? {22root =new BitNode(key);23Create(root->left);24Create(root->right);25? ? }26}2728voidPreOrderTraversal(BitNode *root)29{30if (root)31? ? {32cout << root->data <<"";33PreOrderTraversal(root->left);34PreOrderTraversal(root->right);35? ? }36}3738//深度优先搜索39//利用栈，现将右子树压栈再将左子树压栈40voidDepthFirstSearch(BitNode *root)41{42stack nodeStack;43? ? nodeStack.push(root);44while(!nodeStack.empty())45? ? {46BitNode *node = nodeStack.top();47cout << node->data <<'';48? ? ? ? nodeStack.pop();49if(node->right)50? ? ? ? {51nodeStack.push(node->right);52? ? ? ? }53if(node->left)54? ? ? ? {55nodeStack.push(node->left);56? ? ? ? }57? ? }58}5960//广度优先搜索61voidBreadthFirstSearch(BitNode *root)62{63queue nodeQueue;64? ? nodeQueue.push(root);65while(!nodeQueue.empty())66? ? {67BitNode *node = nodeQueue.front();68cout << node->data <<'';69? ? ? ? nodeQueue.pop();70if(node->left)71? ? ? ? {72nodeQueue.push(node->left);73? ? ? ? }74if(node->right)75? ? ? ? {76nodeQueue.push(node->right);77? ? ? ? }78? ? }79}8081int? main()82{83BitNode *root = NULL;84? ? Create(root);85//前序遍历86? ? PreOrderTraversal(root);87//深度优先遍历88cout << endl <<"dfs"<< endl;89? ? DepthFirstSearch(root);90//广度优先搜索91cout << endl <<"bfs"<< endl;92? ? BreadthFirstSearch(root);93}
