ดาวน์โหลด binstree - ดาวน์โหลดซอร์สโค้ด binstree

บินส์ทรี

แผนผังการค้นหาแบบไบนารีสำหรับ ES6

คำอธิบาย

การใช้ ES6 ของโครงสร้างข้อมูลแผนผังการค้นหาแบบไบนารีพร้อมการสนับสนุน TypeScript

ไปที่แนวทางปฏิบัติเพื่อเรียนรู้เพิ่มเติมเกี่ยวกับวิธีแปลเอกสารนี้เป็นภาษาอื่นๆ

สารบัญ

คำอธิบาย
ติดตั้ง
ในระดับความลึก
การใช้งาน
เอพีไอ
การพัฒนา
ที่เกี่ยวข้อง
ทีม
ใบอนุญาต

ติดตั้ง

เส้นด้าย

yarn add binstree

นพีเอ็ม

npm install binstree

ในระดับความลึก

แผนผังการค้นหาแบบไบนารีเป็นโครงสร้างข้อมูลแบบต้นไม้ไบนารีแบบรูท ซึ่งโหนดประกอบด้วย key เฉพาะและ value ที่เกี่ยวข้อง และชี้ไปที่แผนผังย่อย left และ right สองรายการที่แตกต่างกัน ทรีเป็นไปตามคุณสมบัติการค้นหาแบบไบนารี ดังนั้นคีย์ในแต่ละโหนดจึงมากกว่าคีย์ใดๆ ที่จัดเก็บไว้ในแผนผังย่อยด้านซ้าย และน้อยกว่าคีย์ใดๆ ที่จัดเก็บไว้ในแผนผังย่อยด้านขวา จากผลลัพธ์ที่ใกล้จะเกิดขึ้นของหลักการนี้ การดำเนินการกับแผนผังจะได้รับประโยชน์อย่างมาก เนื่องจากโดยเฉลี่ยแล้วการเปรียบเทียบคีย์แต่ละครั้งจะทำให้การดำเนินการสามารถข้ามได้ประมาณครึ่งหนึ่งของแผนผัง ดังนั้นการแทรก การลบ หรือการค้นหาแต่ละครั้งจะใช้เวลาเป็นสัดส่วนกับลอการิทึมของจำนวนโหนด เก็บไว้ในต้นไม้

การใช้งาน

Binstree เปิดเผย API แบบลูกโซ่ ซึ่งสามารถใช้งานได้ผ่านไวยากรณ์ที่เรียบง่ายและน้อยที่สุด ช่วยให้คุณสามารถรวมวิธีการต่างๆ ได้อย่างมีประสิทธิภาพ

ตัวอย่างการใช้งานยังสามารถพบได้ที่ไดเร็กทอรี 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

เอพีไอ

ต้นไม้. `insert(key, value)`

ประเภทการส่งคืน: Tree

กลายพันธุ์ต้นไม้โดยการแทรกโหนดใหม่ในตำแหน่งที่เหมาะสม

`key`

ประเภท: Number

อาจเป็นตัวเลขใดก็ได้ที่จะสอดคล้องกับ key ของโหนดที่สร้างขึ้น แต่ละโหนดมี key เฉพาะของตัวเอง

`value`

ประเภท: Any

อาจเป็นค่าใดๆ ที่จะจัดเก็บไว้ในโหนดที่สร้างขึ้น

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

const tree = new Tree ( ) ;

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

ต้นไม้. `root`

ประเภทการส่งคืน: Node | null

ส่งกลับโหนดรากของต้นไม้ หากต้นไม้ว่างเปล่าจะส่งกลับ null

 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 }

ต้นไม้. `isEmpty()`

ประเภทการส่งคืน: Boolean

กำหนดว่าต้นไม้ว่างเปล่า โดยคืน true หรือ false ตามความเหมาะสม

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

const tree = new Tree ( ) ;

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

ต้นไม้. `remove(key)`

ประเภทการส่งคืน: Tree

กลายพันธุ์ต้นไม้โดยการลบโหนดที่สอดคล้องกับอาร์กิวเมนต์ key

`key`

ประเภท: Number

อาจเป็นตัวเลขใดๆ ที่สอดคล้องกับ key ของโหนดที่มีอยู่

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

const tree = new Tree ( ) ;

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

ต้นไม้. `includes(key)`

ประเภทการส่งคืน: Boolean

กำหนดว่าแผนผังมีโหนดที่มี key บางตัว โดยส่งคืน true หรือ false ตามความเหมาะสม

`key`

