Найти высоту заданного узла дерева

224

19 февраля 2017, 08:15

Есть для высоты дерева:

public static void HeigthTree(Node t, ref int count, ref int heigth)
{
      if (t!=null) // если текущий узел не пустой
      {
             if (count > heigth) //и длина пути от корня до текущего узла больше высоты дерева, то
                {
                      heigth=count; // полагаем в качестве высоты дерева длину пути до текущего узла
                }
             count++; // в любом случае увеличиваем длину пути от корня до текущего узла
             HeigthTree(t.left, ref count, ref heigth); //обходим левое поддерево
             HeigthTree(t.rigth, ref count, ref heigth); //обходим правое поддерево
             count--; //после чего уменьшаем длину пути от корня до текущего узла
      }
}

Высота узла-это длина пути от этого узла к самому нижнему листу.Вопрос,как реализовать эту самую высоту...

Answer 1

Слишком много параметров. Попробуйте следующую рекурсию:

static int height(Node node) {
    if(node == null) return 0;
    //находим высоту правой и левой ветки, и из них берем максимальную
    //todo если дерево не бинарное, то для поиска макс ветки реализовать цикл
    return 1 + Math.max(height(node.left), height(node.right));
}

Так как само дерево также является экземляром Node, то для нахождения высоты дерева: