Медианные узлы в двоичном дереве

У меня был экзамен со следующим вопросом, на который я не смог ответить: у нас есть двоичное дерево, в котором каждый узел имеет определенную высоту (снизу) и определенную глубину (от корня). Оба начинаем считать с нуля; Например: для дерева с корнем и единственным дочерним элементом глубина дочернего элемента будет равна 1, а высота - 0.

Найдите рекурсивный алгоритм, который печатает все средние узлы, то есть когда высота узла равна его глубине.

Была дана подсказка: укажите d (глубину) в качестве аргумента функции и высоту в качестве возвращаемого значения ...


recursion tree binary-tree tree-traversal
person Gene Frank    schedule 13.11.2012    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Реализация Python, где узел - это объект с атрибутом children.

def R(node, d):
  if not node.children: # No children, leaf node
    height = 0
  else:
    height = max( R(child, d+1) for child in node.children ) + 1
  if height == d:
    print node  # Or some node.id
  return height

R(root, 0)  # Call with a root node
person Ante    schedule 14.11.2012

arrow_upward
0
arrow_downward 

void medianInTree(class tree* root, int depth, int height)
{

    if(root)
    {
         if(height == depth)
             cout<<"   "<<root->data;
         medianInTree(root->left, depth-1, height+1);
         medianInTree(root->right, depth-1, height+1);
    }
}

Передайте глубину как высоту дерева (учитывая высоту корня = 1).

person instance    schedule 28.05.2015