ประเภท: Number

key โหนดเพื่อค้นหา

 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

ต้นไม้. `search(key)`

ประเภทการส่งคืน: Node | null

กำหนดว่าแผนผังรวมโหนดที่มี key บางตัว โดยส่งคืนโหนดเป้าหมายหรือ null ตามความเหมาะสม

`key`

ประเภท: Number

key โหนดเพื่อค้นหา

 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 }

ต้นไม้. `min()`

ประเภทการส่งคืน: Node | null

ส่งคืนโหนดซ้ายสุดในแผนผัง ดังนั้นโหนดที่สอดคล้องกับ key ขั้นต่ำ

 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 }

ต้นไม้. `max()`

ประเภทการส่งคืน: Node | null

ส่งคืนโหนดขวาสุดในแผนผัง ดังนั้นโหนดที่สอดคล้องกับ key สูงสุด

 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 }

ต้นไม้. `size()`

ประเภทการส่งคืน: Number

ส่งกลับจำนวนโหนดทั้งหมดที่อยู่ในแผนผัง

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

const tree = new Tree ( ) ;

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

ต้นไม้. `height()`

ประเภทการส่งคืน: Number

ส่งกลับระยะห่างสูงสุดของโหนดใบใดๆ จากราก หากต้นไม้ว่างเปล่า -1 จะถูกส่งกลับ

 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

ต้นไม้. `inOrder(fn)`

ประเภทการส่งคืน: Tree

ใช้การแวะผ่านตามลำดับ (การแวะผ่านเชิงลึกก่อน - LNR) กับแผนผังและดำเนินการฟังก์ชัน fn ที่มีให้บนแต่ละโหนดที่สำรวจโดยไม่ต้องเปลี่ยนโครงสร้างต้นไม้เอง

`fn`

ประเภท: Function

ฟังก์ชั่นที่จะดำเนินการในแต่ละโหนด

 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

ต้นไม้. `preOrder(fn)`

ประเภทการส่งคืน: Tree

ใช้การแวะผ่านตามคำสั่งซื้อล่วงหน้า (การแวะผ่านเชิงลึกก่อน - NLR) กับแผนผังและดำเนินการฟังก์ชัน fn ที่ให้มาบนแต่ละโหนดที่สำรวจโดยไม่ต้องเปลี่ยนโครงสร้างต้นไม้เอง

`fn`

ประเภท: Function

ฟังก์ชั่นที่จะดำเนินการในแต่ละโหนด

 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

ต้นไม้. `postOrder(fn)`

ประเภทการส่งคืน: Tree

ใช้การแวะผ่านลำดับหลัง (การแวะผ่านเชิงลึกก่อน - LRN) กับแผนผังและดำเนินการฟังก์ชัน fn ที่ให้มาบนแต่ละโหนดที่สำรวจโดยไม่ต้องเปลี่ยนโครงสร้างต้นไม้เอง

`fn`

ประเภท: Function

ฟังก์ชั่นที่จะดำเนินการในแต่ละโหนด

 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

ต้นไม้. `outOrder(fn)`

ประเภทการส่งคืน: Tree

ใช้การแวะผ่านนอกลำดับ (การแวะผ่านเชิงลึกก่อน - RNL) กับแผนผังและดำเนินการฟังก์ชัน fn ที่จัดไว้ให้บนแต่ละโหนดที่สำรวจโดยไม่ต้องเปลี่ยนโครงสร้างต้นไม้เอง

`fn`

ประเภท: Function

ฟังก์ชั่นที่จะดำเนินการในแต่ละโหนด

 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

ต้นไม้. `levelOrder(fn)`

ประเภทการส่งคืน: Tree

ใช้การข้ามลำดับระดับ (การข้ามผ่านตามความกว้างก่อน) กับแผนผังและดำเนินการฟังก์ชัน fn ที่จัดให้บนแต่ละโหนดที่ข้ามผ่านโดยไม่ต้องเปลี่ยนโครงสร้างต้นไม้เอง

`fn`

ประเภท: Function

ฟังก์ชั่นที่จะดำเนินการในแต่ละโหนด

 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

ต้นไม้. `clear()`

ประเภทการส่งคืน: Tree

กลายพันธุ์ต้นไม้โดยการลบโหนดที่อยู่ทั้งหมดออก และส่งคืนให้ว่างเปล่า

 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

ต้นไม้. `toArray()`

ประเภทการส่งคืน: Array<Node>

