JavaScriptでは、二叉樹を利用して配列を並べ替えます.

1522 ワード

二叉木と二叉で木を検索します.
二叉ツリーのノードは最大で2つのサブノードしかありません.一つは左側のサブノード、もう一つは右側のサブノードです.二叉探索ツリー(BST)は二叉ツリーの一つであるが、親ノードよりも左側ノードに小さい値を格納し、右側のいくつかの点にノードよりも大きい(または等しい)値を格納することができる.BSTのこのような特性を利用して、配列を並べ替えることができます.
class Node{
    constructor(key){
        this.key = key;
        this.left = null;
        this.right= null;
    }
}
class BinarySearchTree{
    constructor(){
        this.root = null;
        this.length = 0;
    }
    insert(key){
        const node = new Node(key);
        const insertNode = (root, node) => {
            if(root.key>node.key){
                root.left ? insertNode(root.left, node) : root.left = node;
            }else {
                root.right ? insertNode(root.right, node) : root.right = node;
            }
        }
        if(this.root){
            insertNode(this.root, node);
        }else {
            this.root = node;
        }
        this.length++;
        return this;
    }
    //        
    middleOrderTree(){
        var result = [];
        const middleOrder = (root) => {
            root.left && middleOrder(root.left);
            result.push(root.key);
            root.right && middleOrder(root.right);
            return result;
        };
        return middleOrder(this.root);
    }
    arrayToTree(arr){
        for(var i=0;i
二叉の木には、3つのエルゴード方法があります.まず、ノード自体を巡回します.左側のサブノード–右側のサブノード中を巡回します.左側のサブノード–ノード自身>>右側のサブノードの後を巡回します.左側のサブノード–ノード自体を>>右側のサブノード