So implementieren Sie die Binärbaumdurchquerung mithilfe von JavaScript

In diesem Artikel wird hauptsächlich die Methode zum Definieren, Durchlaufen und Durchsuchen von Binärbäumen in JavaScript vorgestellt. Er analysiert die zugehörigen Konzepte von Binärbäumen im Detail in Form von Beispielen und den allgemeinen Betriebstechniken zum Erstellen von Binärbäumen sowie zum Durchlaufen und Durchsuchen von Binärbäumen in JavaScript. Freunde, die es benötigen, können es als Referenz verwenden:

Das Beispiel in diesem Artikel beschreibt, wie die Definition, Durchquerung und Suche von Binärbäumen mithilfe von JavaScript implementiert wird. Teilen Sie es wie folgt mit allen als Referenz:

Binärbaum (Binärbaum)

Bevor wir diesen Artikel schreiben, sprechen wir darüber Datenstruktur und Die Algorithmusreihe enthält viele Dinge, wie zum Beispiel Sortierung, lineare Tabellen, verallgemeinerte Tabellen, Bäume und Diagramme, aber wie viele dieser Dinge können wir in unserer Arbeit verwenden, nachdem wir sie gelernt haben? Ich weiß, dass die meisten Unternehmen, First-Line-Programmierer und Programmierer diese Dinge nicht verwenden. Warum sollte ich in diesem Fall den Schwerpunkt auf Algorithmen und Datenstrukturen legen? Von First-Line-Codierern und gewöhnlichen Programmierern geht es, um es einfach auszudrücken, darum, sich selbst zu verbessern. Zweitens werden alle Sprachen verstanden, solange Sie eine Sprache beherrschen, ist das Erlernen anderer Sprachen so, als würden Sie mühelos mit dem Strom schwimmen. Ein weiterer Punkt ist, dass ich diese Serie weiter schreiben werde, obwohl ich viel im Internet gesucht habe und sie bereits fertiggestellt habe. Der erste Zweck besteht darin, sie mit allen zu teilen, und der zweite darin, mich selbst weiterzuentwickeln ausführlich verstehen. Okay, sonst gibt es nicht viel zu sagen, ich habe kürzlich Binärbäume überprüft, also werde ich dies zuerst schreiben und dann nacheinander Sortierung, lineare Tabellen und verallgemeinerte Tabellen hinzufügen. . . . Warten Sie

Binärbaum

Wenn es um Binärbäume geht, werden wir uns auf jeden Fall fragen: Was ist ein Binärbaum, was ist ein Binärbaum, wofür wird er verwendet? Und warum wollen wir es lernen? Wenn Sie sich diese Fragen beim Erlernen von Binärbäumen nicht gestellt haben, ist Ihr Verständnis davon nur ein Verständnis. Lassen Sie uns nun darüber sprechen, was ein Binärbaum ist. Ein Binärbaum ist eine Datenstruktur und seine organisatorische Beziehung ähnelt einem Baum in der Natur. Die offizielle Sprachdefinition lautet: Es handelt sich um eine Menge endlicher Elemente, die entweder leer ist oder aus einem Element namens Wurzel und zwei disjunkten Binärbäumen besteht, die als linker Teilbaum bzw. rechter Teilbaum bezeichnet werden. Warum ich es lernen sollte, sagte meine Mutter immer: „Kind, du wirst es verstehen, wenn du erwachsen bist.“

Eigenschaften von Binärbäumen

Eigenschaft 1: Die Anzahl der Knoten auf der i-ten Ebene eines Binärbaums beträgt höchstens 2i-1 (i≥1) ;
Eigenschaft 2: Tiefe Der Binärbaum für k hat höchstens 2k-1 Knoten (k≥1).
Eigenschaft 3: Wenn in jedem Binärbaum die Anzahl der Blattknoten (d. h. Knoten mit Grad 0) n0 ist, ist die Anzahl der Knoten mit Grad 1 n1 und die Anzahl der Knoten mit Grad 2 ist n2, Dann ist no=n2+1.

Speicherstruktur und Aufbau von Binärbäumen

Es gibt zwei Möglichkeiten, Binärbäume zu speichern, eine ist die sequentielle Speicherung, zum Beispiel:
var binaryTree = ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i']; Dies ist ein Binärbaum, vorausgesetzt, dass BinaryTree[i] ein Knoten eines Binärbaums ist, dann ist sein linker untergeordneter Knoten leftChild = BinaryTree[i*2+1], dann der entsprechende rechte Unterknoten rightChild = BinaryTree[i*2+2]; Im Allgemeinen sequentiell gespeichert. Eine andere Speichermethode ist die Kettenspeicherung. Im Folgenden werde ich den Aufbau und die Speichermethode einer Binärbaumstruktur detailliert beschreiben Dieser ist sehr einfach und der andere ist mit einer nicht rekursiven Methode erstellt. Dieser ist etwas komplizierter als der vorherige, aber keine Sorge, ich werde dem Code detaillierte Kommentare hinzufügen und folgen es Schritt für Schritt. Wir verwenden jetzt 26 englische Buchstaben, um einen Binärbaum zu erstellen

Kopieren Sie den Code Der Code lautet wie folgt:

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'];

bei Bevor wir einen Binärbaum erstellen, verwenden wir ein Knotenobjekt wie folgt: (Hinweis: Ich werde die objektorientierten, prototypischen und grammatikalischen Funktionen von JavaScript in diese Reihe von Wissenspunkten zur JavaScript-Sprache aufnehmen )

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

Rekursiv einen Binärbaum erstellen

Nach dem Erstellen der Binärbaumknoten verwenden wir dann die Rekursion, um den Binärbaum zu erstellen

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开始构建

Nicht-rekursiv einen Binärbaum erstellen

Das Folgende ist eine nicht-rekursive Möglichkeit, einen Binärbaum zu erstellen:

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];
}

Drei Durchquerungen eines Binärbaums

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

实现栈的对象

下面用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插件的环境配置（详细教程）

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Binärbaumdurchquerung mithilfe von JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!