如何計算樹的高度

Question

我想學習DSA並陷入一個問題。

如何計算樹的高度。我的意思是正常的樹，而不是像BT或BST那樣的樹的任何具體實現。

我曾試過谷歌，但似乎每個人都在談論二叉樹，沒有什麼可用於正常的樹。

任何人都可以幫助我重定向到一些頁面或文章來計算樹的高度。

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 |）。