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

文章图片
相关概念「树的遍历」指按照一定规则不重复地访问树中所有节点的过程。
「访问」指针对节点的操作，如打印节点的值，更新节点的值等。
本文讨论二叉树的遍历，对节点的访问通过打印节点的值体现出来。
从二叉树的根节点出发，遍历可分为三个环节：

访问节点（打印节点的值）
遍历节点的左子树
遍历节点的右子树

不同环节执行的先后顺序产生了不同的遍历方式。
「前序遍历」指先访问节点，再遍历节点的左子树，最后遍历节点的右子树，按照这种规则不重复地访问树中所有节点的过程。
「中序遍历」指先遍历节点的左子树，再访问节点，最后遍历节点的右子树，按照这种规则不重复地访问树中所有节点的过程。
「后序遍历」指先遍历节点的左子树，再遍历节点的右子树，最后访问节点，按照这种规则不重复地访问树中所有节点的过程。
前序遍历

文章图片
图1 前序遍历
图1展现了前序遍历的整个过程，图中树的结构用代码表示如下

function Node(value) { this.value = https://www.it610.com/article/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 {any} root */ function preOrderTraverse(root){ console.log(root.value) // 访问节点（打印节点的值） ... // 遍历节点的左子树 ... // 遍历节点的右子树 }

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

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

【二叉树的递归遍历（JS实现）】添加递归的终止条件，即访问到叶节点就停止调用函数

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

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