JavaScript二叉树遍历

布满荆棘的人生 2022-05-29 08:52 199阅读 0赞

本文主要讲述二叉树的先序、中序、后序递归遍历及非递归遍历，并讲述如何使用JavaScript实现遍历逻辑。  
下面，我们通过一个例子来回顾一下先序、中序、后序遍历：

![二叉树][Image 1]

> 上面二叉树先序、中序、后序遍历结果分别为：  
> 先序：ABCDEF  
> 中序：CBDAEF  
> 后序：CDBFEA

从上例可以总结出先序、中序、后序的规则：  
**先序:**遍历到一个节点时，输出节点的值，然后遍历此节点的左子树，接着遍历此节点的右子树。  
**中序：**遍历到一个节点时，先暂时存下来此节点，然后遍历此节点的左子树，然后输出节点的值，接着遍历此节点的右子树。  
**后序：**遍历到一个节点时，先暂时存下来此节点，然后遍历此节点的左子树，接着遍历此节点的右子树，最后输出此节点的值。

--------------------

## JavaScript代码实现 ##

--------------------

开始讲述代码实现之前，先给出树节点构造函数：

function TreeNode(x) { 
        this.val = x;
        this.left = null;
        this.right = null;
    }

### 先序遍历 ###

--------------------

#### 先序遍历递归实现 ####

function prefaceTraverse(root){
        if(root!==null){
            console.log(root.val);
            prefaceTraverse(root.left);
            prefaceTraverse(root.right);
        }
    }

#### 先序遍历非递归实现 ####

function prefaceTraverse(root){ 
        var stack = [];//定义一个暂时存储节点的栈
        var node = root;//定义一个游动节点
        //只要节点不为空，或者存储节点的栈不为空，就需要一直执行
        while(node!==null || stack.length >0){
            //只要节点不为空，根据先序遍历特点，一直向左走
            while(node !== null){
                console.log(node.val);//打印节点值
                stack.push(node);//把已经遍历打印的节点入栈
                node = node.left;//向左子树走
            }
            //上述循环跳出，说明，向左走走到叶节点了，若栈不为空
            //出栈一个节点，然后把node赋值为这个节点的右子树
            //接着就会继续从上述第一层循环开始遍历node的右子树
            if(stack.length >0){
                node = stack.pop();
                node = node.right;
            }
        }
    }

### 中序遍历 ###

--------------------

#### 中序遍历递归实现 ####

function inOrderTraverse(root){
        if(root!==null){
            inOrderTraverse(root.left);
            console.log(root.val);
            inOrderTraverse(root.right);
        }
    }

#### 中序遍历非递归实现 ####

function inOrderTraverse(root){ 
        var stack = [];//定义一个暂时存储节点的栈
        var node = root;//定义一个游动节点
        //只要节点不为空，或者存储节点的栈不为空，就需要一直执行
        while(node!==null || stack.length >0){
            //只要节点不为空，根据中序遍历特点，一直向左走
            while(node !== null){
                stack.push(node);//把节点入栈
                node = node.left;//向左子树走
            }
            //上述循环跳出，说明，向左走走到叶节点了，若栈不为空
            //出栈一个节点，然后打印出节点值
            //然后把node赋值为这个节点的右子树
            //接着就会继续从上述第一层循环开始遍历node的右子树
            if(stack.length >0){
                node = stack.pop();
                console.log(node.val);//打印节点值
                node = node.right;
            }
        }
    }

### 后序遍历 ###

--------------------

#### 后序遍历递归实现 ####

function postOrderTraverse(root){
        if(root!==null){
            postOrderTraverse(root.left);
            postOrderTraverse(root.right);
            console.log(root.val);
        }
    }

#### 后序遍历非递归实现 ####

> 后序遍历思想：  
> 后序遍历和中序遍历不太一样，后序遍历判断当前节点是否可输出的条件是：当前节点的右子树是否遍历完成。  
> 这个时候就需要我们增加一个变量lastNode去表标识上一个遍历的节点，若当前节点的右子树等于lastNode，说明就可输出当前节点。

