JavaScript를 사용하여 이진 트리 탐색을 구현하는 방법

이 글에서는 주로 JavaScript에서 이진 트리 정의, 순회 및 검색을 구현하는 방법을 소개합니다. 이진 트리 관련 개념을 예제 형식으로 자세히 분석하고 이진 트리 구성, 순회 및 검색의 일반적인 작동 기술을 설명합니다. JavaScript가 필요한 친구는 다음을 참고할 수 있습니다.

이 기사의 예에서는 JavaScript를 사용하여 이진 트리 정의, 순회 및 검색을 구현하는 방법을 설명합니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

Binary tree

이 기사를 쓰기 전에 일련의 데이터 구조 및 알고리즘에 대해 이야기하겠습니다. 이 시리즈에는 정렬과 같은 많은 내용이 포함되어 있습니다. , 선형 테이블, 일반화된 테이블, 트리, 그래프에 대해서는 누구나 알고 있지만, 이 중에서 배운 후에 작업에 사용할 수 있는 것이 얼마나 됩니까? 제가 아는 한, 대부분의 회사, 일선 코더, 패자 및 프로그래머는 Apes에는 이런 것들이 필요하지 않은데 왜 이 시리즈를 강조해야 합니까? 알고리즘과 데이터 구조는 프로그래밍의 기본 기술이라고 생각합니다. 간단히 말해서, 자신이 더욱 멋져지도록 하세요. 둘째, 언어는 모두 이해됩니다. 하나의 언어를 마스터하면 다른 언어를 배우는 것은 아무런 노력 없이도 흐름을 따라가는 것과 같습니다. 또 하나의 포인트는 이 시리즈를 계속해서 쓸 것이라는 점입니다. 비록 인터넷에서 많이 검색해서 이미 끝냈지만, 제가 이 글을 쓰는 목적은 두 가지입니다. -깊이. 좋아요, 더 이상 할 말이 없습니다. 최근에 이진 트리를 검토했기 때문에 이것을 먼저 작성한 다음 정렬, 선형 테이블, 일반화 테이블을 순서대로 추가하겠습니다. . . . 잠깐

이진 트리

이진 트리에 관해 우리는 확실히 묻습니다. 이진 트리가 무엇인지, 이진 트리가 무엇인지, 어디에 사용되는지, 왜 배워야 하는지? 이진 트리를 배울 때 스스로에게 이런 질문을 하지 않았다면, 이진 트리에 대한 이해는 단지 이해일 뿐입니다. 이제 이진 트리가 무엇인지 이야기해 보겠습니다. 이진 트리는 데이터 구조이고 조직 관계는 본질적으로 트리와 같습니다. 공식 언어의 정의는 다음과 같습니다. 이는 비어 있거나 루트라는 요소와 각각 왼쪽 하위 트리와 오른쪽 하위 트리라고 하는 두 개의 분리된 이진 트리로 구성된 유한 요소 집합입니다. 왜 배워야 하는지에 대해 어머니는 늘 말씀하셨다. “꼬마야, 크면 이해하게 될 거야.”

이진 트리의 속성

속성 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']; 이것은 이진 트리이며, binTree[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];
}

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!