JavaScript 二叉树实现：定义、递归与非递归遍历详解

JavaScript 实现二叉树定义、遍历及查找的方法详解

本文通过具体实例，详细阐述了在 JavaScript 中定义二叉树、执行遍历操作以及进行节点查找的实现方法，供读者参考学习。

二叉树（binary tree）

在撰写本文之前，有必要先谈谈数据结构与算法系列。该系列涵盖排序、线性表、广义表、树、图等广泛内容。虽然许多一线开发人员在实际工作中可能较少直接应用这些理论，但算法与数据结构被视为程序员的必备基本功。若想突破普通程序员的职业瓶颈，掌握这些核心知识至关重要。此外，编程语言之间原理相通，精通一门语言后，学习其他语言将事半功倍。尽管网上此类资料已非常丰富，但我坚持撰写此系列的目的有二：一是分享知识，二是深化自身理解。近期复习了二叉树，故以此开篇，后续将陆续补充排序、线性表等内容。

二叉树基本概念

二叉树

提到二叉树，读者常会疑惑：它究竟是什么？有何实际用途？为何需要学习？若在学习时未深入思考这些问题，对二叉树的理解往往仅停留在表面。从定义来看，二叉树是一种数据结构，其组织形态类似自然界中的树。官方定义为：一个有限元素的集合，该集合要么为空，要么由一个根元素及两个互不相交的子集组成，这两个子集分别被称为左子树和右子树。至于学习的必要性，随着职业发展深入，其价值自会显现。

二叉树的性质

性质1：二叉树第 i 层上的节点数目最多为 2^(i-1)（i≥1）；性质2：深度为 k 的二叉树至多有 2^k - 1 个结点（k≥1）。性质3：在任意一棵二叉树中，若叶子结点（即度为 0 的结点）的个数为 n0，度为 1 的结点数为 n1，度为 2 的结点数为 n2，则满足 n0 = n2 + 1。

二叉树的存储结构与构建

二叉树包含顺序与链式两种存储方案。顺序存储示例如下： var binaryTree = ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i']; 此结构假设 binaryTree[i] 为节点，则左孩子 leftChild = binaryTree[i*2+1]，右孩子 rightChild = binaryTree[i*2+2]；该方式应用较少。链式存储通过代码详述构建与存储，构建方式分递归（简单）与非递归（稍复杂，附详细注释）。本文以26个英文字母构建二叉树

代码如下:

var charecters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];

在构建二叉树之前，我们需要定义一个节点对象，具体定义如下：（注：关于 JavaScript 的面向对象、原型及语法特点，将在 JavaScript 语言知识点系列中另行介绍）


/*
 *二叉树的节点对象
 */
function Node() {
  this.text = '';      //节点的文本
  this.leftChild = null;  //节点的左孩子引用
  this.rightChild = null;  //节点右孩子引用
}

递归构建二叉树

在定义好二叉树节点后，我们紧接着使用递归方法来构建二叉树。


var charecters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
function buildTree(node, i) {
    var leftIndex = 2*i+1,             //左孩子节点的索引
      rightIndex = 2*i+2;             //右孩子节点的索引
    if(leftIndex < charecters.length) {       //判断索引的长度是否超过了charecters数组的大小
      var childNode = new Node();         //创建一个新的节点对象
      childNode.text = charecters[leftIndex];   //给节点赋值
      node.leftChild = childNode;         //给当前节点node加入左孩子节点
      buildTree(childNode, leftIndex);      //递归创建左孩子
    }
    if(rightIndex < charecters.length) {      //下面注释参照上面的构建左孩子的节点
      var childNode = new Node();
      childNode.text = charecters[rightIndex];
      node.rightChild = childNode;
      buildTree(childNode, rightIndex);
    }
}
//下面构造二叉树
var node = new Node();
node.text = charecters[0];
buildTree(node, 0);  //索引i是从0开始构建

非递归构建二叉树

以下是通过非递归方式构建二叉树的实现。


