java - ツリー内のノードに子があるかどうか、または子ノードにアクセスしたかどうかを検出する

Question

ツリー内のノードが存在するか、アクセスされたことを検出するロジックに苦労しています。

ノードを持つツリーがあります (ノードには左右の子ノードがあります)。

ノードで 2 つのことを確認したい: 子ノードがない場合子ノードがある場合それらが訪問されたかどうかを確認したい。

私は現在、見た目が嫌いな大きな状態にあります。単純化できる方法はありますか？

public boolean finished(){
      return right == null && left == null || ((right != null && right.visited && (left != null && left.visited))
}

私はfinished()真になりたい: 右と左のノードが存在しない場合右が存在し、訪問された場合左が存在し、訪問された場合

私も必要だと思うので、訪問ORした右が存在する場合、左はnullですANDAND

私は少し混乱しています:S

score 0 · Accepted Answer

私はこれがあなたが求めているものかもしれないと思います

if( (right == null || right.visited) && ( left == null || left.visited) )

したがって、各子ノードが空であるか、アクセスされている場合は、完了です。

これはケースをカバーします

Right == null; Left == null; 
Right == null; Left.visited; 
Right.visited; Left == null; 
Right.visited; Left.visited;

説明を考えると、これはあなたがチェックしたかったケースだと思います。

score 0 · Accepted Answer

「訪問済み」への最も簡単なアプローチは、ノードに「訪問済み」フラグを設定することです。すべてのフラグをリセットして開始し、ツリートラバーサルを実行して、訪問したときにフラグを設定します。

使用するたびに「visited」フラグをリセットする必要がないようにするには、「flag」を整数にし、visited フラグが必要な場所でスキャンを実行するたびにインクリメントされるグローバルカウンターを保持します。

boolean haveVisited() {
   return visitedFlag == globalVisitedCounter;
}

void markVisited() {
   visitedFlag = globalVisitedCounter;
}

理論的には、ツリー内のすべてのノードをスキャンし、グローバルカウンターがラップしたときにそれらをリセットするロジックが必要ですが、実際には通常は必要ありません。

2 に答える 2