index.ts
import type { TreeNode, TreeTraversalOrder } from './models'; import { inorderTraverse, levelorderTraverse, postorderTraverse, preorderTraverse, } from './traversals'; /** * 인자로 받은 순회 타입에 따라 트리 노드를 순회하는 함수입니다. 기본 탐색 알고리즘은 레벨 탐색입니다. * * 재귀로 작동하기 때문에 트리의 깊이가 너무 깊어지면 OOM이 발생할 수 있습니다. * * @example * ```ts * const tree: TreeNode<{ id: string }> = { * id: 'root', * children: [{ * id: '1-1', * children: [{ * id: '2-1' * }, { * id: '2-2' * }] * }, { * id: '1-2', * children: [], * }], * }; * * traverse(tree, (v) => console.log(v.id)); * // 1-1 * // 1-2 * // 2-1 * // 2-2 * ``` */ export function traverse<T>( node: TreeNode<T>, fn: (node: TreeNode<T>) => void, order: TreeTraversalOrder = '레벨' ) { switch (order) { case '전위': return preorderTraverse(node, fn); case '후위': return postorderTraverse(node, fn); case '중위': return inorderTraverse(node, fn); case '레벨': return levelorderTraverse(node, fn); } } /** * 트리 내부에서 원하는 노드 원본을 가져옵니다. 조건에 일치하는 노드가 여러 개라면 그 중 가장 첫 번째 방문 노드를 반환합니다. (기본 알고리즘은 레벨 순회입니다) * * 만약 조건에 일치하는 노드가 없는 경우 null을 반환합니다. * * @example * ```ts * const node = findNode(tree, v => v.children.length === 0); * ``` */ export function findNode<T>( node: TreeNode<T>, matcher: (node: TreeNode<T>) => boolean, order: TreeTraversalOrder = '레벨' ) { let result: TreeNode<T> | null = null; traverse( node, (v) => { if (matcher(v) === true && result == null) { result = v; } }, order ); return result; } /** * 인자로 주어진 노드의 부모 노드 원본을 반환합니다. */ export function findParent<T>( node: TreeNode<T>, matcher: (node: TreeNode<T>) => boolean, order: TreeTraversalOrder = '레벨' ) { return findNode( node, (v) => { return v.children.find(matcher) != null; }, order ); } function preorderMap<T>( node: TreeNode<T>, mapper: (node: TreeNode<T>) => TreeNode<T> ): TreeNode<T> { return { ...mapper(node), children: node.children.map((child) => preorderMap(child, mapper)), }; } /** * 트리를 전위 순회하며 각 노드에 map 연산을 수행합니다. */ export function replaceNode<T>(node: TreeNode<T>, mapper: (node: TreeNode<T>) => TreeNode<T>) { const newNode = { ...node }; return preorderMap(newNode, mapper); } export * from './models';
models.ts
export type TreeNode<T> = { children: TreeNode<T>[]; } & T; export type TreeTraversalOrder = '전위' | '후위' | '중위' | '레벨';
traversals.ts
import type { TreeNode } from './models'; export function preorderTraverse<T>(node: TreeNode<T>, fn: (node: TreeNode<T>) => void) { fn(node); node.children.forEach((child) => preorderTraverse(child, fn)); } export function postorderTraverse<T>(node: TreeNode<T>, fn: (node: TreeNode<T>) => void) { node.children.forEach((child) => postorderTraverse(child, fn)); fn(node); } export function inorderTraverse<T>(node: TreeNode<T>, fn: (node: TreeNode<T>) => void) { if (node.children.length > 0) { inorderTraverse(node.children[0], fn); } fn(node); if (node.children.length > 1) { inorderTraverse(node.children[1], fn); } } export function levelorderTraverse<T>(node: TreeNode<T>, fn: (node: TreeNode<T>) => void) { const nodes: TreeNode<T>[] = []; if (node !== null) { nodes.push(node); } while (nodes.length > 0) { const node = nodes.shift()!; fn(node); node.children.forEach((child) => nodes.push(child)); } }
tree.test.ts
import { type TreeNode } from './models'; import { findNode, findParent, replaceNode, traverse } from '.'; const tree: TreeNode<{ id: string }> = { id: 'root', children: [ { id: '1-1', children: [ { id: '2-1', children: [], }, { id: '2-2', children: [], }, ], }, { id: '1-2', children: [], }, ], }; describe('traverse', () => { it('travere 함수는 인자로 받은 트리의 모든 노드를 전위 순회한다', function () { const logSpy = jest.spyOn(console, 'log'); traverse( tree, (node) => { console.log(node.id); }, '전위' ); expect(logSpy.mock.calls[0][0]).toBe('root'); expect(logSpy.mock.calls[1][0]).toBe('1-1'); expect(logSpy.mock.calls[2][0]).toBe('2-1'); expect(logSpy.mock.calls[3][0]).toBe('2-2'); expect(logSpy.mock.calls[4][0]).toBe('1-2'); logSpy.mockRestore(); }); it('travere 함수는 인자로 받은 트리의 모든 노드를 후위 순회한다', function () { const logSpy = jest.spyOn(console, 'log'); traverse( tree, (node) => { console.log(node.id); }, '후위' ); expect(logSpy.mock.calls[0][0]).toBe('2-1'); expect(logSpy.mock.calls[1][0]).toBe('2-2'); expect(logSpy.mock.calls[2][0]).toBe('1-1'); expect(logSpy.mock.calls[3][0]).toBe('1-2'); expect(logSpy.mock.calls[4][0]).toBe('root'); logSpy.mockRestore(); }); it('travere 함수는 인자로 받은 트리의 모든 노드를 중위 순회한다', function () { const logSpy = jest.spyOn(console, 'log'); traverse( tree, (node) => { console.log(node.id); }, '중위' ); expect(logSpy.mock.calls[0][0]).toBe('2-1'); expect(logSpy.mock.calls[1][0]).toBe('1-1'); expect(logSpy.mock.calls[2][0]).toBe('2-2'); expect(logSpy.mock.calls[3][0]).toBe('root'); expect(logSpy.mock.calls[4][0]).toBe('1-2'); logSpy.mockRestore(); }); it('travere 함수는 인자로 받은 트리의 모든 노드를 레벨 순회한다', function () { const logSpy = jest.spyOn(console, 'log'); traverse(tree, (node) => { console.log(node.id); }); expect(logSpy.mock.calls[0][0]).toBe('root'); expect(logSpy.mock.calls[1][0]).toBe('1-1'); expect(logSpy.mock.calls[2][0]).toBe('1-2'); expect(logSpy.mock.calls[3][0]).toBe('2-1'); expect(logSpy.mock.calls[4][0]).toBe('2-2'); logSpy.mockRestore(); }); }); describe('findNode', () => { it('findNode 함수는 인자로 받은 트리 내에서 matcher와 일치하는 노드를 찾아낸다', function () { const node = findNode(tree, (node) => node.id === '2-1'); expect(node).toStrictEqual({ id: '2-1', children: [], }); }); it('findNode 함수는 인자로 받은 트리 내에서 matcher와 일치하는 노드가 없는 경우 null을 반환한다', function () { const node = findNode(tree, (node) => node.id === '3-100'); expect(node).toBeNull(); }); }); describe('replaceNode', () => { it('replaceNode 함수는 인자로 받은 트리 내 모든 노드에 mapper를 적용하여 새로운 트리를 만들어낸다', function () { const newTree = replaceNode(tree, (node) => ({ ...node, id: 'test', })); expect(tree).toBe(tree); expect(newTree).not.toBe(tree); expect(newTree).toStrictEqual({ id: 'test', children: [ { id: 'test', children: [ { id: 'test', children: [], }, { id: 'test', children: [], }, ], }, { id: 'test', children: [], }, ], }); }); }); describe('findParent', () => { it('findParent 함수는 인자로 받은 트리 내에서 matcher와 일치하는 노드의 부모 노드를 반환한다', function () { const node = findParent(tree, (node) => node.id === '2-1'); expect(node).toStrictEqual({ id: '1-1', children: [ { id: '2-1', children: [], }, { id: '2-2', children: [], }, ], }); }); });