binstree Download - binstree Quellcode herunterladen

Binstree

Binäre Suchbäume für ES6

Beschreibung

ES6-Implementierung der binären Suchbaum-Datenstruktur mit TypeScript-Unterstützung.

Besuchen Sie die Beitragsrichtlinien, um mehr darüber zu erfahren, wie Sie dieses Dokument in weitere Sprachen übersetzen können.

Inhalt

Beschreibung
Installieren
Im Detail
Verwendung
API
Entwicklung
Verwandt
Team
Lizenz

Installieren

Garn

yarn add binstree

NPM

npm install binstree

Im Detail

Ein binärer Suchbaum ist eine verwurzelte binäre Baumdatenstruktur, deren Knoten einen eindeutigen key und einen zugehörigen value enthalten und auf zwei unterschiedene left und right Unterbäume verweisen. Der Baum erfüllt die binäre Sucheigenschaft, daher ist der Schlüssel in jedem Knoten größer als jeder im linken Teilbaum gespeicherte Schlüssel und kleiner als jeder im rechten Teilbaum gespeicherte Schlüssel. Als direkte Folge dieses Prinzips ergeben sich große Vorteile für Baumoperationen, da die Operationen im Durchschnitt bei jedem Schlüsselvergleich etwa die Hälfte des Baums überspringen können, sodass jedes Einfügen, Löschen oder Nachschlagen Zeit proportional zum Logarithmus der Anzahl der Knoten benötigt im Baum gespeichert.

Verwendung

Binstree stellt eine verkettbare API bereit, die über eine einfache und minimale Syntax genutzt werden kann und es Ihnen ermöglicht, Methoden effektiv zu kombinieren.

Anwendungsbeispiele finden Sie auch im test .

 'use strict' ;
const { Tree , Node } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;
//=> Tree { root: null }

tree . insert ( 10 , 'A' ) ;
// => Tree { root: Node { left: null, right: null, key: 10, value: 'A' } }

tree . root ;
//=> Node { left: null, right: null, key: 10, value: 'A' }

const node = new Node ( 10 , 'A' ) ;

tree . root . key === node . key ;
//=> true

tree . root . value === node . value ;
//=> true

tree . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) . root ;
//=> Node { left: [Node], right: [Node], key: 10, value: 'A' }

tree . root . left ;
//=> Node { left: null, right: null, key: 5, value: 'B' }

tree . root . right ;
//=> Node { left: null, right: null, key: 15, value: 'C' }

tree . insert ( 2 , 'D' ) . insert ( 7 , 'E' ) . insert ( 12 , 'F' ) . insert ( 20 , 'G' ) ;

tree . search ( 5 ) ;
//=> Node { key: 5, value: 'B',
//  left: Node { left: null, right: null, key: 2, value: 'D' },
//  right: Node { left: null, right: null, key: 7, value: 'E' } }

tree . search ( 15 ) ;
//=> Node { key: 15, value: 'C',
//  left: Node { left: null, right: null, key: 12, value: 'F' },
//  right: Node { left: null, right: null, key: 20, value: 'G' } }

tree . includes ( 12 ) ;
//=> true

tree . includes ( 100 ) ;
//=> false

tree . height ( ) ;
//=> 2

tree . isBalanced ( ) ;
//=> true

tree . remove ( 10 ) . root ;
//=> Node { key: 12, value: 'F',
//  left: Node { left: [Node], right: [Node], key: 5, value: 'B' },
//  right: Node { left: null, right: [Node], key: 15, value: 'C' } }

tree . isBalanced ( ) ;
//=> false

API

Baum. `insert(key, value)`

Rückgabetyp: Tree

Ändert den Baum, indem an der entsprechenden Stelle ein neuer Knoten eingefügt wird.

`key`

Typ: Number

Kann eine beliebige Zahl sein, die dem key des erstellten Knotens entspricht. Jeder Knoten hat seinen eigenen eindeutigen key .

`value`

Typ: Any

Kann ein beliebiger Wert sein, der im erstellten Knoten gespeichert wird.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) ;
// => Tree { root: Node { key: 10, value: 'A', left: null, right: null } }

Baum. `root`

Rückgabetyp: Node | null

