JavaScriptでは、二叉樹を利用して配列を並べ替えます.
1522 ワード
二叉木と二叉で木を検索します.
二叉ツリーのノードは最大で2つのサブノードしかありません.一つは左側のサブノード、もう一つは右側のサブノードです.二叉探索ツリー(BST)は二叉ツリーの一つであるが、親ノードよりも左側ノードに小さい値を格納し、右側のいくつかの点にノードよりも大きい(または等しい)値を格納することができる.BSTのこのような特性を利用して、配列を並べ替えることができます.
二叉ツリーのノードは最大で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つのエルゴード方法があります.まず、ノード自体を巡回します.左側のサブノード–右側のサブノード中を巡回します.左側のサブノード–ノード自身>>右側のサブノードの後を巡回します.左側のサブノード–ノード自体を>>右側のサブノード