对于一颗二叉树，深度优先搜索(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}