Gibt den Wurzelknoten des Baums zurück. Wenn der Baum leer ist, wird null zurückgegeben.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) ;
// => Tree { root: Node { key: 10, value: 'A', left: null, right: null } }
tree . root ;
// => Node { key: 10, value: 'A', left: null, right: null }

Baum. `isEmpty()`

Rückgabetyp: Boolean

Bestimmt, ob der Baum leer ist, und gibt je nach Bedarf true oder false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) ;
tree . isEmpty ( ) ;
// => false

Baum. `remove(key)`

Rückgabetyp: Tree

Mutiert den Baum, indem der Knoten entfernt wird, der dem key entspricht.

`key`

Typ: Number

Kann eine beliebige Zahl sein, die dem key eines vorhandenen Knotens entspricht.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) ;
tree . remove ( 10 ) ;
//=> Tree { root: null }

Baum. `includes(key)`

Rückgabetyp: Boolean

Bestimmt, ob der Baum einen Knoten mit einem bestimmten key enthält, und gibt je nach Bedarf true oder false zurück.

`key`

Typ: Number

key , nach dem gesucht werden soll.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) ;
tree . includes ( 10 ) ;
// => true
tree . includes ( 25 ) ;
// => false
tree . includes ( 5 ) ;
// => true

Baum. `search(key)`

Rückgabetyp: Node | null

Bestimmt, ob der Baum einen Knoten mit einem bestimmten key enthält, und gibt je nach Bedarf den Zielknoten oder null zurück.

`key`

Typ: Number

key , nach dem gesucht werden soll.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) ;
tree . search ( 10 ) ;
// => Node { key: 10, value: 'A', left: [Node], right: null }
tree . search ( 25 ) ;
// => null
tree . search ( 5 ) ;
// => Node { key: 5, value: 'B', left: null, right: null }

Baum. `min()`

Rückgabetyp: Node | null

Gibt den Knoten ganz links im Baum zurück, also den Knoten, der dem key entspricht.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 0 , 'C' ) ;
tree . min ( ) ;
// => Node { key: 0, value: 'C', left: null, right: null }

Baum. `max()`

Rückgabetyp: Node | null

Gibt den Knoten ganz rechts im Baum zurück, also den Knoten, der dem maximalen key entspricht.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 15 , 'B' ) . insert ( 25 , 'C' ) ;
tree . max ( ) ;
// => Node { key: 25, value: 'C', left: null, right: null }

Baum. `size()`

Rückgabetyp: Number

Gibt die Gesamtzahl der im Baum vorhandenen Knoten zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 15 , 'B' ) . insert ( 25 , 'C' ) ;
tree . size ( ) ;
// => 3

Baum. `height()`

Rückgabetyp: Number

Gibt den maximalen Abstand eines Blattknotens von der Wurzel zurück. Wenn der Baum leer ist, wird -1 zurückgegeben.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) ;
tree . height ( ) ;
// => 0
tree . insert ( 15 , 'B' ) . insert ( 25 , 'C' ) . insert ( 35 , 'D' ) ;
tree . height ( ) ;
//=> 3

Baum. `inOrder(fn)`

Rückgabetyp: Tree

Wendet eine Durchquerung in der Reihenfolge (Tiefe-zuerst-Durchquerung – LNR) auf den Baum an und führt die bereitgestellte fn Funktion auf jedem durchquerten Knoten aus, ohne den Baum selbst zu verändern.

`fn`

Typ: Function

Funktion, die auf jedem Knoten ausgeführt werden soll.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . inOrder ( node => console . log ( node . key ) ) ;
// => 5
// 10
// 15

Baum. `preOrder(fn)`

Rückgabetyp: Tree

Wendet eine Vorbestellungsdurchquerung (Depth-First-Durchquerung – NLR) auf den Baum an und führt die bereitgestellte fn Funktion auf jedem durchquerten Knoten aus, ohne den Baum selbst zu verändern.

`fn`

Typ: Function

Funktion, die auf jedem Knoten ausgeführt werden soll.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . preOrder ( node => console . log ( node . key ) ) ;
// => 10
// 5
// 15

Baum. `postOrder(fn)`

Rückgabetyp: Tree

Wendet Post-Order-Traversal (Tiefen-First-Traversal – LRN) auf den Baum an und führt die bereitgestellte fn Funktion auf jedem durchlaufenen Knoten aus, ohne den Baum selbst zu verändern.

`fn`

Typ: Function

