이진 트리 파트 3 'Breadth-First Search' JavaScript 및 Python

너비 우선 검색

이것은 순회가 선택된 노드(일반적으로 루트)에서 시작하고 순회가 왼쪽에서 오른쪽으로 레이어 방식으로 발생하는 트리를 순회하기 위한 알고리즘입니다.

위의 다이어그램에서 트리를 순회하고 결과를 배열에 저장하면 결과 배열은 [0,1,2,3,4,5,7]가 됩니다.

구현 단계

루트 속성으로 설정된 노드 변수를 생성합니다

데이터를 만들고 대기열 변수를 빈 배열 또는 목록으로 설정합니다.

대기열 끝에 노드 변수를 추가합니다.

대기열이 비어 있지 않은 동안 반복합니다. 각 반복 세트에서 노드를 대기열 배열에서 제거하는 첫 번째 노드를 설정합니다. 노드 값 속성을 데이터 배열에 추가한 다음 대기열에 추가하는 경우 노드에 왼쪽 속성이 있는지 확인합니다.
올바른 속성이 있는지 확인하고 노드에 추가합니다.

JavaScript 코드 구현은 다음과 같습니다BFS.

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

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

    insert(val){
        let newNode = new Node(val);
        if(!this.root){
            this.root = newNode;
        }else{
            let current = this.root;
            while(true){
                if(val < current.val){
                    if(current.left === null){
                        current.left = newNode;
                        return this
                    }else{
                        current = current.left;
                    }
                }else{
                    if(current.right === null){
                        current.right = newNode;
                        return this
                    }else{
                        current = current.right
                    }
                }
            }

        }

    }
    find(val){
        let current  = this.root;
        let found = false;
        while(current && !found){
            if(val < current.val){
                if(current.val === val){
                    found = true;
                    return current;
                }else{
                    current = current.left;
                }
            }else{
                if(current.val === val){
                    found = true;
                    return current;
                }else{
                    current = current.right;
                }
            }
        }
        return 'not found'
    }

    BFS(){
        let data=[];
        let queue=[];
        let node= this.root;
        queue.push(node);
        while(queue.length){
            node = queue.shift();
            data.push(node.val);
            if(node.left)queue.push(node.left);
            if(node.right)queue.push(node.right);
        }
        return data
    }
}

let tree = new BST();
tree.insert(100);
tree.insert(200);
tree.insert(150);
tree.insert(80);
tree.insert(90);
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(180);
tree.insert(190);
console.log(tree,BFS())

파이썬에서 :-

class Node:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root= None

    def insert(self, val):
         newNode = Node(val)
         if self.root == None:
             self.root= newNode
         else:
             current = self.root
             while True:
                 if val< current.val:
                     if current.left == None:
                         current.left = newNode
                         return self
                     else:
                         current= current.left 
                 else:
                     if(current.right == None):
                         current.right = newNode
                         return self
                     else:
                         current = current.right

    def  find(self, val):          
                current= self.root
                found = False
                while current and not found:
                    if val < current.val:
                        current = current.left
                    elif val > current.val:
                        current= current.right
                    else:
                        found = True
                if(not found): return "not found"
                return current
    def bfs(self):
        node = self.root
        data = []
        queue = []
        queue.append(node)
        while len(queue)!= 0:
            node = queue.pop(0)
            data.append(node.val)

            if(node.left): queue.append(node.left)
            if(node.right): queue.append(node.right)

        return data





bst = BST()
bst.insert(100)
bst.insert(200)
bst.insert(150)
bst.insert(175)
bst.insert(160)
bst.insert(180)
bst.insert(75)
bst.insert(50)
bst.insert(65)
bst.insert(40)
bst.insert(55)
bst.insert(20)

print(bst.bfs())

다음으로 depth first search preorder 를 살펴보겠습니다.

Reference

이 문제에 관하여(이진 트리 파트 3 'Breadth-First Search' JavaScript 및 Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/edwardcashmere/binary-tree-part-3-breadth-first-search-javascript-and-python-21k1

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

이진 트리 파트 3 'Breadth-First Search' JavaScript 및 Python

너비 우선 검색

구현 단계

Reference

좋은 웹페이지 즐겨찾기