ใช้การข้ามผ่านตามลำดับกับแผนผังและจัดเก็บแต่ละโหนดที่ข้ามผ่านในอาร์เรย์ อาร์เรย์จะถูกส่งกลับเมื่อสิ้นสุดการสำรวจ

 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' }
// ]

ต้นไม้. `toPairs()`

ประเภทการส่งคืน: Array<[Number, Any]>

ใช้การข้ามผ่านตามลำดับกับทรีและสำหรับแต่ละโหนดที่เคลื่อนที่จะเก็บอยู่ใน n -tuple โดยที่ n ขนาดของทรีคือคู่อันดับ/2-tuple โดยที่องค์ประกอบแรกคือ number ที่สอดคล้องกับ key ของ โหนดที่เคลื่อนที่ และค่าสุดท้ายคือค่าประเภท any ซึ่งสอดคล้องกับ value ที่เก็บไว้ในโหนดที่เคลื่อนที่ n -tuple จะถูกส่งกลับเมื่อสิ้นสุดการสำรวจ

 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'] ]

ต้นไม้. `leafNodes()`

ประเภทการส่งคืน: Array<Node>

ใช้การข้ามผ่านตามลำดับกับทรีและจัดเก็บโหนดลีฟที่เคลื่อนที่แต่ละโหนด (โหนดที่ไม่มีลูก) ในอาร์เรย์ อาร์เรย์จะถูกส่งกลับเมื่อสิ้นสุดการสำรวจ

 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' } 
// ]

ต้นไม้. `fullNodes()`

ประเภทการส่งคืน: Array<Node>

ใช้การข้ามผ่านตามลำดับกับแผนผังและจัดเก็บแต่ละโหนดที่เคลื่อนที่ผ่าน (โหนดที่มีลูกที่ไม่ใช่ค่าว่างสองตัว) ในอาร์เรย์ อาร์เรย์จะถูกส่งกลับเมื่อสิ้นสุดการสำรวจ

 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' } 
// ]

ต้นไม้. `partialNodes()`

ประเภทการส่งคืน: Array<Node>

ใช้การข้ามผ่านตามลำดับกับแผนผังและจัดเก็บแต่ละโหนดบางส่วน (โหนดที่มีลูกที่ไม่ใช่ค่าว่างหนึ่งรายการ) ในอาร์เรย์ อาร์เรย์จะถูกส่งกลับเมื่อสิ้นสุดการสำรวจ

 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' }
// ]

ต้นไม้. `isBalanced()`

ประเภทการส่งคืน: Boolean

คืนค่า true หากต้นไม้มีความสูงสมดุล ซึ่งหมายความว่าต้นไม้ย่อยด้านซ้ายมีความสมดุล ต้นไม้ย่อยด้านขวามีความสมดุล และความแตกต่างระหว่างความสูงของต้นไม้ย่อยด้านซ้ายและแผนภูมิย่อยด้านขวาไม่เกิน 1 ใน กรณีอื่น ๆ วิธีการจะส่งกลับ false

 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

ต้นไม้. `isComplete()`

ประเภทการส่งคืน: Boolean

เมธอดนี้จะคืนค่า true หากทรีเป็นแผนผังการค้นหาแบบไบนารีที่สมบูรณ์ ซึ่งหมายความว่าทุกระดับยกเว้นระดับสุดท้ายจะถูกเติมจนเต็ม และโหนดทั้งหมดจะอยู่ซ้ายสุดเท่าที่จะเป็นไปได้ ในกรณีอื่น ๆ วิธีการจะส่งกลับค่าเท็จ

 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

ต้นไม้. `isFull()`

ประเภทการส่งคืน: Boolean

วิธีการคืนค่า true หากโหนดทั้งหมดที่อยู่ในแผนผังเป็นโหนดใบหรือโหนดเต็ม ในกรณีอื่นใด (ระดับโหนดเท่ากับ 1) วิธีการจะส่งกลับ false

 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

ต้นไม้. `isPerfect()`

ประเภทการส่งคืน: Boolean

วิธีการคืนค่า true หากโหนดภายในทั้งหมดที่อยู่ในแผนผังเป็นโหนดเต็ม (ระดับโหนดเท่ากับ 2) และโหนดใบทั้งหมดอยู่ที่ระดับความสูงเท่ากัน ในกรณีอื่นใด (ระดับโหนดเท่ากับ 1 หรือลีฟและโหนดเต็มพบในระดับความสูงเดียวกัน) วิธีการจะส่งกลับค่า false

 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

