java - 检测树中的节点是否有子节点或子节点已被访问

Question

我正在努力解决检测树中节点是否存在或已被访问的逻辑。

我有一棵带节点的树（一个节点有一个左右子节点）。

我想检查一个节点上的两件事：如果没有子节点如果有子节点我想检查它们是否被访问过。

我目前有一个很大的条件，我讨厌它的样子。有没有办法可以简化它？

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

我想finished()是真的：如果一个左右节点不存在如果一个右节点存在并且已经被访问如果一个左节点存在并且已经被访问

我想我也需要一个OR所以如果存在一个权利，那么AND访问的AND左边是空的

我有点困惑：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

“已访问”的最简单方法是在您的节点中放置“已访问”标志。重置所有标志以开始，然后进行树遍历并在访问它们时设置标志。

为避免在每次使用后都必须重置“已访问”标志，请将“标志”设为整数，并保留一个全局计数器，每次您在需要访问标志的地方进行扫描时，该计数器都会递增：

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

void markVisited() {
   visitedFlag = globalVisitedCounter;
}

理论上，您确实需要有逻辑来扫描树中的所有节点并在全局计数器换行时重置它们，但实际上通常不需要这样做。

2 回答 2