var root;
function createBinaryTree() {
    var len = charecters.length,        //数组的长度
      index = 0,               //索引从0开始
      nodes = new Array();          //创建一个临时数组，用于存放二叉树节点
    //循环创建二叉树节点存放到数组中
    for (var i = 0 ; i < charecters.length ; i++) {
      var node = new Node();
      node.text = charecters[i];
      nodes.push(node);
    }
    //循环建立二叉树子节点的引用
    while(index < len) {
      var leftIndex = 2*index+1,       //当前节点左孩子索引
        rightIndex = 2*index+2;       //当前节点右孩子索引
      //给当前节点添加左孩子
      nodes[index].leftChild = nodes[leftIndex];
      //给当前节点添加右孩子
      nodes[index].rightChild = nodes[rightIndex];
      index++;
    }
    root = nodes[0];
}

二叉树的三种遍历

成功构建二叉树的链式结构后，接下来进入最基本的遍历操作。遍历主要包括三种基本方式：先序遍历、中序遍历和后序遍历。虽然这三种遍历的递归实现相对简单，但非递归实现则具有一定难度。在实现遍历之前，我们需要先实现栈结构，因为非递归遍历依赖于栈。栈和队列同属数据结构，栈遵循后进先出（LIFO）原则，而队列遵循先进先出（FIFO）原则。

实现栈的对象

下面使用 JavaScript 实现栈对象。


function Stack() {
    var stack = new Array();        //存放栈的数组
    //压栈
    this.push = function(o) {
      stack.push(o);
    };
    //出栈
    this.pop = function() {
      var o = stack[stack.length-1];
      stack.splice(stack.length-1, 1);
      return o;
    };
    //检查栈是否为空
    this.isEmpty = function() {
      if(stack.length <= 0) {
        return true;
      }
      else {
        return false;
      }
    };
}
//使用方式如下
var stack = new Stack();
stack.push(1);    //现在栈中有一个元素
stack.isEmpty();   //false , 栈不为空
alert(stack.pop()); //出栈, 打印1
stack.isEmpty();   //true, 此时栈为空，因为在调用了stack.pop()之后元素出栈了，所以为空

1. 先序遍历

在实现栈对象后，首先进行先序遍历的递归方式实现。


function firstIteration(node) {
    if(node.leftChild) {          //判断当前节点是否有左孩子
      firstIteration(node.leftChild);  //递归左孩子
    }
    if(node.rightChild) {         //判断当前节点是否有右孩子
      firstIteration(node.rightChild);  //递归右孩子
    }
}
//递归遍历二叉树
firstIteration(root);

先序遍历的非递归方式

读者可在 firstIteration() 方法中添加 alert() 函数以验证代码正确性。接下来讨论先序遍历的非递归方式，其核心思想是：先访问根节点，再访问左节点，最后访问右节点。具体过程为：从根节点一直向下访问左孩子节点，直至到达最后一个左孩子节点（将这条路径保存到栈中），然后访问最后一个左孩子的兄弟节点（即右孩子节点），随后回溯到上一层（将栈中元素取出，即出栈），再从该节点（回溯到的上一层节点）继续向下访问左孩子节点……直到栈中元素为空，循环结束。


function notFirstIteration(node) {
    var stack = new Stack(),         //开辟一个新的栈对象
      resultText = '';           //存放非递归遍历之后的字母顺序
    stack.push(root);            //这个root在上面非递归方式构建二叉树的时候已经构建好的
    var node = root;
    resultText += node.text;
    while(!stack.isEmpty()) {
      while(node.leftChild) {       //判断当前节点是否有左孩子节点
        node = node.leftChild;      //取当前节点的左孩子节点
        resultText += node.text;     //访问当前节点
        stack.push(node);        //将当前节点压入栈中
      }
      stack.pop();             //出栈
      node = stack.pop().rightChild;    //访问当前节点的兄弟节点（右孩子节点）
      if(node) {              //当前节点的兄弟节点不为空
        resultText += node.text;     //访问当前节点
        stack.push(node);        //将当前节点压入栈中
      }
      else {                //当前节点的兄弟节点为空
        node = stack.pop();       //在回溯到上一层
      }
    }
}
//非递归先序遍历
notFirstIteration(root);

2. 中序遍历

只要理清思路，实现起来其实并不困难。熟悉一种二叉树的非递归遍历方式后，其他几种便容易掌握，只需照葫芦画瓢即可。以下是中序遍历的递归方式，其思想是：先访问左孩子节点，再访问根节点，最后访问右节点。


