binary-search-tree

说明

二叉搜索树

源码

用法

binarySearchTree.test.ts
import { BinarySearchTree } from "../../utility/algorithm/binary-search-tree";
describe('BST', () => {
const bst = new BinarySearchTree({
nodes: [2, 5, 3, 8, 7, 4, 9, 12, 23, 10, 1],
});
test('bst.handleHasValue should receive a number and return true or false if the value was exist', () => {
const received = [2, 5, 3, 8, 7, 4, 9, 12, 23, 10, 1];
for (const v of received) {
expect(bst.handleHasValue(v)).toBeTruthy();
}
});
test('bst.handleInsert should receive a number and insert it to root', () => {
const received = [100, 200, 300];
for (const v of received) {
bst.handleInsert(v);
expect(bst.handleHasValue(v)).toBeTruthy();
}
});
test('bst.handleRemove should receive a number and remove it from root', () => {
const received = [100, 200, 300];
for (const v of received) {
bst.handleRemove(v);
expect(bst.handleHasValue(v)).toBeFalsy();
}
});
test('bst.handleGetDepth should return the whole tree depth when received undefined', () => {
const expected = 6;
expect(bst.handleGetDepth()).toBe(expected);
});
test('bst.handleGetDepth should receive a number and return its depth which was in tree', () => {
const received = [5, 7, 23];
const expected = [2, 4, 6];
for (const [i, v] of received.entries()) {
expect(bst.handleGetDepth(v)).toBe(expected[i]);
}
});
test('bst.handleGetHeight should return whe whole tree height when received undefined', () => {
const expected = 6;
expect(bst.handleGetHeight()).toBe(expected);
});
test('bst.handleGetHeight should receive a number and return its height which was in tree', () => {
const received = [5, 7, 23];
const expected = [5, 1, 1];
for (const [i, v] of received.entries()) {
expect(bst.handleGetHeight(v)).toBe(expected[i]);
}
});
test('bst.handleGetLeaves should return the collection of leaves node', () => {
const expected = [1, 4, 7, 10, 23];
const result = bst.handleGetLeaves();
for (const [i, v] of result.entries()) {
expect(v.value).toBe(expected[i]);
}
});
test('bst.handleFrontOrderTraversal should ergodic the whole tree by using front-order and execute callback parameter', () => {
const expected = [2, 1, 5, 3, 4, 8, 7, 9, 12, 10, 23];
let count = 0;
bst.handleFrontOrderTraversal((node) => {
expect(node.value).toBe(expected[count]);
count++;
});
});
test('bst.handleMiddleOrderTraversal should ergodic the whole tree by using middle-order and execute callback parameter', () => {
const expected = [1, 2, 5, 3, 4, 8, 7, 9, 12, 10, 23];
let count = 0;
bst.handleMiddleOrderTraversal((node) => {
expect(node.value).toBe(expected[count]);
count++;
})
});
test('bst.handleBackOrderTraversal should ergodic the whole tree by using back-order and execute callback parameter', () => {
const expected = [1, 5, 3, 4, 8, 7, 9, 12, 10, 23, 2];
let count = 0;
bst.handlBackOrderTraversal((node) => {
expect(node.value).toBe(expected[count]);
count++;
})
});
test('bst.handleGetRoot should return the whole tree', () => {
const expected = [2, 1, 5, 3, 4, 8, 7, 9, 12, 10, 23];
let count = 0;
bst.handleFrontOrderTraversal((node) => {
expect(node.value).toBe(expected[count]);
count++;
});
});
test('bst.handleGetMaxValue should return the maximum node which was in tree', () => {
const expected = 23;
const result = bst.handleGetMaxValue();
expect(result).toBe(expected);
});
test('bst.handleGetMinValue should return the minimum node which was in tree', () => {
const expected = 1;
const result = bst.handleGetMinValue();
expect(result).toBe(expected);
});
});

API

Name
Type
Description
handleInsert
(value: number) => Tree
添加新节点
handleRemove
(value: number) => Tree
移除指定节点
handleGetDepth
(value?: number) => Tree
获取指定节点的深度
handleHasValue
(value: number) => Tree
查找二叉树中是否有指定的值
handleFrontOrderTraversal
(callback: (node: TreeNode) => void,) => void
先序遍历
handleMiddleOrderTraversal
(callback: (node: TreeNode) => void,) => void
中序遍历
handlBackOrderTraversal
(callback: (node: TreeNode) => void,) => void
后序遍历
handleGetHeight
(value?: number) => number
获取节点高度
handleGetLeaves
() => TreeNode[]
获取叶子节点
handleGetMinValue
() => number | null
获取最小值
handleGetMaxValue
() => number | null
获取最大值
复制链接