นอกจากนี้ ยังมีคลาส Node ที่เปิดเผยพร้อมกับคลาส Tree อีกด้วย ซึ่งมีประโยชน์หลักสำหรับการทดสอบ เนื่องจากสามารถใช้เพื่อเปรียบเทียบโหนดแผนผังได้ คลาสนี้มีเมธอดคอนสตรัคเตอร์แบบไบนารี โดยมี key และพารามิเตอร์ value ซึ่งสอดคล้องกับคีย์และค่าที่จัดเก็บไว้ในอินสแตนซ์ที่สร้างขึ้นตามลำดับ

โหนด `key`

ประเภทการส่งคืน: Number

key ที่สอดคล้องกับอินสแตนซ์ของโหนด

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

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

โหนด `value`

ประเภทการส่งคืน: Any

ค่าที่โหนดมีอยู่

 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 }

โหนด `left`

ประเภทการส่งคืน: Node | null

ทรีย่อยด้านซ้ายที่โหนดชี้ไป

 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 }

โหนด `right`

ประเภทการส่งคืน: Node | null

ทรีย่อยด้านขวาที่โหนดชี้ไป

 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 }

โหนด `children`

ประเภทการส่งคืน: Array<Node>

ส่งคืนอาร์เรย์ที่ติดต่อกับลูกของอินสแตนซ์ โดยที่ลูกด้านซ้าย (ถ้ามี) เป็นองค์ประกอบแรกของอาร์เรย์ และลูกด้านขวา (หากมี) คือองค์ประกอบสุดท้ายของอาร์เรย์

 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 }
// ]

โหนด `degree`

ประเภทการส่งคืน: Number

ส่งกลับจำนวนแผนผังย่อยที่โหนดชี้ไป

 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

โหนด `height()`

ประเภทการส่งคืน: Number

ส่งกลับระยะทางสูงสุดของโหนดปลายสุดจากอินสแตนซ์ของโหนด

 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

โหนด `isFull()`

ประเภทการส่งคืน: Boolean

กำหนดว่าโหนดเป็นโหนดเต็ม (มีสองลูกที่ไม่ใช่ค่าว่าง) โดยส่งคืน true หรือ false ตามความเหมาะสม

 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

โหนด `isInternal()`

ประเภทการส่งคืน: Boolean

กำหนดว่าโหนดเป็นโหนดภายใน (มีลูกที่ไม่ใช่ค่าว่างอย่างน้อยหนึ่งรายการ) โดยส่งคืน true หรือ false ตามความเหมาะสม

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

const tree = new Tree ( ) ;

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

โหนด `isLeaf()`

ประเภทการส่งคืน: Boolean

กำหนดว่าโหนดเป็นโหนดปลายสุด (ไม่มีลูก) โดยส่งคืน true หรือ false ตามความเหมาะสม

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

const tree = new Tree ( ) ;

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

โหนด `isLeftPartial()`

ประเภทการส่งคืน: Boolean

กำหนดว่าโหนดเป็นโหนดบางส่วนด้านซ้าย (มีโหนดย่อยที่ไม่เป็นค่าว่างเพียงโหนดเดียว) โดยส่งคืน true หรือ false ตามความเหมาะสม

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

const tree = new Tree ( ) ;

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

โหนด `isPartial()`

ประเภทการส่งคืน: Boolean

กำหนดว่าโหนดเป็นโหนดบางส่วน (มีลูกเดียวที่ไม่ใช่ค่าว่าง) โดยส่งคืน true หรือ false ตามความเหมาะสม

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

const tree = new Tree ( ) ;

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

โหนด `isRightPartial()`

ประเภทการส่งคืน: Boolean

กำหนดว่าโหนดเป็นโหนดบางส่วนที่ถูกต้อง (มีโหนดย่อยที่ไม่ใช่ค่าว่างเพียงโหนดเดียว) โดยส่งคืน true หรือ false ตามความเหมาะสม

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

const tree = new Tree ( ) ;

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

โหนด `toPair()`

ประเภทการส่งคืน: [Number, Any]

ส่งกลับค่าคู่อันดับ/2-tuple โดยที่องค์ประกอบแรกเป็นตัวเลขที่สอดคล้องกับ key ของโหนด และองค์ประกอบสุดท้ายคือค่า ซึ่งสามารถเป็นประเภทใดก็ได้ ซึ่งสอดคล้องกับ value ที่จัดเก็บไว้ในโหนด

 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']

การพัฒนา

สำหรับข้อมูลเพิ่มเติมเกี่ยวกับวิธีการมีส่วนร่วมในโครงการ โปรดอ่านหลักเกณฑ์การบริจาค

