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