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); }
上面是我整理给大家的,希望今后会对大家有帮助。
相关文章:
在webpack中有关于jquery插件的环境配置(详细教程)
위 내용은 JavaScript를 사용하여 이진 트리 탐색을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

Video Face Swap
완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

하드 드라이브 일련 번호와 MAC 주소는 컴퓨터 하드웨어의 중요한 식별자이며 컴퓨터 시스템을 관리하고 유지하는 데 매우 유용합니다. 이 문서에서는 하드 디스크 일련 번호와 MAC 주소를 찾는 방법을 소개합니다. 1. 하드 드라이브 일련 번호를 찾으십시오. 하드 드라이브 일련 번호는 하드 드라이브 제조업체가 하드 드라이브를 식별하고 추적하는 데 사용하는 고유 식별자입니다. 운영 체제에 따라 하드 드라이브 일련 번호를 찾는 방법이 약간 다릅니다. Windows: 명령 프롬프트를 열고(시작 메뉴에서 "cmd" 검색) 다음 명령을 입력하고 Enter를 누릅니다. wmicdisk

Apple의 나의 찾기 앱을 사용하면 iPhone이나 기타 기기의 위치를 찾아 분실하거나 잊어버리는 일을 방지할 수 있습니다. 나의 찾기는 장치를 추적하는 데 유용한 도구이지만 개인 정보 보호 문제가 우려되거나 배터리 소모를 원하지 않는 경우 또는 기타 이유로 비활성화할 수 있습니다. 다행히도 iPhone에서 나의 찾기를 끄는 방법에는 여러 가지가 있으며, 이 기사에서는 이에 대해 모두 설명하겠습니다. iPhone에서 나의 찾기를 끄는 방법 [4가지 방법] 네 가지 방법으로 iPhone에서 나의 찾기를 끌 수 있습니다. 방법 1을 사용하여 찾기를 끈 경우 비활성화하려는 장치에서 이 작업을 수행할 수 있습니다. 방법 2, 3, 4를 진행하려면 Find Finder를 끄려는 iPhone의 전원을 끄거나

MySQL의 복합 기본 키는 테이블의 여러 필드로 구성된 기본 키를 말하며 각 레코드를 고유하게 식별하는 데 사용됩니다. 단일 기본 키와 달리 복합 기본 키는 여러 필드의 값을 결합하여 형성됩니다. 테이블을 생성할 때 여러 필드를 기본 키로 지정하여 복합 기본 키를 정의할 수 있습니다. 복합 기본 키의 정의와 기능을 보여주기 위해 먼저 id, 사용자 이름, 이메일이라는 세 가지 필드가 포함된 users라는 테이블을 만듭니다. 여기서 id는 자동으로 증가하는 기본 키이고 user입니다.

"Discovering Discuz: 정의, 기능 및 코드 예제" 인터넷의 급속한 발전과 함께 커뮤니티 포럼은 사람들이 정보를 얻고 의견을 교환하는 중요한 플랫폼이 되었습니다. 많은 커뮤니티 포럼 시스템 중에서 중국의 잘 알려진 오픈 소스 포럼 소프트웨어인 Discuz는 대다수의 웹 사이트 개발자 및 관리자가 선호합니다. 그렇다면 Discuz는 무엇입니까? 어떤 기능이 있으며 웹사이트에 어떻게 도움이 됩니까? 이 기사에서는 Discuz를 자세히 소개하고 독자가 이에 대해 더 자세히 알아볼 수 있도록 구체적인 코드 예제를 첨부합니다.

Java는 강력한 파일 처리 기능을 갖춘 널리 사용되는 프로그래밍 언어입니다. Java에서는 폴더를 탐색하고 모든 파일 이름을 가져오는 것이 일반적인 작업이므로 특정 디렉터리에서 파일을 빠르게 찾고 처리하는 데 도움이 될 수 있습니다. 이 기사에서는 폴더를 탐색하여 모든 파일 이름을 Java로 가져오는 방법을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다. 1. 재귀적 방법을 사용하여 폴더를 순회할 수 있습니다. 재귀적 방법은 폴더를 효과적으로 순회할 수 있는 자체 호출 방법입니다.

JavaScript 튜토리얼: HTTP 상태 코드를 얻는 방법, 특정 코드 예제가 필요합니다. 서문: 웹 개발에서는 서버와의 데이터 상호 작용이 종종 포함됩니다. 서버와 통신할 때 반환된 HTTP 상태 코드를 가져와서 작업의 성공 여부를 확인하고 다양한 상태 코드에 따라 해당 처리를 수행해야 하는 경우가 많습니다. 이 기사에서는 JavaScript를 사용하여 HTTP 상태 코드를 얻는 방법과 몇 가지 실용적인 코드 예제를 제공합니다. XMLHttpRequest 사용

컴퓨터 하드 드라이브의 일련번호를 확인하는 방법 컴퓨터 기술의 발달로 컴퓨터 하드 드라이브는 우리 삶에 없어서는 안 될 부분이 되었습니다. 중요한 파일을 저장하거나 운영 체제 및 소프트웨어를 설치하는 등의 작업을 완료하려면 하드 디스크에 의존해야 합니다. 하드 드라이브의 일련 번호와 같은 컴퓨터 하드 드라이브에 대한 몇 가지 기본 정보를 이해하면 컴퓨터 시스템을 더 잘 관리하고 유지하는 데 도움이 될 수 있습니다. 그렇다면 컴퓨터 하드디스크의 일련번호를 확인하는 방법은 무엇일까요? 이 기사에서는 몇 가지 일반적인 방법을 소개합니다. 방법 1: Windows 시스템과 함께 제공되는 명령줄 도구 사용 Windows 시스템

PHP 인터페이스 소개 및 정의 방법 PHP는 웹 개발에 널리 사용되는 오픈 소스 스크립팅 언어입니다. 유연하고 간단하며 강력합니다. PHP에서 인터페이스는 여러 클래스 간의 공통 메서드를 정의하여 다형성을 달성하고 코드를 보다 유연하고 재사용 가능하게 만드는 도구입니다. 이 기사에서는 PHP 인터페이스의 개념과 이를 정의하는 방법을 소개하고 사용법을 보여주는 특정 코드 예제를 제공합니다. 1. PHP 인터페이스 개념 인터페이스는 클래스 애플리케이션을 정의하는 객체 지향 프로그래밍에서 중요한 역할을 합니다.