Funktion, die auf jedem Knoten ausgeführt werden soll.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . postOrder ( node => console . log ( node . key ) ) ;
// => 5
// 15
// 10

Baum. `outOrder(fn)`

Rückgabetyp: Tree

Wendet Out-Order-Traversal (Tiefen-First-Traversal – RNL) auf den Baum an und führt die bereitgestellte fn Funktion auf jedem durchlaufenen Knoten aus, ohne den Baum selbst zu verändern.

`fn`

Typ: Function

Funktion, die auf jedem Knoten ausgeführt werden soll.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . outOrder ( node => console . log ( node . key ) ) ;
// => 15
// 10
// 5

Baum. `levelOrder(fn)`

Rückgabetyp: Tree

Wendet eine Durchquerung der Ebenenreihenfolge (Breite-zuerst-Durchquerung) auf den Baum an und führt die bereitgestellte fn Funktion auf jedem durchquerten Knoten aus, ohne den Baum selbst zu verändern.

`fn`

Typ: Function

Funktion, die auf jedem Knoten ausgeführt werden soll.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . levelOrder ( node => console . log ( node . key ) ) ;
// => 10
// 5
// 15

Baum. `clear()`

Rückgabetyp: Tree

Mutiert den Baum, indem er alle vorhandenen Knoten entfernt und ihn leer zurückgibt.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
//=> Tree { root: Node { left: [Node], right: [Node], key: 3, value: 'A' } }
tree . size ( ) ;
//=> 3
tree . clear ( ) ;
//=> Tree { root: null } }
tree . size ( ) ;
//=> 0

Baum. `toArray()`

Rückgabetyp: Array<Node>

Wendet eine Durchquerung in der richtigen Reihenfolge auf den Baum an und speichert jeden durchquerten Knoten in einem Array. Das Array wird am Ende des Durchlaufs zurückgegeben.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) . insert ( 3 , 'D' ) . insert ( 20 , 'F' ) ;
tree . toArray ( ) ;
//=> [ 
//  Node { left: null, right: null, key: 3, value: 'D' },
//  Node { left: [Node], right: null, key: 5, value: 'B' },
//  Node { left: [Node], right: [Node], key: 10, value: 'A' },
//  Node { left: null, right: [Node], key: 15, value: 'C' },
//  Node { left: null, right: null, key: 20, value: 'F' }
// ]

Baum. `toPairs()`

Rückgabetyp: Array<[Number, Any]>

Wendet eine Durchquerung in der Reihenfolge auf den Baum an und speichert für jeden durchquerten Knoten ein n -Tupel, wobei n die Größe des Baums ist, ein geordnetes Paar/2-Tupel, wobei das erste Element eine number ist, die dem key des Baums entspricht durchquerten Knoten, und der letzte ist ein Wert vom Typ any , der dem im durchquerten Knoten gespeicherten value entspricht. Das n -Tupel wird am Ende des Durchlaufs zurückgegeben.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) . insert ( 3 , 'D' ) . insert ( 20 , 'F' ) ;
tree . toPairs ( ) ;
//=> [ [3, 'D'], [5, 'B'], [10, 'A'], [15, 'C'], [20, 'F'] ]

Baum. `leafNodes()`

Rückgabetyp: Array<Node>

Wendet eine Durchquerung in der richtigen Reihenfolge auf den Baum an und speichert jeden durchquerten Blattknoten (Knoten ohne untergeordnete Elemente) in einem Array. Das Array wird am Ende des Durchlaufs zurückgegeben.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . leafNodes ( ) ;
//=> [ 
//  Node { left: null, right: null, key: 5, value: 'B' },
//  Node { left: null, right: null, key: 15, value: 'C' } 
// ]

Baum. `fullNodes()`

Rückgabetyp: Array<Node>

Wendet die Durchquerung in der richtigen Reihenfolge auf den Baum an und speichert jeden durchquerten vollständigen Knoten (Knoten mit zwei untergeordneten Elementen ungleich Null) in einem Array. Das Array wird am Ende des Durchlaufs zurückgegeben.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . fullNodes ( ) ;
//=> [ 
//  Node { left: [Node], right: [Node], key: 10, value: 'A' } 
// ]

Baum. `partialNodes()`

Rückgabetyp: Array<Node>

