Как рассчитать высоту дерева

Question

Я пытаюсь узнать DSA и застрял в одной проблеме.

Как рассчитать высоту дерева. Я имею в виду нормальное дерево, а не какую-либо конкретную реализацию дерева типа BT или BST.

Я пробовал Google, но кажется, что все говорят о двоичном дереве, и ничего не доступно для нормального дерева.

Может ли кто-нибудь помочь мне перенаправить на какую-либо страницу или статьи, чтобы рассчитать высоту дерева.

Answer 1

Допустим, что типичный узел в вашем дереве представлен как класс Java.

class Node{ 
    Entry entry; 
    ArrayList<Node> children; 
    Node(Entry entry, ArrayList<Node> children){ 
     this.entry = entry; 
     this.children = children; 
    } 
    ArrayList<Node> getChildren(){ 
     return children; 
    } 
} 

Тогда простая Высота Функция может быть -

int getHeight(Node node){ 
    if(node == null){ 
     return 0; 
    }else if(node.getChildren() == null){ 
     return 1; 
    } else{ 
     int childrenMaxHeight = 0; 
     for(Node n : node.getChildren()){ 
      childrenMaxHeight = Math.max(childrenMaxHeight, getHeight(n)); 
     } 
     return 1 + childrenMaxHeight; 
    } 
} 

Тогда вам просто необходимо, чтобы вызвать эту функцию, проходящий корень дерева в качестве аргумента. Поскольку он проходит весь узел ровно один раз, время выполнения O (n).

Answer 2

В случае «нормального дерева» вы можете рекурсивно вычислять высоту дерева аналогично бинарному дереву, но здесь вам придется рассматривать всех детей на узле, а не только два.

Answer 3

Чтобы найти высоту дерева, итерация BFS будет работать нормально.

отредактированной форме Википедия:

Breadth-First-Search(Graph, root): 

    create empty set S 
    create empty queues Q1, Q2  

    root.parent = NIL 

    height = -1 

    Q1.enqueue(root)      
    while Q1 is not empty: 

     height = height + 1 
     switch Q1 and Q2 

     while Q2 is not empty: 
      for each node n that is adjacent to current: 
       if n is not in S: 
        add n to S 
        n.parent = current 
        Q1.enqueue(n) 

Вы можете видеть, что добавление другой очереди позволяет мне знать, какой уровень дерева. Итерирует для каждого уровня и для каждого режима на этом уровне.

Это способ дискредитации (напротив рекурсивного). Поэтому вам тоже не нужно беспокоиться об этом.

Время работы O (| V | + | E |).