二叉树(二)——递归遍历

我不是女神ヾ 2022-07-16 10:30 274阅读 0赞

1、前序遍历
前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。

  1. //前序遍历
  2. void preorder(TreeNode *root, vector<int> &path)
  3. {
  4.     if(root != NULL)
  5.     {
  6.         path.push_back(root->val);
  7.         preorder(root->left, path);
  8.         preorder(root->right, path);
  9.     }
  10. }

2、中序遍历
中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。

  1. //中序遍历
  2. void inorder(TreeNode *root, vector<int> &path)
  3. {
  4.     if(root != NULL)
  5.     {
  6.         inorder(root->left, path);
  7.         path.push_back(root->val);
  8.         inorder(root->right, path);
  9.     }
  10. }

3、后序遍历
后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。

  1. //后续遍历
  2. void postorder(TreeNode *root, vector<int> &path)
  3. {
  4.     if(root != NULL)
  5.     {
  6.         postorder(root->left, path);
  7.         postorder(root->right, path);
  8.         path.push_back(root->val);
  9.     }
  10. }

由以上可见，二叉树的递归遍历，风格统一，逻辑和代码都很简单。如何实现二叉树的非递归遍历，请看我的下片博文：二叉树(三)——非递归遍历

发表评论

表情：
评论列表 （有 0 条评论，274人围观）

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

相关阅读

    相关 递归遍历二叉树

    网上的递归遍历代码很多，这里就不赘述了，说一下思考的角度： 1. 把每一个棵子树都看成是独立的树； 2. 每一个节点都会把递归的代码重新执行一次； 3. 想象压栈的过程

    今天药忘吃喽~今天药忘吃喽~/ 0 赞/ 119 阅读

    相关 二叉树遍历（递归）

    二叉树又称为红黑树，是一种常用的数据结构，而二叉树的遍历则是一种非常基本的操作。遍历二叉树的方式有两大类：递归和非递归。递归方式算法较为简便，并且更便于理解，非递归方式则需要对

    末蓝、末蓝、/ 0 赞/ 283 阅读

    相关 二叉树遍历（递归版）

    问题描述： 以一定的方式输入数据（本文是以先序遍历的方式输入），程序根据数据进行解析，创建二叉树，然后对二叉树进行操作，主要操作包括以下几种： 1. 求二叉树的高度 2

    男娘i男娘i/ 0 赞/ 289 阅读