تحديد أنواع هياكل الأشجار

نوع عقدة الشجرة

type TreeNode<T> = {
  value: T;
  children: TreeNode<T>[];
};
const leaf: TreeNode<number> = { value: 1, children: [] };
console.log(leaf.value);

بناء شجرة صغيرة

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const tree: TreeNode<string> = {
  value: "root",
  children: [
    { value: "a", children: [] },
    { value: "b", children: [] }
  ]
};
console.log(tree.children.length);

التداخل إلى عمق أكبر

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const tree: TreeNode<number> = {
  value: 1,
  children: [
    { value: 2, children: [{ value: 4, children: [] }] },
    { value: 3, children: [] }
  ]
};
console.log(tree.children[0].children[0].value);

جمع كل القيم

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function sum(node: TreeNode<number>): number {
  let total = node.value;
  for (const child of node.children) total += sum(child);
  return total;
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }, { value: 3, children: [] }] };
console.log(sum(t));

عدّ العقد

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function count<T>(node: TreeNode<T>): number {
  return 1 + node.children.reduce((acc, c) => acc + count(c), 0);
}
const t: TreeNode<string> = { value: "r", children: [{ value: "a", children: [] }] };
console.log(count(t));

العثور على أقصى عمق

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function depth<T>(node: TreeNode<T>): number {
  if (node.children.length === 0) return 1;
  return 1 + Math.max(...node.children.map(depth));
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [{ value: 3, children: [] }] }] };
console.log(depth(t));

جمع كل القيم

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function flatten<T>(node: TreeNode<T>): T[] {
  return [node.value, ...node.children.flatMap(flatten)];
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }, { value: 3, children: [] }] };
console.log(flatten(t));

البحث في الشجرة

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function find<T>(node: TreeNode<T>, pred: (v: T) => boolean): TreeNode<T> | null {
  if (pred(node.value)) return node;
  for (const c of node.children) {
    const hit = find(c, pred);
    if (hit) return hit;
  }
  return null;
}
const t: TreeNode<number> = { value: 1, children: [{ value: 5, children: [] }] };
console.log(find(t, v => v === 5)?.value);

تحويل الشجرة

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function mapTree<T, U>(node: TreeNode<T>, fn: (v: T) => U): TreeNode<U> {
  return { value: fn(node.value), children: node.children.map(c => mapTree(c, fn)) };
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }] };
console.log(mapTree(t, x => x * 100).value);

الأشجار تمثّل بيانات حقيقية

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
type FileTree = TreeNode<string>;
const fs: FileTree = { value: "/", children: [{ value: "home", children: [] }] };
console.log(fs.value, fs.children[0].value);

الأوراق والفروع

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function isLeaf<T>(node: TreeNode<T>): boolean {
  return node.children.length === 0;
}
console.log(isLeaf({ value: 1, children: [] }));

تحقق سريع: بنى الأشجار

مراجعة: كتابة أنواع بنى الأشجار

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }] };
console.log(t.children[0].value);