java - 计算叶图中的节点数

Question

我已经为此工作了一段时间，但没有运气。希望有人能指出正确的方向。

代码:

public class BST {
  public BTNode<Integer> root;
  int nonLeafCount = 0;
  int depthCount = 0;

  public BST() {
    root = null;
  }



  class BTNode<T> {
    T data;
    BTNode<T> left, right;

    BTNode(T o) {
      data = o;
      left = right = null;
    }

    public String toString() {
      return String.valueOf(data);
    }
  }
}

Answer 1

无需递归调用即可遍历树的简单方法是使用堆栈。将根插入堆栈，然后进入一个循环，只要堆栈不为空，就会从堆栈中弹出一个节点并压入该节点的非空子节点。很明显，这最终会将每个节点恰好一次插入堆栈并弹出一次。现在您需要做的就是计算至少有一个子节点的弹出节点数。把这些放在一起，

public int nonleaves() {
  int nonLeafCount = 0;
  BTNode<Integer> [] stack = new BTNode[2];
  int p = 0;
  stack[p++] = root; // push root
  while (p != 0) {
    BTNode<Integer> node = stack[--p]; // pop
    if (node.left != null || node.right != null) ++nonLeafCount;
    if (p + 1 >= stack.length) stack = Arrays.copyOf(stack, 2 * stack.length);
    if (node.right != null) stack[p++] = node.right; // push right
    if (node.left != null) stack[p++] = node.left;   // push left
  }
  return nonLeafCount;
}

请注意，根据您的描述，我使用了一个简单的 Java 数组作为堆栈，每当它填满时，它就会以 2 倍的速度增长。整数p是堆栈指针。

此外，此代码假设根不为空。如果根可以为空，请在开头添加检查并在这种情况下返回 0。

注意，即使没有堆栈，也可以通过多种方法进行遍历，尽管代价是在遍历期间更改树。 (遍历完成后，它会恢复到原来的形状。)IMO 中最好的是 Morris's algorithm ，但它们都比堆栈复杂得多。看来你是个新程序员，先弄清楚堆栈方法。

编辑

要找到最大深度:

public int maxDepth() {
  int max = 0;
  Pair<Integer> [] stack = new Pair[2];
  int p = 0;
  stack[p++] = new Pair(root, 1);
  while (p != 0) {
    Pair<Integer> pair = stack[--p];
    if (pair.depth > max) max = pair.depth;
    if (p + 1 >= stack.length) stack = Arrays.copyOf(stack, 2 * stack.length);
    if (pair.node.right != null) 
      stack[p++] = new Pair(pair.node.right, 1 + pair.depth);
    if (pair.node.left != null) 
      stack[p++] = new Pair(pair.node.left, 1 + pair.depth);
  }
  return max;
}

private static class Pair<T> {
  BTNode<T> node;
  int depth;
  Pair(BTNode<T> node, int depth) {
    this.node = node;
    this.depth = depth;
  }
}

最后，如果我没有指出我们可以对算法进行一些代数运算来消除一些微小的低效率，那就是我的失职。您会注意到，在将左子级插入堆栈后，它肯定会在下一次循环迭代中弹出。根推/弹出类似。我们不妨直接设置node。另外，还有一些多余的比较。这篇笔记的细节太多了，但这里有一个重新设计的非叶计数器(未经测试，但应该可以正常工作):

public int nonleaves() {
  int nonLeafCount = 0;
  BTNode<Integer>[] stack = new BTNode[1];
  int p = 0;
  BTNode<Integer> node = root;
  for (;;) {
    if (node.left == null) {
      if (node.right == null) {
        if (p == 0) break;
        node = stack[--p];
      } else { // node.right != null
        ++nonLeafCount;
        node = node.right;
      }
    } else { // node.left != null
      ++nonLeafCount;
      if (node.right != null) {
        if (p >= stack.length) {
          stack = Arrays.copyOf(stack, 2 * stack.length);
        }
        stack[p++] = node.right;
      }
      node = node.left;
    }
  }
  return nonLeafCount;
}

你可以看到，为了追求一点点效率，我们失去了很多简单性。这几乎总是一个糟糕的讨价还价。我建议不要这样做。