二叉树的递归遍历（JS实现）

ethernet 发布于2019-08-21 17:07 / 2772人阅读

摘要：本文讨论二叉树的遍历，对节点的访问通过打印节点的值体现出来。从二叉树的根节点出发，遍历可分为三个环节访问节点打印节点的值遍历节点的左子树遍历节点的右子树不同环节执行的先后顺序产生了不同的遍历方式。至于二叉树的非递归遍历，且听下回分解。

相关概念

「树的遍历」指按照一定规则不重复地访问树中所有节点的过程。
「访问」指针对节点的操作，如打印节点的值，更新节点的值等。

本文讨论二叉树的遍历，对节点的访问通过打印节点的值体现出来。
从二叉树的根节点出发，遍历可分为三个环节：

访问节点（打印节点的值）

遍历节点的左子树

遍历节点的右子树

不同环节执行的先后顺序产生了不同的遍历方式。

「前序遍历」指先访问节点，再遍历节点的左子树，最后遍历节点的右子树，按照这种规则不重复地访问树中所有节点的过程。
「中序遍历」指先遍历节点的左子树，再访问节点，最后遍历节点的右子树，按照这种规则不重复地访问树中所有节点的过程。
「后序遍历」指先遍历节点的左子树，再遍历节点的右子树，最后访问节点，按照这种规则不重复地访问树中所有节点的过程。

前序遍历

上图展现了前序遍历的整个过程，其中树的结构用代码表示如下（存储为变量root)

function Node(value) {
  this.value = value
  this.left = null
  this.right = null
}

root {
  value: "A",
  left: {
      value: "B",
      left: {
          value: "D",
          left: {
              value: "H",
              left: null,
              right: null
          },
          right: {
              value: "I",
              left: null,
              right: null
          }
      },
      right: {
          value: "E",
          left: null,
          right: null
      }
  },
  right: {
      value: "C",
      left: {
          value: "F",
          left: null,
          right: null
      },
      right: {
          value: "G",
          left: null,
          right: null
      }
  }
}

设计一个函数，用于遍历二叉树，传入的参数是二叉树的根节点，函数会先访问节点（打印节点的值），再遍历节点的左子树，最后遍历节点的右子树。
上述代码翻译成代码片段就是

/**
 * 函数的作用是遍历二叉树
 * 传入的参数是二叉树的根节点
 * @param {object} root 
 */
function preOrderTraverse(root){
  console.log(root.value) // 访问节点（打印节点的值）
  ... // 遍历节点的左子树
  ... // 遍历节点的右子树
}

... 处应该是遍历节点的左，右子二叉树的代码。遍历二叉树不正是这个函数的作用吗？故想到了递归

function preOrderTraverse(root){
  console.log(root.value) // 访问节点（打印节点的值）
  preOrderTraverse(root.left) // 遍历节点的左子树
  preOrderTraverse(root.right) // 遍历节点的右子树
}

添加递归的终止条件，即访问到叶节点就停止调用函数

const preOrderTraverse = root => {
  console.log(root.value) // 访问节点（打印节点的值）
  root.left && preOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
  root.right && preOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
}
preOrderTraverse(root)
// A B D H I E C F G

举一反三

中序遍历

const inOrderTraverse = root => {
  root.left && inOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
  console.log(root.value) // 访问节点（打印节点的值）
  root.right && inOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
}
inOrderTraverse(root)
// H D I B E A F C G

后序遍历

const postOrderTraverse = root => {
  root.left && postOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
  root.right && postOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
  console.log(root.value) // 访问节点（打印节点的值）
}
postOrderTraverse(root)
// H I D E B F G C A

非递归遍历

随着被调用次数的增加，递归函数会线性地增加栈空间的使用。
至于二叉树的非递归遍历，且听下回分解。

私有云 GPU服务器二叉树的遍历非递归二叉树遍历 JS二叉树遍历二叉树的存储

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/89148.html

js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。树的简介栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...

Yuanf 2019-08-23 11:38 评论0 收藏0
JS递归与二叉树的遍历

摘要：貌似大部分语言中的递归都差不多，之所以在标题加是因为搜了下后感觉网上用来描述这概念的不多，简单地说递归就是函数调用自己的过程。貌似大部分语言中的递归都差不多，之所以在标题加JS是因为搜了下后感觉网上用js来描述这概念的不多，简单地说递归就是函数调用自己的过程。下面的栗子可以很直观地展示递归的执行过程： function rec(x){ if(x!==1){ console....

church 2019-08-21 10:48 评论0 收藏0
【数据结构初阶】第八篇——二叉树的链式结构（二叉树的前、中和后序遍历+层序遍历+链式结构的实现+相关

摘要：代码实现如下二叉树的创建与销毁二叉树的创建问题通过前序遍历的数组给定一串字符串，代表的是空树，其他的都是节点。 ⭐️本篇博客我要来和大家一起聊一聊数据结构中的二...

BigNerdCoding 2021-11-18 10:02 评论0 收藏0
【数据结构初阶之二叉树】：二叉树相关的性质和经典的习题（用C语言实现，附图详解）

摘要：当集合为空时，称该二叉树为空二叉树。也就是说，如果一个二叉树的层数为，且结点总数是，则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。 ...

Martin91 2021-11-24 09:39 评论0 收藏0
Java数据结构与算法——二叉树及操作(包括二叉树遍历)

摘要：本篇主要介绍二叉树的概念二叉树的表示二叉树的操作三种遍历方式实现求二叉树的子树求节点的父节点二叉树高度，可能是考试中的，也可能是面试中的。通常二叉树的遍历根据根节点的遍历次序分为先根遍历中根遍历后根遍历。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇主要介绍二叉树的概念、二叉树的表示、二叉树的操作（三种遍历...

muddyway 2019-08-16 11:15 评论0 收藏0