binary-search-tree

说明

二叉搜索树

源码

用法

binarySearchTree.test.ts
1
import { BinarySearchTree } from "../../utility/algorithm/binary-search-tree";
2
3
describe('BST', () => {
4
const bst = new BinarySearchTree({
5
nodes: [2, 5, 3, 8, 7, 4, 9, 12, 23, 10, 1],
6
});
7
8
test('bst.handleHasValue should receive a number and return true or false if the value was exist', () => {
9
const received = [2, 5, 3, 8, 7, 4, 9, 12, 23, 10, 1];
10
11
for (const v of received) {
12
expect(bst.handleHasValue(v)).toBeTruthy();
13
}
14
});
15
16
test('bst.handleInsert should receive a number and insert it to root', () => {
17
const received = [100, 200, 300];
18
19
for (const v of received) {
20
bst.handleInsert(v);
21
expect(bst.handleHasValue(v)).toBeTruthy();
22
}
23
});
24
25
test('bst.handleRemove should receive a number and remove it from root', () => {
26
const received = [100, 200, 300];
27
28
for (const v of received) {
29
bst.handleRemove(v);
30
expect(bst.handleHasValue(v)).toBeFalsy();
31
}
32
});
33
34
test('bst.handleGetDepth should return the whole tree depth when received undefined', () => {
35
const expected = 6;
36
37
expect(bst.handleGetDepth()).toBe(expected);
38
});
39
40
test('bst.handleGetDepth should receive a number and return its depth which was in tree', () => {
41
const received = [5, 7, 23];
42
const expected = [2, 4, 6];
43
44
for (const [i, v] of received.entries()) {
45
expect(bst.handleGetDepth(v)).toBe(expected[i]);
46
}
47
});
48
49
test('bst.handleGetHeight should return whe whole tree height when received undefined', () => {
50
const expected = 6;
51
52
expect(bst.handleGetHeight()).toBe(expected);
53
});
54
55
test('bst.handleGetHeight should receive a number and return its height which was in tree', () => {
56
const received = [5, 7, 23];
57
const expected = [5, 1, 1];
58
59
for (const [i, v] of received.entries()) {
60
expect(bst.handleGetHeight(v)).toBe(expected[i]);
61
}
62
});
63
64
test('bst.handleGetLeaves should return the collection of leaves node', () => {
65
const expected = [1, 4, 7, 10, 23];
66
const result = bst.handleGetLeaves();
67
68
for (const [i, v] of result.entries()) {
69
expect(v.value).toBe(expected[i]);
70
}
71
});
72
73
test('bst.handleFrontOrderTraversal should ergodic the whole tree by using front-order and execute callback parameter', () => {
74
const expected = [2, 1, 5, 3, 4, 8, 7, 9, 12, 10, 23];
75
let count = 0;
76
77
bst.handleFrontOrderTraversal((node) => {
78
expect(node.value).toBe(expected[count]);
79
80
count++;
81
});
82
});
83
84
test('bst.handleMiddleOrderTraversal should ergodic the whole tree by using middle-order and execute callback parameter', () => {
85
const expected = [1, 2, 5, 3, 4, 8, 7, 9, 12, 10, 23];
86
let count = 0;
87
88
bst.handleMiddleOrderTraversal((node) => {
89
expect(node.value).toBe(expected[count]);
90
91
count++;
92
})
93
});
94
95
test('bst.handleBackOrderTraversal should ergodic the whole tree by using back-order and execute callback parameter', () => {
96
const expected = [1, 5, 3, 4, 8, 7, 9, 12, 10, 23, 2];
97
let count = 0;
98
99
bst.handlBackOrderTraversal((node) => {
100
expect(node.value).toBe(expected[count]);
101
102
count++;
103
})
104
});
105
106
test('bst.handleGetRoot should return the whole tree', () => {
107
const expected = [2, 1, 5, 3, 4, 8, 7, 9, 12, 10, 23];
108
let count = 0;
109
110
bst.handleFrontOrderTraversal((node) => {
111
expect(node.value).toBe(expected[count]);
112
113
count++;
114
});
115
});
116
117
test('bst.handleGetMaxValue should return the maximum node which was in tree', () => {
118
const expected = 23;
119
const result = bst.handleGetMaxValue();
120
121
expect(result).toBe(expected);
122
});
123
124
test('bst.handleGetMinValue should return the minimum node which was in tree', () => {
125
const expected = 1;
126
const result = bst.handleGetMinValue();
127
128
expect(result).toBe(expected);
129
});
130
});
Copied!

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
获取最大值
最近更新 1yr ago
复制链接