-
Notifications
You must be signed in to change notification settings - Fork 0
/
AbstractBinaryTree.ts
79 lines (68 loc) · 1.73 KB
/
AbstractBinaryTree.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import IBinaryTree from "../../../types/IBinaryTree";
import AbstractBinaryNode from "./AbstractBinaryNode";
import { FnCompareTwo } from "../../../types/FnCompareTwo";
import { EnumTreeTraversalType } from "../../../types/EnumTreeTraversalType";
/**
*
*/
export default abstract class AbstractBinaryTree<T> implements IBinaryTree<T> {
/**
* Function that checks is node A better
* @default a > b
* @example 5 > 4
* @example 'abc' > 'aba'
*/
protected compare: FnCompareTwo<T> = (a: T, b: T) => a > b;
protected _head: AbstractBinaryNode<T> | null;
protected _length: number;
/**
*
* @param fnCompare
* @protected
*/
protected constructor(fnCompare?: FnCompareTwo<T>) {
if (fnCompare) {
this.compare = fnCompare;
}
this._head = null;
this._length = 0;
}
/**
* Returns nodes count in the entire tree
*/
public length(): number {
return this._length;
}
/**
* Will create new node and place it according to the type of tree rules
*/
public abstract insert(value: T): void;
/**
* Will check if tree has a node with given data
*/
public abstract has(value: T): boolean;
/**
* Will delete node from the tree and restructure it
*/
public abstract delete(value: T): void;
/**
* Max value of the tree
*/
public abstract max(): T;
/**
* Min value of the tree
*/
public abstract min(): T;
/**
* Returns same class instance with new head node
*/
public abstract subtree(value: T): IBinaryTree<T>;
/**
* Returns the highest branch length in the tree
*/
public abstract height(): number;
/**
* In-order/Pre-order/Post-order traversing of the tree
*/
public abstract traverse(type: EnumTreeTraversalType): Array<T>;
}