非二叉树高度

Question

有没有方法可以找到不一定是二进制的树的高度？对于二叉树的高度有许多算法，但它们都不适用于非二元树。

Answer 1

定义对于任何树都是一样的。树的高度是任何一个孩子的高度（加上一个）。所以如果你有三个孩子，你可以检查他们所有三个孩子，递归地把最大的+1作为你的身高。

Answer 2

通常，您可以将二叉树的大部分算法扩展为非二进制。

例如，对于2-树：

h(node) = max(h(left-child-of(node)) , h(right-child-of(node)))+1 

其可以扩展到：

h(node) = max(h(for-all-child-of(node)) + 1 

Answer 3

是的，有。递归方法可以是这样的：

public class TreeNode<T>{ 
    private List<TreeNode<T>> children = new ArrayList<TreeNode<T>>(); 
    private T data = null; 

    public TreeNode(T data){ 
     this.data = data; 
    }  

    public List<TreeNode<T>> getChildren(){ 
     return children; 
    } 

    public void setChild(TreeNode<T> children){ 
     this.children.add(children); 
    } 

    public Integer getHeight(TreeNode<T> root){ 
     if(root == null) return 0; 
     Integer h=0; 

     for(TreeNode<T> n : root.getChildren()){ 
      h = Math.max(h, getHeight(n)); 
     } 
     return h+1; 
    } 
} 

测试：

public static void main(String[] args){ 
    TreeNode<Integer> root = new TreeNode<Integer>(50); 
    TreeNode<Integer> c1 = new TreeNode<Integer>(100); 
    TreeNode<Integer> c2= new TreeNode<Integer>(10); 
    TreeNode<Integer> c3 = new TreeNode<Integer>(-5); 
    TreeNode<Integer> c4 = new TreeNode<Integer>(0); 
    TreeNode<Integer> c5 = new TreeNode<Integer>(33); 
    TreeNode<Integer> c6 = new TreeNode<Integer>(1); 
    TreeNode<Integer> c7 = new TreeNode<Integer>(2); 
    TreeNode<Integer> c8 = new TreeNode<Integer>(3); 
    TreeNode<Integer> c9 = new TreeNode<Integer>(300); 
    TreeNode<Integer> c10 = new TreeNode<Integer>(350); 

    root.setChild(c1); 
    root.setChild(c2); 
    c2.setChild(c3); 
    c3.setChild(c4); 
    c3.setChild(c5); 
    c3.setChild(c6); 
    c3.setChild(c7); 
    c3.setChild(c8); 

    c1.setChild(c9); 
    c1.setChild(c10); 

    System.out.print("Pre order: \n"); 
    root.dfs(root, 0); 
    System.out.print("\nPost order: \n"); 
    root.dfs(root, 1); 
    System.out.print("\nBFS: \n"); 
    root.bfs(root); 
    System.out.println(); 
    System.out.print("\nHeigth: \n"); 
    System.out.println(root.getHeight(root)); 
} 

结果：

Heigth: 
3