如何计算树的高度

我想学习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

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

如何计算树的高度

回答

相关问题