data-structures - 非二分木の高さ

Question

必ずしもバイナリではない木の高さを見つける方法はありますか？二分木の高さには多くのアルゴリズムがありますが、非二分木では機能しません。

Answer 1

はいあります。再帰的なアプローチは次のようになります。

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: 
4

編集: 前述のように 3 ではなく 4 を返します

Answer 2

定義はどのツリーでも同じです。ツリーの高さは、そのすべての子の高さ (プラス 1) です。したがって、3 人の子供がいる場合は、3 つすべてをチェックし、最大の + 1 を身長として再帰的に取得します。

Answer 3

一般に、バイナリ ツリーのほとんどのアルゴリズムを非バイナリに拡張できます。

たとえば、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