Wendet einen Durchlauf in der richtigen Reihenfolge auf den Baum an und speichert jeden Teilknoten (Knoten mit einem untergeordneten Element ungleich Null) in einem Array. Das Array wird am Ende des Durchlaufs zurückgegeben.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) . insert ( 20 , 'D' ) . insert ( 3 , 'E' ) ;
tree . partialNodes ( ) ;
//=> [ 
//  Node { left: [Node], right: null, key: 5, value: 'B' },
//  Node { left: null, right: [Node], key: 15, value: 'C' }
// ]

Baum. `isBalanced()`

Rückgabetyp: Boolean

Gibt true zurück, wenn der Baum höhenausgeglichen ist, was bedeutet, dass sein linker Unterbaum ausgeglichen ist, sein rechter Unterbaum ausgeglichen ist und der Unterschied zwischen den Höhen des linken Unterbaums und des rechten Unterbaums nicht größer als 1 ist In jedem anderen Fall gibt die Methode false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . isBalanced ( ) ;
//=> true
tree . insert ( 20 , 'D' ) . insert ( 30 , 'E' ) ;
tree . isBalanced ( ) ;
//=> false

Baum. `isComplete()`

Rückgabetyp: Boolean

Die Methode gibt true zurück, wenn der Baum ein vollständiger binärer Suchbaum ist, was bedeutet, dass jede Ebene, außer möglicherweise der letzten, vollständig gefüllt ist und alle Knoten so weit links wie möglich liegen. In allen anderen Fällen gibt die Methode „false“ zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . isComplete ( ) ;
//=> true
tree . insert ( 3 , 'D' ) ;
tree . isComplete ( ) ;
//=> true
tree . insert ( 20 , 'E' ) ;
tree . isComplete ( ) ;
//=> false

Baum. `isFull()`

Rückgabetyp: Boolean

Die Methode gibt true zurück, wenn alle im Baum vorhandenen Knoten entweder Blattknoten oder vollständige Knoten sind. In jedem anderen Fall (Knotengrad gleich 1) gibt die Methode false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . isFull ( ) ;
//=> true
tree . insert ( 8 , 'D' ) ;
tree . isFull ( ) ;
//=> false

Baum. `isPerfect()`

Rückgabetyp: Boolean

Die Methode gibt true zurück, wenn alle internen Knoten im Baum vollständige Knoten sind (Knotengrad gleich 2) und alle Blattknoten auf derselben Höhenstufe liegen. In allen anderen Fällen (Knotengrad gleich 1 oder Blatt- und Vollknoten befinden sich auf derselben Höhenebene) gibt die Methode false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) ;
tree . isPerfect ( ) ;
//=> true
tree . insert ( 3 , 'D' ) . insert ( 7 , 'E' ) . insert ( 12 , 'F' ) . insert ( 20 , 'G' ) ;
tree . isPerfect ( ) ;
//=> true
tree . insert ( 1 , 'H' ) ;
tree . isPerfect ( ) ;
//=> false

Neben der exponierten Tree -Klasse ist auch die Node -Klasse verfügbar, die hauptsächlich für Testzwecke nützlich ist, da sie zum Vergleichen von Baumknoten verwendet werden kann. Die Klasse verfügt über eine binäre Konstruktormethode mit einem key und einem value , die dem Schlüssel bzw. dem in der erstellten Instanz gespeicherten Wert entsprechen.

Knoten. `key`

Rückgabetyp: Number

Der key , der der Knoteninstanz entspricht.

 const { Node } = require ( 'binstree' ) ;

const node = new Node ( 10 , 'A' ) ;
// => { key:10, value: 'A', left: null, right: null }
node . key ;
//=> 10

Knoten. `value`

Rückgabetyp: Any

Der Wert, den der Knoten enthält.

 const { Node } = require ( 'binstree' ) ;

const node = new Node ( 10 , 'A' ) ;

// => { key: 10, value: 'A', left: null, right: null }
node . value ;
//=> 'A'
node . value = 'B'
// => { key: 10, value: 'B', left: null, right: null }

Knoten. `left`

Rückgabetyp: Node | null

Der linke Unterbaum, auf den der Knoten zeigt.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root ;
// => { key: 10, value: 'A', left: null, right: null }
tree . root . left ;
//=> null
tree . insert ( 5 , 'B' ) . root ;
// => { key: 10, value: 'A', left: { key: 5, value: 'B', left: null, right: null } , right: null }
tree . root . left ;
//=> { key: 5, value: 'B', left: null, right: null }

