【TypeScriptで学ぶデータ構造】木（二分木）

木

一つの要素に複数の要素が紐付き、さらに紐づいた要素が複数の要素と紐付く、という形で階層が深くなるほど枝分かれしていく構造です。
（一つ一つの要素をノードという）

具体的な例はHTMLのDOMツリー

各html要素がノードとして扱われ、タグの階層関係に基づいて木構造が生成されます。
学び初めは木構造て何？といった感じでしたがとても身近ですね

二分木を再現したクラス

binary.ts

//二分木のノードクラス
class TreeNode<T> {
	public value: T;
	public left: TreeNode<T> | null = null;
	public right: TreeNode<T> | null = null;

	constructor(value: T) {
		this.value = value;
	}
}

//二分木を表現したクラス
class BinarySearchTree<T> {
	private root: TreeNode<T> | null = null;

	//ノードの挿入
	public insert(value: T): void {
		const newNode = new TreeNode(value);
		if (this.root === null) {
			this.root = newNode;
		} else {
			this.insertNode(this.root, newNode);
		}
	}

	//ノードの挿入を行うメソッド（再帰的に適切な位置を探す仕様）
	private insertNode(node: TreeNode<T>, newNode: TreeNode<T>): void {
		if (newNode.value < node.value) {
			if (node.left === null) {
				node.left = newNode;
			} else {
				this.insertNode(node.left, newNode);
			}
		} else {
			if (node.right === null) {
				node.right = newNode;
			} else {
				this.insertNode(node.right, newNode);
			}
		}
	}

	//ノードの探索を行うメソッド
	public search(value: T): boolean {
		return this.searchNode(this.root, value);
	}

	private searchNode(node: TreeNode<T> | null, value: T): boolean {
		if (node === null) {
			return false;
		}
		if (value === node.value) {
			return true;
		} else if (value < node.value) {
			return this.searchNode(node.left, value);
		} else {
			return this.searchNode(node.right, value);
		}
	}

	//最小値を取得するメソッド
	public findMin(): T | null {
		return this.findMinNode(this.root);
	}

	private findMinNode(node: TreeNode<T> | null): T | null {
		if (node === null) {
			return null;
		} else if (node.left === null) {
			return node.value;
		} else {
			return this.findMinNode(node.left);
		}
	}

	//最大値を取得するメソッド
	public findMax(): T | null {
		return this.findMaxNode(this.root);
	}

	private findMaxNode(node: TreeNode<T> | null): T | null {
		if (node === null) {
			return null;
		} else if (node.right === null) {
			return node.value;
		} else {
			return this.findMaxNode(node.right);
		}
	}
	//トラバース（全ノードを一回ずつ全て探索する処理です）
	public inOrderTraversal(): void {
		this.inOrder(this.root);
	}

	private inOrder(node: TreeNode<T> | null): void {
		if (node !== null) {
			this.inOrder(node.left);
			console.log(node.value);
			this.inOrder(node.right);
		}
	}
}

// 使用例
const bst = new BinarySearchTree<number>();

bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);

console.log("トラバース");
bst.inOrderTraversal(); // 20, 30, 40, 50, 60, 70, 80が表示される

console.log("60を探した結果！", bst.search(60)); // true
console.log("25を探した結果！", bst.search(25)); // false

console.log("最小値", bst.findMin()); // 20
console.log("最大値", bst.findMax()); // 80