JavaScript에서 이진 검색 트리 구현 - 가장 간단합니다.

다음은 JavaScript 클래스를 사용한 이진 검색 트리의 가장 간단한 구현입니다.

⚠ 입력이 증가할 때 트리는 균형이 맞지 않습니다 [예 - 1,2,3,4,5 ..... n ]

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

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

    // insert a new node in tree
    insertNode(data) {
        if (this.root === null) {
            this.root = new Node(data);
            return;
        }
        let currentChildren = this.root;
        this.findNodeToInsert(data, currentChildren);
    }
    findNodeToInsert(data, parentNode) {
        if (data > parentNode.data) {
            if (parentNode.right) {
                this.findNodeToInsert(data, parentNode.right);
                return;
            }
            parentNode.right = new Node(data);
        }
        else if (data <= parentNode.data) {
            if (parentNode.left) {
                this.findNodeToInsert(data, parentNode.left);
                return;
            }
            parentNode.left = new Node(data);
        }

    }

    // search a node in tree
    contains(data, currentNode = this.root) {
        // using ? operator to safegurad when we hit the null node 

        if (!this.root) return null;

        if (data === currentNode?.data) {
            console.log('Contains', currentNode)
            return currentNode;
        }

        if (data > currentNode?.data) {
            this.contains(data, currentNode?.right);
        } else if (data < currentNode?.data) {
            this.contains(data, currentNode?.left)
        } else {
            console.log("Node dosen't contain to this tree");
            return null;
        }
    }

    // print binary tree 
    printTreeInOrder(currentNode = this.root) {
        if (!this.root || !currentNode) return;
        this.printTreeInOrder(currentNode?.left)
        console.log(currentNode.data);
       this.printTreeInOrder(currentNode?.right);
    }
    printTreePreOrder(currentNode = this.root) {
        if (!this.root || !currentNode) return;
        console.log(currentNode.data);
        this.printTreeInOrder(currentNode?.left)
       this.printTreeInOrder(currentNode?.right);
    }
    printTreePostOrder(currentNode = this.root) {
        if (!this.root || !currentNode) return;
        this.printTreeInOrder(currentNode?.left)
        this.printTreeInOrder(currentNode?.right);
        console.log(currentNode.data);
    }
}

const Tree = new BinarySearchTree();

Tree.insertNode(2);
Tree.insertNode(5);
Tree.insertNode(10);
Tree.insertNode(10)
Tree.insertNode(20)

// search a node
Tree.contains(2);

console.log("Root",Tree.root);

console.log("Printing tree Inorder [Left, Root, Right]");
// 2,5,10,10,20
Tree.printTreeInOrder()

//@todo - test properly
console.log("Printing tree Preorder [Root, Left, Right]");
Tree.printTreePreOrder();

console.log("Printing tree Postorder [Left, Right, Root]");
Tree.printTreePostOrder();

이진 검색 트리의 매우 간단한 구현입니다. 일부 극단적인 경우가 있을 수 있습니다.

추신 - 나는 내 블로그 표지를 - https://coverview.vercel.app/ [사용자 정의 포함]에서 만듭니다.
👋