Knoten. `right`

Rückgabetyp: Node | null

Der rechte Unterbaum, auf den der Knoten zeigt.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root ;
// => { key: 10, value: 'A', left: null, right: null }
tree . root . right ;
//=> null
tree . insert ( 15 , 'B' ) . root ;
// => { key: 10, value: 'A', left: null , right: { key: 15, value: 'B', left: null, right: null } }
tree . root . right ;
//=> { key: 15, value: 'B', left: null, right: null }

Knoten. `children`

Rückgabetyp: Array<Node>

Gibt ein Array zurück, das die untergeordneten Elemente der Instanz kontaktiert, wobei das linke untergeordnete Element, sofern vorhanden, das erste Element des Arrays und das rechte untergeordnete Element, sofern vorhanden, das letzte Element des Arrays ist.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root . children ;
//=> []
tree . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) . root . children ;
// => [
//  { key: 5, value: 'B', left: null , right: null }, 
//  { key: 15, value: 'C', left: null, right: null }
// ]

Knoten. `degree`

Rückgabetyp: Number

Gibt die Anzahl der Unterbäume zurück, auf die der Knoten zeigt.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root . degree ;
//=> 0
tree . insert ( 5 , 'B' ) . root . degree ;
//=> 1
tree . insert ( 15 , 'C' ) . root . degree ;
//=> 2

Knoten. `height()`

Rückgabetyp: Number

Gibt den maximalen Abstand eines beliebigen Blattknotens von der Knoteninstanz zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . insert ( 15 , 'B' ) . insert ( 25 , 'C' ) . insert ( 35 , 'D' ) ;
tree . root . height ( ) ;
//=> 3
tree . root . right . height ( ) ;
//=> 2

Knoten. `isFull()`

Rückgabetyp: Boolean

Bestimmt, ob ein Knoten ein vollständiger Knoten ist (zwei untergeordnete Knoten ungleich Null hat) und gibt je nach Bedarf true oder false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root . isFull ( ) ;
//=> false
tree . insert ( 5 , 'B' ) . insert ( 15 , 'C' ) . root . isFull ( ) ;
//=> true

Knoten. `isInternal()`

Rückgabetyp: Boolean

Bestimmt, ob ein Knoten ein interner Knoten ist (mindestens einen untergeordneten Knoten ungleich Null hat) und gibt je nach Bedarf true oder false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root . isInternal ( ) ;
//=> false
tree . insert ( 5 , 'B' ) . root . isInternal ( ) ;
//=> true

Knoten. `isLeaf()`

Rückgabetyp: Boolean

Bestimmt, ob ein Knoten ein Blattknoten ist (keine untergeordneten Knoten hat) und gibt je nach Bedarf true oder false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root . isLeaf ( ) ;
//=> true
tree . insert ( 5 , 'B' ) . root . isLeaf ( ) ;
//=> false

Knoten. `isLeftPartial()`

Rückgabetyp: Boolean

Bestimmt, ob es sich bei einem Knoten um einen linken Teilknoten handelt (d. h. es gibt nur noch einen untergeordneten Knoten, der nicht Null ist), und gibt je nach Bedarf true oder false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root . isLeftPartial ( ) ;
//=> false
tree . insert ( 5 , 'B' ) . root . isLeftPartial ( ) ;
//=> true

Knoten. `isPartial()`

Rückgabetyp: Boolean

Bestimmt, ob ein Knoten ein Teilknoten ist (nur einen untergeordneten Knoten ungleich Null hat) und gibt je nach Bedarf true oder false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root . isPartial ( ) ;
//=> false
tree . insert ( 15 , 'B' ) . root . isPartial ( ) ;
//=> true

Knoten. `isRightPartial()`

Rückgabetyp: Boolean

