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

本文实例讲述了javascript实现二叉树定义、遍历及查找的方法。分享给大家供大家参考，具体如下：

二叉树（binary tree）

在写这篇文章之前说一下数据结构和算法这个系列，这个系列包含了很多东西，比如啥子排序，线性表，广义表，树，图这些大家都是知道的，但是这些东西我们学了之后工作中能用到的又有多少呢，据我所知绝大部分公司，一线码农，屌丝，程序猿是用不到这些东西，既然这样为啥子我还要强调这个系列呢，本人觉得算法和数据结构是程序的基本功，前提想脱离一线码农，普通程序猿行列，说得通俗一点就是让自己变的更牛逼。其次语言都是想通的，只要是掌握了一门语言学习其他语言就如同顺水推舟，不费一点力气。另外还有一点就是我会一直把这个系列写下去， 虽然网上一搜一大筐，已经写烂了，但是我写作的目的有两个，第一和大家分享， 第二可以让自己更深入的理解。好了，其他的不多说了，最近复习了一下二叉树， 就先写这个，后面会依次的加上排序， 线性表，广义表。。。。等等

二叉树

一说到二叉树我们肯定会问，什么是二叉树，二叉树是个啥子东东，拿来有啥子用嘛，我们为啥子要学习它嘛？ 如果当初你在学习二叉树的时候你没有问过自己这些问题，那么你对它的了解也仅仅也只是了解。那我们现在来说说什么是二叉树，二叉树就是一种数据结构， 它的组织关系就像是自然界中的树一样。官方语言的定义是：是一个有限元素的集合,该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。至于为啥子要学习它，妈妈总是说，孩子，等你长大了就明白了。

二叉树的性质

性质1：二叉树第i层上的节点数目最多为2i-1(i≥1);
性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。
性质3： 在任意-棵二叉树中，若叶子结点（即度为0的结点）的个数为n0，度为1的结点数为n1，度为2的结点数为n2，则no=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];
}

二叉树的三种遍历

好了，现在我们已经成功构建了二叉树的链式结构，在构建了二叉树的链式结构后我们进入二叉树的最基本的遍历了，遍历有三种最基本的遍历，我不说想必大家都知道，先序遍历，中序遍历和后续遍历。虽然这三种遍历递归方式都比较简单，但非递归方式就不是那么容易了，当时我在实现的时候都卡了半天，真的是说起来容易做起来难啊，在实现遍历前我们首先要来实现的是栈，因为在非递归遍历的时候会用到栈，那到底什么是栈呢，这里我就简单介绍下吧，有兴趣的朋友可以去*有权威的定义，栈和队列也是一种数据结构，栈存放数据的时候是先进先出，而队列是先进后出。

实现栈的对象

下面用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步骤, 直到栈中的元素为空，循环结束。3.访问根节点

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程序设计有所帮助。