非二叉树高 [英] Non-binary tree height

问题描述

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

解决方案

有。递归方法可以是：

  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整数getHeight（TreeNode< T>根）{
 if（root == null）return 0; 
整数h = 0; （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：\\\
）; 
 root.dfs（root，0）; 
 System.out.print（\\\
Post order：\\\
）; 
 root.dfs（root，1）; 
 System.out.print（\\\
BFS：\\\
）; 
 root.bfs（root）; 
 System.out.println（）; 
 System.out.print（\\\
Heigth：\\\
）; 
 System.out.println（root.getHeight（root））; 
} 
  

结果：

  Heigth：
 3 
  

Is there a way to find the height of a tree which is not necessarily binary? There are many algorithms for the height of a binary tree but none of them will work for a non-binary.

解决方案

Yes, there is. A recursive approach could be something like:

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;
    }
}

Test:

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));
}

Result:

Heigth: 
3

这篇关于非二叉树高的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！