แยกพื้นที่เก็บข้อมูลและโคลนไปยังเครื่องของคุณ
นำทางไปยังทางแยกในพื้นที่ของคุณ: cd binstree
ติดตั้งการพึ่งพาโครงการ: npm install หรือ yarn install
ขลิบโค้ดและรันการทดสอบ: npm test หรือ yarn test

ที่เกี่ยวข้อง

avlbinstree - แผนผังการค้นหาไบนารีที่ปรับสมดุลตัวเองของ AVL สำหรับ ES6
binoheap - ฮีปทวินามสำหรับ ES6
doublelie - รายการเชื่อมโยงแบบวงกลมและเชิงเส้นสองเท่าสำหรับ ES6
dsforest - ฟอเรสต์ที่แยกจากกันสำหรับ ES6
kiu - คิว FIFO สำหรับ ES6
mheap - ไบนารีขั้นต่ำและฮีปสูงสุดสำหรับ ES6
prioqueue - คิวลำดับความสำคัญสำหรับ ES6
shtack - กอง LIFO สำหรับ ES6
singlely - รายการเชื่อมโยงแบบวงกลมและเชิงเส้นเดี่ยวสำหรับ ES6

ทีม

เคลาส์ ซินานี (@klaussinani)

ใบอนุญาต

เอ็มไอที

ขยาย

binstree

บินส์ทรี

แผนผังการค้นหาแบบไบนารีสำหรับ ES6

คำอธิบาย

สารบัญ

ติดตั้ง

เส้นด้าย

นพีเอ็ม

ในระดับความลึก

การใช้งาน

เอพีไอ

ต้นไม้. insert(key, value)

key

value

ต้นไม้. root

ต้นไม้. isEmpty()

ต้นไม้. remove(key)

key

ต้นไม้. includes(key)

key

ต้นไม้. search(key)

key

ต้นไม้. min()

ต้นไม้. max()

ต้นไม้. size()

ต้นไม้. height()

ต้นไม้. inOrder(fn)

fn

ต้นไม้. preOrder(fn)

fn

ต้นไม้. postOrder(fn)

fn

ต้นไม้. outOrder(fn)

fn

ต้นไม้. levelOrder(fn)

fn

ต้นไม้. clear()

ต้นไม้. toArray()

ต้นไม้. toPairs()

ต้นไม้. leafNodes()

ต้นไม้. fullNodes()

ต้นไม้. partialNodes()

ต้นไม้. isBalanced()

ต้นไม้. isComplete()

ต้นไม้. isFull()

ต้นไม้. isPerfect()

โหนด key

โหนด value

โหนด left

โหนด right

โหนด children

โหนด degree

โหนด height()

โหนด isFull()

โหนด isInternal()

โหนด isLeaf()

โหนด isLeftPartial()

โหนด isPartial()

โหนด isRightPartial()

โหนด toPair()

การพัฒนา

ที่เกี่ยวข้อง

ทีม

ใบอนุญาต

ต้นไม้. `insert(key, value)`

`key`

`value`

ต้นไม้. `root`

ต้นไม้. `isEmpty()`

ต้นไม้. `remove(key)`

`key`

ต้นไม้. `includes(key)`

`key`

ต้นไม้. `search(key)`

`key`

ต้นไม้. `min()`

ต้นไม้. `max()`

ต้นไม้. `size()`

ต้นไม้. `height()`

ต้นไม้. `inOrder(fn)`

`fn`

ต้นไม้. `preOrder(fn)`

`fn`

ต้นไม้. `postOrder(fn)`

`fn`

ต้นไม้. `outOrder(fn)`

`fn`

ต้นไม้. `levelOrder(fn)`

`fn`

ต้นไม้. `clear()`

ต้นไม้. `toArray()`

ต้นไม้. `toPairs()`

ต้นไม้. `leafNodes()`

ต้นไม้. `fullNodes()`

ต้นไม้. `partialNodes()`

ต้นไม้. `isBalanced()`

ต้นไม้. `isComplete()`

ต้นไม้. `isFull()`

ต้นไม้. `isPerfect()`

โหนด `key`

โหนด `value`

โหนด `left`

โหนด `right`

โหนด `children`

โหนด `degree`

โหนด `height()`

โหนด `isFull()`

โหนด `isInternal()`

โหนด `isLeaf()`

โหนด `isLeftPartial()`

โหนด `isPartial()`

โหนด `isRightPartial()`

โหนด `toPair()`