JavaScript로 이진 검색 트리 구현-JS 튜토리얼-php.cn

在 JavaScript 中实现二叉搜索树

트리 데이터 구조

트리는 일부 가장자리로 연결된 노드의 모음입니다. 관례적으로 트리의 각 노드는 하위 노드에 대한 일부 데이터와 참조를 저장합니다.

이진 검색 트리

이진 검색 트리는 더 작은 값을 갖는 노드가 왼쪽에 저장되고 더 작은 값을 갖는 노드가 왼쪽에 저장되는 이진 트리입니다. 더 높은 값이 오른쪽에 저장됩니다.

예를 들어, 유효한 BST의 시각적 표현은 -

25 / \ 20 36 / \ / \ 10 22 30 40

로그인 후 복사

입니다. 이제 JavaScript 언어로 자체 이진 검색 트리를 구현해 보겠습니다.

1단계: 노드 클래스

이 클래스는 BST의 각 지점에 존재하는 단일 노드를 나타냅니다. BST 아무것도 오히려 규칙에 따라 배치된 데이터와 하위 참조를 저장하는 노드의 모음입니다. 상술 한 바와 같이.

class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }; };

로그인 후 복사

새 Node 인스턴스를 생성하려면 일부 데이터를 사용하여 이 클래스를 호출할 수 있습니다.

const newNode = new Node(23);

로그인 후 복사

이렇게 하면 데이터가 23으로 설정되고 왼쪽 및 오른쪽 참조가 null인 새 Node 인스턴스가 생성됩니다.

2단계: 이진 검색 트리 클래스:

class BinarySearchTree{ constructor(){ this.root = null; }; };

로그인 후 복사

이것은 이진 검색 트리 클래스를 생성합니다. 새 키워드를 사용하여 호출하여 트리 인스턴스.

이제 기본 사항을 완료했으므로 정의에 설명된 BST 규칙에 따라 올바른 위치에 새 노드를 삽입해 보겠습니다.

3단계: BST에 노드 삽입

class BinarySearchTree{ constructor(){ this.root = null; } insert(data){ var newNode = new Node(data); if(this.root === null){ this.root = newNode; }else{ this.insertNode(this.root, newNode); }; }; insertNode(node, newNode){ if(newNode.data < node.data){ if(node.left === null){ node.left = newNode; }else{ this.insertNode(node.left, newNode); }; } else { if(node.right === null){ node.right = newNode; }else{ this.insertNode(node.right,newNode); }; }; }; };

로그인 후 복사

예제

전체 이진 검색 트리 코드:

class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }; }; class BinarySearchTree{ constructor(){ this.root = null; } insert(data){ var newNode = new Node(data); if(this.root === null){ this.root = newNode; }else{ this.insertNode(this.root, newNode); }; }; insertNode(node, newNode){ if(newNode.data < node.data){ if(node.left === null){ node.left = newNode; }else{ this.insertNode(node.left, newNode); }; } else { if(node.right === null){ node.right = newNode; }else{ this.insertNode(node.right,newNode); }; }; }; }; const BST = new BinarySearchTree(); BST.insert(1); BST.insert(3); BST.insert(2);

로그인 후 복사

위 내용은 JavaScript로 이진 검색 트리 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!