как написать бинарное дерево поиска generic через
set?
class TreeNode<T> {
constructor(public value: T, public left: TreeNode<T> = null, public right: TreeNode<T> = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
class BinarySearchTree<T> {
constructor(
public root: TreeNode<T> = null
) {}
add(value: T): boolean {
if (this.root === null) {
this.root = new TreeNode(value);
return true;
} else {
const searchTree = (node: TreeNode<T>): boolean => {
if (value < node.value) {
if (node.left === null) {
node.left = new TreeNode(value);
return true;
} else if (node.left != null) {
return searchTree(node.left);
}
} else if (value > node.value) {
if (node.right === null) {
node.right = new TreeNode(value);
return true;
} else if (node.right != null) {
return searchTree(node.right);
}
} else {
return false;
}
};
return searchTree(this.root);
}
}
findMin(): T {
let current: TreeNode<T> = this.root;
while (current.left !== null) {
current = current.left;
}
return current.value;
}
findMax(): T {
let current = this.root;
while (current.right !== null) {
current = current.right;
}
return current.value;
}
find(data: T): TreeNode<T> {
let current: TreeNode<T> = this.root;
while (current.value !== data) {
if (data < current.value) {
current = current.left;
} else {
current = current.right;
}
if (current === null) {
return null;
}
}
return current;
}
isPresent(data: T): boolean {
let current = this.root;
while (current) {
if (data === current.value) {
return true;
}
if (data < current.value) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
remove(data: T): void {
const removeNode = (node: TreeNode<T>, data: T) => {
if (node == null) {
return null;
}
if (data == node.value) {
if (node.left == null && node.right == null) {
return null;
}
if (node.left == null) {
return node.right;
}
if (node.right == null) {
return node.left;
}
let tempNode = node.right;
while (tempNode.left !== null) {
tempNode = tempNode.left;
}
node.value = tempNode.value;
node.right = removeNode(node.right, tempNode.value);
return node;
} else if (data < node.value) {
node.left = removeNode(node.left, data);
return node;
} else {
node.right = removeNode(node.right, data);
return node;
}
};
this.root = removeNode(this.root, data);
}
isBalanced(): boolean {
return this.findMinHeight() >= this.findMaxHeight() - 1;
}
findMinHeight(node: TreeNode<T> = this.root): number {
if (node == null) {
return -1;
}
let left = this.findMinHeight(node.left);
let right = this.findMinHeight(node.right);
if (left < right) {
return left + 1;
} else {
return right + 1;
}
}
findMaxHeight(node: TreeNode<T> = this.root): number {
if (node == null) {
return -1;
}
let left = this.findMaxHeight(node.left);
let right = this.findMaxHeight(node.right);
if (left > right) {
return left + 1;
} else {
return right + 1;
}
}
inOrder(): Array<T> {
if (this.root == null) {
return null;
} else {
var result = new Array();
const traverseInOrder = (node: TreeNode<T>) => {
node.left && traverseInOrder(node.left);
result.push(node.value);
node.right && traverseInOrder(node.right);
};
traverseInOrder(this.root);
return result;
}
}
levelOrder(): Array<T> {
let result = [];
let Q = [];
if (this.root != null) {
Q.push(this.root);
while (Q.length > 0) {
let node = Q.shift();
result.push(node.data);
if (node.left != null) {
Q.push(node.left);
}
if (node.right != null) {
Q.push(node.right);
}
}
return result;
} else {
return null;
}
}
invert(): void {
function invert(node: TreeNode<T>) {
if (!node.left && !node.right) {
return;
}
invert(node.left);
invert(node.right);
const tempNode = node.right;
node.right = node.left;
node.left = tempNode;
}
invert(this.root);
}
elementHeight(data: T): number {
function findHeight(data: T, tree: TreeNode<T>, height = -1): number {
if (!tree) {
return height;
}
const tempHeight = tree.value === data || height >= 0 ? height + 1 : height;
return Math.max(findHeight(data, tree.left, tempHeight), findHeight(data, tree.right, tempHeight));
}
return findHeight(data, this.root);
}
}