function postOrderTraverse(root){ 
        var stack = [];//定义一个暂时存储节点的栈
        var node = root;//定义一个游动节点
        var lastNode = root;//标识上次遍历输出的节点
        //只要节点不为空，或者存储节点的栈不为空，就需要一直执行
        while(node!==null || stack.length >0){
            //只要节点不为空，根据先序遍历特点，一直向左走
            while(node !== null){
                stack.push(node);//把节点入栈
                node = node.left;//向左子树走
            }
    
            //出栈栈顶节点，若此节点的右子树已经遍历，或者为空
            //可以直接输出此节点
            node = stack[stack.length-1];
            if(node.right===null || node.right === lastNode){
                console.log(node.val);//打印节点值
                stack.pop();
                lastNode = node;
                node =null;
            }
            else{
                //继续遍历右子树
                node = node.right;
            }
        }
    }

[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

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

相关阅读

相关二叉树二叉树遍历通过二叉树遍历求得二叉树

什么是二叉树 > > 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且

偏执的太偏执、/ 2022年12月04日 01:08/ 0 赞/ 321 阅读

相关遍历二叉树

1. 二叉树的遍历遍历定义 ——顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的信息等。

迈不过友情╰/ 2022年08月22日 14:26/ 0 赞/ 456 阅读

相关遍历二叉树

遍历二叉树二叉树是由3个基本单元组成的：根结点、左子树和右子树。若限定先左后右的顺序，则遍历二叉树只有三种情况分别称为先（根）序遍历、中（根）序遍历和后（根）序遍

比眉伴天荒/ 2022年06月08日 00:48/ 0 赞/ 320 阅读

相关遍历二叉树

遍历二叉树今天我们学习了二叉树，现在我就基于二叉树的递归定义来说一说遍历二叉树的三种方法：先序、中序和后序。根据二叉树的递归定义可知，二叉树是由3个基本单元组成：根结点

傷城~/ 2022年06月05日 08:11/ 0 赞/ 371 阅读

相关二叉树遍历

include<iostream> include<queue> using namespace std; //二叉树结点

╰+攻爆jí腚メ/ 2022年06月04日 05:35/ 0 赞/ 318 阅读

相关 JavaScript二叉树遍历

本文主要讲述二叉树的先序、中序、后序递归遍历及非递归遍历，并讲述如何使用JavaScript实现遍历逻辑。下面，我们通过一个例子来回顾一下先序、中序、后序遍历：

布满荆棘的人生/ 2022年05月29日 08:52/ 0 赞/ 200 阅读

相关二叉树遍历

前序遍历（左中右）ABDGHCEIF ![前序遍历][70] 中序遍历（左根右）GDHBAEICF![中序遍历][70 1] 后序遍历（左右根）GHDBIEFCA![

Bertha 。/ 2022年05月11日 13:48/ 0 赞/ 375 阅读

相关二叉树遍历

二叉树是数据结构中很重要的一个章节，很多同学反应很难，今天我就把我平时的经验给大家讲解一下，今天讲一下二叉树的遍历工具/原料 ● 数据结构知识 ● 了解树的定义

爱被打了一巴掌/ 2022年05月10日 03:08/ 0 赞/ 332 阅读

相关二叉树遍历

//节点定义 template <class T> struct binaryTreeNode { T

比眉伴天荒/ 2022年03月19日 14:08/ 0 赞/ 372 阅读

相关遍历二叉树

用递归的方法实现前序遍历，中序遍历，后序遍历：用递归的方法遍历的时候，其实每个节点都遍历了三遍，根据打印时间的不同，即可实现前序中序及后续，这就是三个遍历代码一样而打印顺序

浅浅的花香味﹌/ 2021年11月01日 15:28/ 0 赞/ 480 阅读