如何計算樹的高度

我想學習DSA並陷入一個問題。如何計算樹的高度

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

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

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

來源

2017-02-16 Abhash786

您的問題缺乏很多背景，有哪些工具和數據可用？否則答案可能是：拿一把梯子和一卷捲尺。 – Piou

請參閱此鏈接，希望你找到你的答案，http://stackoverflow.com/questions/13476508/non-binary-tree-height – soewin

二進制或n-ary沒有太大的區別找到高度。 –

假設樹中的典型節點表示爲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）。

來源

2017-02-16 16:33:23

在「正常樹」的情況下，您可以以與二叉樹類似的方式遞歸計算樹的高度，但在這裏您將不得不考慮節點上的所有孩子而不是兩個。

來源

2017-02-16 11:51:11 handle1605

要找到樹高度，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 |）。

來源

2017-02-17 03:02:26 Dolev

這似乎像一個樹深度查找解決方案 –

@ elad.chen它是。那不是你要找的東西嗎？ – Dolev

樹的高度和樹的深度有很大的不同。 –

如何計算樹的高度

回答

相關問題