var strText = "";
function secondIteration(node) {
    //访问左节点
    if(node.leftChild) {
      if(node.leftChild.leftChild) {
        secondIteration(node.leftChild);
      }
      else {
        strText += node.leftChild.text;
      }
    }
    //访问根节点
    strText += node.text;
    //访问右节点
    if(node.rightChild) {
      if(node.rightChild.leftChild) {
        secondIteration(node.rightChild);
      }
      else {
        strText += node.rightChild.text;
      }
    }
}
secondIteration(root);
alert(strText);

中序遍历的非递归方式

具体思想如下：1. 从根节点一直向下查找左孩子节点，直到找到最后一个左孩子节点（用栈保存此路径，但不访问）；2. 访问最后一个左孩子节点，然后访问根节点（需先弹出栈，即取出上一层节点）；3. 访问当前节点（最后一个左孩子节点）的兄弟节点（右孩子节点）。注意：若兄弟节点是叶节点，则直接访问；若兄弟节点是一棵子树，则不能立即访问，需重复步骤 1、2、3，直到栈为空，循环结束。


function notSecondIteration() {
    var resultText = '',
      stack = new Stack(),
      node = root;
    stack.push(node);
    while(!stack.isEmpty()) {
      //从根节点一直往下找左孩子节点直到最后一个左孩子节点，然后保存在栈中
      while(node.leftChild) {
        node = node.leftChild;
        stack.push(node);
      }
      //弹出栈
      var tempNode = stack.pop();
      //访问临时节点
      resultText += tempNode.text;
      if(tempNode.rightChild) {
        node = tempNode.rightChild;
        stack.push(node);
      }
    }
    alert(resultText);
}

3. 后续遍历

最后介绍一种遍历方式，即二叉树的后续遍历。后续遍历的思想是：先访问左孩子节点，然后访问右孩子节点，最后访问根节点。

后续遍历的递归方式


var strText = '';
function lastIteration(node) {
    //首先访问左孩子节点
    if(node.leftChild) {
      if(node.leftChild.leftChild) {
        lastIteration(node.leftChild);
      }
      else {
        strText += node.leftChild.text;
      }
    }
    //然后再访问右孩子节点
    if(node.rightChild) {
      if(node.rightChild.rightChild) {
        lastIteration(node.rightChild);
      }
      else {
        strText += node.rightChild.text;
      }
    }
    //最后访问根节点
    strText += node.text;
}
//中序递归遍历
lastIteration(root);
alert(strText);

后续非递归遍历

后续非递归遍历的思想如下：1. 从根节点一直向下查找左孩子节点，直到最后一个左孩子节点（将路径保存到栈中，但不访问）；2. 弹出栈访问最后一个左孩子节点；3. 进入最后一个左孩子节点的兄弟节点，若兄弟节点是叶节点则访问它，否则将该节点重复步骤 1、2，直到栈中元素为空；4. 访问根节点。


function notLastIteration() {
    var strText = '',
    stack = new Stack();
    nodo = root;
    stack.push(node);
    while(!stack.isEmpty()) {
      while(node.leftChild) {
        node = node.leftChild;
        stack.push(node);
      }
      //弹出栈
      var tempNode = stack.pop();
      //访问左孩子节点
      strText += tempNode.text;
      //访问右孩子节点
      if(tempNode.rightChild) {
        if(tempNode.rightChild.leftChild || tempNode.rightChild.rightChild) { //判断最后一个左孩子节点的兄弟节点是否为页节点
          stack.push(tempNode.rightChild);
        }
        else {
          strText += tempNode.rightChild.text;
        }
      }
    }
    alert(strText);
}

更多关于 JavaScript 相关内容感兴趣的读者可查看本站专题：《JavaScript 数据结构与算法技巧总结》、《JavaScript 数学运算用法总结》、《JavaScript 排序算法总结》、《JavaScript 遍历算法与技巧总结》、《JavaScript 查找算法技巧总结》及《JavaScript 错误与调试技巧总结》

希望本文所述对大家 JavaScript 程序设计有所帮助。

JavaScript 实现二叉树定义、遍历及查找的方法详解

JavaScript 实现二叉树定义、遍历及查找的方法详解

二叉树基本概念

二叉树的性质

二叉树的存储结构与构建

二叉树的三种遍历

实用工具推荐