Bestimmt, ob ein Knoten ein rechter Teilknoten ist (nur einen rechten untergeordneten Knoten ungleich Null hat) und gibt je nach Bedarf true oder false zurück.

 const { Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;

tree . insert ( 10 , 'A' ) . root . isRightPartial ( ) ;
//=> false
tree . insert ( 15 , 'B' ) . root . isRightPartial ( ) ;
//=> true

Knoten. `toPair()`

Rückgabetyp: [Number, Any]

Gibt ein geordnetes Paar/2-Tupel zurück, wobei das erste Element eine Zahl ist, die dem key des Knotens entspricht, und das letzte Element ein Wert ist, der von einem beliebigen Typ sein kann und dem im Knoten gespeicherten value entspricht.

 const { Node , Tree } = require ( 'binstree' ) ;

const tree = new Tree ( ) ;
const node = new Node ( 5 , 'B' ) ;

node . toPair ( ) ;
//=> [5, 'B']
tree . insert ( 10 , 'A' ) . root . toPair ( ) ;
//=> [10, 'A']

Entwicklung

Weitere Informationen darüber, wie Sie zum Projekt beitragen können, finden Sie in den Beitragsrichtlinien.

Forken Sie das Repository und klonen Sie es auf Ihren Computer
Navigieren Sie zu Ihrem lokalen Zweig: cd binstree
Installieren Sie die Projektabhängigkeiten: npm install oder yarn install
Flusen Sie den Code und führen Sie die Tests aus: npm test oder yarn test

Verwandt

avlbinstree – AVL selbstausgleichende binäre Suchbäume für ES6
binoheap – Binomial-Heaps für ES6
doublie – Doppelt zirkulär und linear verknüpfte Listen für ES6
dsforest – Disjunkte Wälder für ES6
kiu – FIFO-Warteschlangen für ES6
mheap – Binäre Min- und Max-Heaps für ES6
prioqueue – Prioritätswarteschlangen für ES6
shtack – LIFO-Stacks für ES6
singlie – Einfach zirkulär und linear verknüpfte Listen für ES6

Team

Klaus Sinani (@klaussinani)

Lizenz

MIT

Expandieren

binstree

Binstree

Binäre Suchbäume für ES6

Beschreibung

Inhalt

Installieren

Garn

NPM

Im Detail

Verwendung

API

Baum. insert(key, value)

key

value

Baum. root

Baum. isEmpty()

Baum. remove(key)

key

Baum. includes(key)

key

Baum. search(key)

key

Baum. min()

Baum. max()

Baum. size()

Baum. height()

Baum. inOrder(fn)

fn

Baum. preOrder(fn)

fn

Baum. postOrder(fn)

fn

Baum. outOrder(fn)

fn

Baum. levelOrder(fn)

fn

Baum. clear()

Baum. toArray()

Baum. toPairs()

Baum. leafNodes()

Baum. fullNodes()

Baum. partialNodes()

Baum. isBalanced()

Baum. isComplete()

Baum. isFull()

Baum. isPerfect()

Knoten. key

Knoten. value

Knoten. left

Knoten. right

Knoten. children

Knoten. degree

Knoten. height()

Knoten. isFull()

Knoten. isInternal()

Knoten. isLeaf()

Knoten. isLeftPartial()

Knoten. isPartial()

Knoten. isRightPartial()

Knoten. toPair()

Entwicklung

Verwandt

Team

Lizenz

Baum. `insert(key, value)`

`key`

`value`

Baum. `root`

Baum. `isEmpty()`

Baum. `remove(key)`

`key`

Baum. `includes(key)`

`key`

Baum. `search(key)`

`key`

Baum. `min()`

Baum. `max()`

Baum. `size()`

Baum. `height()`

Baum. `inOrder(fn)`

`fn`

Baum. `preOrder(fn)`

`fn`

Baum. `postOrder(fn)`

`fn`

Baum. `outOrder(fn)`

`fn`

Baum. `levelOrder(fn)`

`fn`

Baum. `clear()`

Baum. `toArray()`

Baum. `toPairs()`

Baum. `leafNodes()`

Baum. `fullNodes()`

Baum. `partialNodes()`

Baum. `isBalanced()`

Baum. `isComplete()`

Baum. `isFull()`

Baum. `isPerfect()`

Knoten. `key`

Knoten. `value`

Knoten. `left`

Knoten. `right`

Knoten. `children`

Knoten. `degree`

Knoten. `height()`

Knoten. `isFull()`

Knoten. `isInternal()`

Knoten. `isLeaf()`

Knoten. `isLeftPartial()`

Knoten. `isPartial()`

Knoten. `isRightPartial()`

Knoten. `toPair()`