Как это работает

1. База: пустой узел — ничего не делаем
2. Обрабатываем текущий узел (выводим ключ)
3. Рекурсивно вызываем для левого поддерева
4. Рекурсивно вызываем для правого поддерева

Inorder и postorder — те же три шага, но в другом порядке (см. таблицу на след. слайдах).

В tree.cpp уже есть bstPreOrder — скопируйте логику, заменив тип узла на BinNode.

Пример: массив из 7 элементов

i:     0   1   2   3  4  5   6
key:  10   5  15   3  7 -1  20

• Индекс 0 → корень 10
• Дети 10: индексы 1 и 2 → 5 и 15
• Индекс 5 = -1 → нет левого ребенка у 15
• Индекс 6 → правый ребенок 15 = 20

Так же устроен массив в куче (семинар 4.10), но там другой смысл ключей.

lib/treeAlgs/binaryTree.cpp — дописать построение, обходы и освобождение памяти

buildByLevelOrder(keys, n):
  if n <= 0: return nullptr
  return buildByIndex(keys, n, 0)

buildByIndex(keys, n, i):
  if i >= n: return nullptr
  if keys[i] == -1: return nullptr

  node = new BinNode(keys[i])
  node.left  = buildByIndex(keys, n, 2*i + 1)
  node.right = buildByIndex(keys, n, 2*i + 2)
  return node

binPreorder(node, out):
  if !node: return
  push node.key → left → right

binInorder(node, out):
  if !node: return
  left → push node.key → right

binPostorder(node, out):
  left → right → push node.key

binLevelOrder(root, out):
  queue.push(root)
  while !queue.empty():
    cur = queue.front(); queue.pop()
    push cur.key
    if cur.left: queue.push(cur.left)
    if cur.right: queue.push(cur.right)

binFree(root):
  left → right → delete root

task_4.09.01/task40901.cpp

runLevelOrderTreeTask(keys, n, output):
  if !output or n < 0: return 1

  root = buildByLevelOrder(keys, n)

  preorder = []
  inorder = []
  postorder = []
  levelorder = []

  binPreorder(root, preorder)
  binInorder(root, inorder)
  binPostorder(root, postorder)
  binLevelOrder(root, levelorder)

  output << formatTraversalLine("Preorder", preorder)
  output << formatTraversalLine("Inorder", inorder)
  output << formatTraversalLine("Postorder", postorder)
  output << formatTraversalLine("Level-order", levelorder)

  binFree(root)
  return 0

task_4.09.02/task40902.cpp

buildBstAndCheckInorder(keys, n, output):
  if !keys or !output or n < 0: return 1

  root = nullptr
  for i in 0..n-1:
    root = bstInsert(root, keys[i])

  values = []
  bstInOrder(root, values)

  output << "Inorder: " + join(values)

  if isStrictlyIncreasing(values):
    output << "Sorted inorder: YES"
  else:
    output << "Sorted inorder: NO"

  bstFree(root)
  return 0

task_4.09.03/task40903.cpp

runBstSearchMetrics(keys, n, queries, q, output):
  if bad pointers or n < 0 or q < 0: return 1

  root = nullptr
  for key in keys:
    root = bstInsert(root, key)

  total = 0
  for query in queries:
    comparisons = 0
    found = bstFindWithComparisons(root, query, &comparisons)
    total += comparisons

    output << query
           << ": found=" << (found ? "YES" : "NO")
           << " comparisons=" << comparisons

  output << "Total comparisons: " << total
  bstFree(root)
  return 0

task_4.09.04/task40904.cpp

sortKeysCopy(src, n, dst):
  скопировать src[0..n-1] в dst
  for i = 1..n-1:
    x = dst[i]
    j = i - 1
    while j >= 0 and dst[j] > x:
      dst[j+1] = dst[j]
      --j
    dst[j+1] = x

bstHeightAfterInsertions(keys, n):
  root = nullptr
  for i = 0..n-1:
    root = bstInsert(root, keys[i])
  h = bstHeight(root)
  bstFree(root)
  return h

main/task:
  read n and keys

  sorted = new int[n]
  sortKeysCopy(keys, n, sorted)

  hOriginal = bstHeightAfterInsertions(keys, n)
  hSorted = bstHeightAfterInsertions(sorted, n)

  print "Height original: ..."
  print "Height sorted: ..."
  delete[] sorted

Input format: n followed by n integer keys for BST insertions.
5
3 1 4 2 5
Output:
Height original: 3
Height sorted: 5

Каждый new BinNode в buildByLevelOrder нужно освободить через binFree.

Аналогично bstFree для БДП.

• Вызывайте в конце run*Task
• Не освобождайте дважды
• После binFree(root) не используйте root

Что делать

1. Имя теста → файл test_task_40901.cpp
2. Сравните actual и expected
3. Часто ошибка в порядке обхода или пропущенном узле
4. Исправили → снова ./01.build.sh и ./03.run_tests.sh

03.run_tests.sh = ctest --output-on-failure из папки build/.