二叉树遍历——深度优先(DFS)与广度优先(BFS)

我不是女神ヾ 2022-05-16 12:12 396阅读 0赞

二叉树的深度优先遍历(DFS)与广度优先遍历(BFS)

深度优先遍历:从根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为止。然后回溯到前一个节点,进行右子树节点的遍历,直到遍历完所有可达节点为止。

广度优先遍历:从根节点出发,在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

DFS实现:

数据结构:栈

父节点入栈,父节点出栈,先右子节点入栈,后左子节点入栈。递归遍历全部节点即可

BFS实现:

数据结构:队列

父节点入队,父节点出队列,先左子节点入队,后右子节点入队。递归遍历全部节点即可

  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4. #include <Stack>
  5. #include <Queue>
  6. using namespace std;
  7. typedef struct Node {
  8. char data;
  9. struct Node *lchild;
  10. struct Node *rchild;
  11. } *Tree;
  12. //Tree 是一个node指针的类型定义
  13. int index = 0; //全局索引变量
  14. //二叉树构造器,按先序遍历顺序构造二叉树
  15. //无左子树或右子树用'#'表示
  16. void treeNodeConstructor(Tree &root, char data[]){
  17. char e = data[index++];
  18. if(e == '#'){
  19. root = NULL;
  20. }else{
  21. root = (Node *)malloc(sizeof(Node));
  22. root->data = e;
  23. treeNodeConstructor(root->lchild, data); //递归构建左子树
  24. treeNodeConstructor(root->rchild, data); //递归构建右子树
  25. }
  26. }
  27. //深度优先遍历
  28. void depthFirstSearch(Tree root){
  29. stack<Node *> nodeStack; //使用C++的STL标准模板库
  30. nodeStack.push(root);
  31. Node *node;
  32. while(!nodeStack.empty()){
  33. node = nodeStack.top();
  34. cout<<node->data;//遍历根结点
  35. nodeStack.pop();
  36. if(node->rchild){
  37. nodeStack.push(node->rchild); //先将右子树压栈
  38. }
  39. if(node->lchild){
  40. nodeStack.push(node->lchild); //再将左子树压栈
  41. }
  42. }
  43. }
  44. //广度优先遍历
  45. void breadthFirstSearch(Tree root){
  46. queue<Node *> nodeQueue; //使用C++的STL标准模板库
  47. nodeQueue.push(root);
  48. Node *node;
  49. while(!nodeQueue.empty()){
  50. node = nodeQueue.front();
  51. nodeQueue.pop();
  52. cout<<node->data;//遍历根结点
  53. if(node->lchild){
  54. nodeQueue.push(node->lchild); //先将左子树入队
  55. }
  56. if(node->rchild){
  57. nodeQueue.push(node->rchild); //再将右子树入队
  58. }
  59. }
  60. }
  61. int main() {
  62. //上图所示的二叉树先序遍历序列,其中用'#'表示结点无左子树或无右子树
  63. char data[15] = {'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#'};
  64. Tree tree;
  65. treeNodeConstructor(tree, data);
  66. printf("深度优先遍历二叉树结果: ");
  67. depthFirstSearch(tree);
  68. printf("\n\n广度优先遍历二叉树结果: ");
  69. breadthFirstSearch(tree);
  70. return 0;
  71. }

深度优先搜索习题

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.(求给定二叉树的最小深度)

思路:深度优先搜索

递归,若为空树返回0;

若左子树为空,则返回右子树的最小深度+1;(加1是因为要加上根这一层,下同)

若右子树为空,则返回左子树的最小深度+1;

若左右子树均不为空,则取左、右子树最小深度的较小值,+1;

虽然没有用到栈的数据结构,但本质上思想就是深度优先搜索。

参考代码:

  1. class Solution {
  2. public:
  3. int run(TreeNode *root)
  4. {
  5. if(root == nullptr) return 0;
  6. if(root->left == nullptr) // 若左子树为空,则返回右子树的最小深度+1
  7. {
  8. return run(root->right)+1;
  9. }
  10. if(root->right == nullptr) // 若右子树为空,则返回左子树的最小深度+1
  11. {
  12. return run(root->left)+1;
  13. }
  14. // 左右子树都不为空时,取较小值
  15. int leftDepth = run(root->left);
  16. int rightDepth = run(root->right);
  17. return min(leftDepth+1,rightDepth+1);
  18. }
  19. };

#

广度优先搜索习题

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

  1. /*
  2. struct TreeNode {
  3. int val;
  4. struct TreeNode *left;
  5. struct TreeNode *right;
  6. TreeNode(int x) :
  7. val(x), left(NULL), right(NULL) {
  8. }
  9. };*/
  10. class Solution {
  11. public:
  12. vector<int> PrintFromTopToBottom(TreeNode* root) {
  13. vector<int> res;
  14. if(root==NULL)
  15. return res;
  16. queue<TreeNode*> q;
  17. q.push(root);
  18. while(!q.empty()){
  19. res.push_back(q.front()->val);
  20. if(q.front()->left!=NULL)
  21. q.push(q.front()->left);
  22. if(q.front()->right!=NULL)
  23. q.push(q.front()->right);
  24. q.pop();
  25. }
  26. return res;
  27. }
  28. };

发表评论

表情:
评论列表 (有 0 条评论,396人围观)

还没有评论,来说两句吧...

相关阅读