条件を使用しないでバイナリツリーに葉を数える

Question

ノードに左右の子がないかどうかをチェックすることで再帰的な葉の数を数える汎用アルゴリズムがあることは知っています。しかし、私は多相コードを使って同じコードを書いて、可能かどうかをチェックしたい、今は私が葉の状態をチェックしているが、その情報は現在のノードに完全に依存しない。

import java.util.*; 
import java.lang.*; 
import java.io.*; 


abstract class Tree { 
    abstract int count(); 
} 

class Empty extends Tree { 
    public int count() { 
    return 0; 
    } 
} 

class NonEmpty extends Tree { 

    private final int val; 
    private final Tree left; 
    private final Tree right; 

    public NonEmpty(int val, Tree left, Tree right) { 
    this.val = val; 
    this.left = left; 
    this.right = right; 
    } 

    public int count() { 
    return left.count() + right.count(); 
    } 
} 

public class Main { 
    public static void main(String[] args) throws java.lang.Exception { 
    Tree t = new NonEmpty(5, new Empty(), new Empty()); 
    System.out.println(t.count()); // 0 but should be 1 
    } 
} 

Update 1の私は、私は多くの批判を得た私の同僚のいくつかでこのアイデアを議論し

、これは悪い考えですか？私の意見は私にはきれいだと感じている、私は他人の意見を聞きたい。

Answer 1

最後に固定ソリューション：

interface Tree { 
    Tree NULL_TREE = new NullTree(); 

    int countLeafs(); 
    Tree left(); 
    Tree right(); 
} 

class NullTree implements Tree { 
    @Override 
    public int countLeafs() { 
     return 0; 
    } 

    @Override 
    public Tree left() { 
     return this; 
    } 

    @Override 
    public Tree right() { 
     return this; 
    } 
} 

class Leaf implements Tree { 
    private int val; 

    public Leaf(int val) { 
     this.val = val; 
    } 

    public int countLeafs() { 
     return 1; 
    } 

    @Override 
    public Tree left() { 
     return NULL_TREE; 
    } 

    @Override 
    public Tree right() { 
     return NULL_TREE; 
    } 
} 

class Node implements Tree { 

    private final int val; 
    private final Tree left; 
    private final Tree right; 

    public Node(int val, Tree left, Tree right) { 
     this.val = val; 
     this.left = left; 
     this.right = right; 
    } 

    @Override 
    public int countLeafs() { 
     return left.countLeafs() + right.countLeafs(); 
    } 

    @Override 
    public Tree left() { 
     return left; 
    } 

    @Override 
    public Tree right() { 
     return right; 
    } 
} 

public class Main { 
    public static void main(String[] args) throws java.lang.Exception { 
     Tree t = new Node(5, new Leaf(10), new Leaf(20)); 
     System.out.println(t.countLeafs()); 
    } 
} 

Answer 2

変更

public int count() { 
    return left.count() + right.count(); 
} 

public int count() { 
    return Math.max(1, left.count() + right.count()); 
} 

にこれは条件式を含むKonstantin's original answerに似ていますleft.count() + right.count()が0であれば、それは葉であり、その数は1

する必要があります

（編集：余りにも多くの警告があり、それを排除することは価値よりも複雑になるため、残りは削除しました）

Answer 3

まあ、friendlydog @が示唆したように、のは、支店と呼ばれる別のクラスを持ってみましょう：でもよりよい解決策については

abstract class Tree { 
    abstract int count(); 
} 

class Empty extends Tree { 
    public int count() { 
    return 0; 
    } 
} 

class NonEmpty extends Tree{ 
    private final int val; 

    public NonEmpty(int val){ 
     this.val=val; 
    } 

    public int count(){ 
     return 1; 
    } 
} 

class Branch extends Tree { 

    private final int val; 
    private final Tree left; 
    private final Tree right; 

    public Branch(int val, Tree left, Tree right) { 
    this.val = val; 
    this.left = left; 
    this.right = right; 
    } 


    public int count() { 
    return 1+left.count() + right.count(); // to count all non-empty nodes 
    //return left.count()+right.count(); //to count only leaves; 
    } 
} 

public class Main { 
    public static void main(String[] args) throws java.lang.Exception { 
    Tree t = new Branch(5, new Empty(), new Empty()); 
    System.out.println(t.count()); // now it's 1 :) 
    } 
} 

を、あなたは2つの以上のコンストラクタを持つことができますBranch：1つはvalと、leftとrightはEmptyで、もう1つはvalで、もう1つはEmptyleft、パディングのみright。

Answer 4

これまでの回答では、リーフまたはの両方の子ノードがあると仮定しています。左と右の子です。ここで行方不明の子供のいずれかを扱うことができるのアプローチがあります：

class Tree { 
    final Optional<Tree> left; 
    final Optional<Tree> right; 

    Tree(Optional<Tree> left, Optional<Tree> right) { 
     this.left = left; 
     this.right = right; 
    } 

    int leafCount() { 
     return left.map(Tree::leafCount) 
       .map(l -> right.map(Tree::leafCount).map(r -> l + r).orElse(l)) 
       .orElse(right.map(Tree:leafCount).orElse(1)); 

    } 
} 

Optional.orElse()は

Answer 5

は、ノードの種類を決定するために、余分な機能や余分な変数を追加しています...しかし変装ifによく似ています。

これは、子供が葉であるように2つの空ノードを有するNonEmptyノードを仮定し、他の条件は葉ではないと考える。

abstract class Tree { 
    abstract int count(); 
    abstract int type(); 
} 

class Empty extends Tree { 
    public int type() { 
     return 1; 
    } 

    public int count() { 
     return 0; 
    } 
} 

class NonEmpty extends Tree { 

    private final int val; 
    private final Tree left; 
    private final Tree right; 
    private final int type; 

    public NonEmpty(int val, Tree left, Tree right) { 
     this.val = val; 
     this.left = left; 
     this.right = right; 
     this.type = left.type() * right.type(); 
    } 

    public int type() { 
     return 0; 
    } 

    public int count() { 
     return (1-this.type) * (left.count() + right.count()) + this.type; 
    } 

}