JavaScript を使用してバイナリ ツリー トラバーサルを実装する方法

この記事では、主に JavaScript でバイナリ ツリーの定義、トラバース、および検索を実装する方法を紹介し、例とバイナリ ツリーの構築、バイナリ ツリーのトラバースおよび検索の一般的な操作テクニックの形でバイナリ ツリーの関連概念を詳細に分析します。 JavaScript が必要な場合は、以下を参照してください。この記事の例では、JavaScript を使用してバイナリ ツリーの定義、走査、検索を実装する方法について説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

バイナリツリー この記事を書く前に、一連のデータ構造とアルゴリズムについて説明します。このシリーズにはソートなどの多くの内容が含まれています。 、線形 テーブル、一般化されたテーブル、ツリー、グラフについては誰もが知っていますが、私が知る限り、ほとんどの企業、第一線のプログラマー、敗者、およびプログラマーは、これらを学習した後に仕事で使用できるものがどれだけあるでしょうか?類人猿にはこれらのことは必要ありませんが、なぜこのシリーズを強調する必要があるのでしょうか? 前提として、アルゴリズムとデータ構造は、第一線のプログラマーや一般的なプログラマーのランクから脱却するためです。シンプルに、自分自身をもっと素晴らしいものにしましょう。第二に、言語はすべて理解できます。1 つの言語をマスターしていれば、他の言語を学習するのは、何の努力も必要ありません。もう一つのポイントは、このシリーズを書き続けることです。ネットでいろいろ調べてすでに書き終えていますが、書く目的は 2 つあります。1 つは、それを皆さんに共有すること、そして 2 つ目は、自分自身をより理解してもらうことです。 -深さがわかります。さて、他に言うことはあまりありません。最近バイナリ ツリーをレビューしたので、これを最初に書き、次にソート、線形テーブル、および一般化テーブルを順番に追加します。 。 。 。待ってください

バイナリーツリー

バイナリーツリーのことになると、必ず疑問に思うでしょう、バイナリーツリーとは何ですか、バイナリーツリーとは何ですか、何に使用されますか、なぜそれを学ぶ必要があるのですか？ 二分木を学習するときにこれらの質問を自問しなかった場合、二分木に対する理解は単なる理解にすぎません。ここで、バイナリ ツリーとは何かについて説明します。バイナリ ツリーはデータ構造であり、その組織関係は自然界のツリーに似ています。公式言語での定義は次のとおりです。これは、空であるか、ルートと呼ばれる要素と、それぞれ左サブツリーおよび右サブツリーと呼ばれる 2 つの素のバイナリ ツリーで構成される有限要素のセットです。なぜそれを学ばなければならないかについて、私の母はいつも「子供よ、大人になれば分かるよ」と言いました。

バイナリ ツリーのプロパティ

プロパティ 1: バイナリ ツリーの i 番目のレベルのノードの数は最大 2i-1 (i≥1);

プロパティ 2: 深さ k のバイナリ ツリーは、最大 2k-1 ノード (k ≥1)。

性質 3: 任意の二分木において、葉ノード (次数 0 のノード) の数が n0、次数 1 のノードの数が n1、次数 2 のノードの数が n2 の場合、 no =n2 です。 +1。

バイナリツリーのストレージ構造と構築

バイナリツリーを保存するには2つの方法があり、1つは次のような逐次ストレージです:

これはバイナリツリーです。binaryTree[i]がバイナリツリーのノードであると仮定します。次に、その左側の子ノード leftChild = binaryTree[i*2+1] 次に、対応する右側の子ノード rightChild = binaryTree[i*2+2]; 一般に、この順次ストレージの構造は、あまり使用されません。別のストレージ方法はチェーンです。ストレージ、以下ではバイナリ ツリー構造の構築と格納方法を詳しく説明します。1 つは非常に単純な再帰的構築で、もう 1 つは非再帰的構築です。これは比較的前のものよりも少し複雑ですが、心配しないでください。コードに詳細なコメントを追加し、ステップごとに説明します。 26 個の英字を使用してバイナリ ツリーを構築します
var binaryTree = ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i'];

コードをコピーします

コードは次のとおりです: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];
}

3二分木の走査

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

实现栈的对象

下面用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);
}

上面是我整理给大家的，希望今后会对大家有帮助。

相关文章：

如何使用vuex实现菜单管理

详细解读Angular5.1新功能

使用nodejs如何实现gulp打包

在vue2中通过keep-alive如何使用

在webpack中有关于jquery插件的环境配置（详细教程）

以上がJavaScript を使用してバイナリ ツリー トラバーサルを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。