计算叶图中的节点数

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 class BST<T> {
    public BTNode<T> root;
    int depthCount = 0;

    public BST() {
        root = null;
    }

    public int nonleaves() { // Method must be declared like this. No
                                // parameters.
        BTNode<T> current = root;
        BTNode<T> previous = null;
        int nonLeafCount = 0;

        while (current != null) {
            if (previous == current.parent) { // this includes when parent is
                                                // null, i.e. current is the
                                                // root.
                previous = current;
                if (current.left != null) {
                    nonLeafCount++;
                    current = current.left;
                } else if (current.right != null) {
                    nonLeafCount++;
                    current = current.right;
                } else {
                    current = current.parent;
                }
            } else if (previous == current.left) {
                previous = current;
                if (current.right != null) {
                    current = current.right;
                } else {
                    current = current.parent;
                }
            } else {
                // previous==current.right
                previous = current;
                current = current.parent;
            }
        }
        return nonLeafCount;
    }

    private static class BTNode<T> {
        BTNode<T> left, right, parent;

        /* ... */
    }
}

使用堆栈：

public class BST2<T> {
    public BTNode<T> root;
    int depthCount = 0;

    public BST2() {
        root = null;
    }

    public int nonleaves() { // Method must be declared like this. No
                                // parameters.
        BTNode<T> current = root;
        BTNode<T> previous = null;
        int nonLeafCount = 0;

        MyStack myStack = new MyStack(); // New empty stack

        while (current != null) {
            if (previous == myStack.top()) { // this includes when stack is 
                                                // empty, i.e. current is the
                                                // root.
                myStack.push(current);
                previous = current;
                if (current.left != null) {
                    nonLeafCount++;
                    current = current.left;
                } else if (current.right != null) {
                    nonLeafCount++;
                    current = current.right;
                } else {
                    myStack.pop();
                    current = myStack.top();
                }
            } else if (previous == current.left) {
                previous = current;
                if (current.right != null) {
                    current = current.right;
                } else {
                    myStack.pop();
                    current = myStack.top();
                }
            } else {
                // previous==current.right
                previous = current;
                myStack.pop();
                current = myStack.top();
            }
        }
        return nonLeafCount;
    }

    private static class BTNode<T> {
        BTNode<T> left, right;

        /* ... */
    }
}

Answer 2

在没有递归调用的情况下遍历树的简单方法是使用堆栈。将根压入堆栈，然后进入一个循环——只要堆栈不为空——从堆栈中弹出一个节点并压入该节点的 non-null children。很明显，这最终会将每个节点恰好一次压入堆栈并恰好弹出一次。现在您需要做的就是统计至少有一个 child 的弹出节点。把这些放在一起，

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是堆栈指针。

此外，此代码假定根是 non-null。如果根可以为空，则在开头添加检查，在这种情况下为 return 0。

NB 甚至可以通过几种方法在没有堆栈的情况下进行遍历，尽管以在遍历期间更改树为代价。（当遍历完成时，它恢复到原来的形状。）最好的 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;
  }
}

最后，如果我没有指出我们可以对算法进行一些代数运算以消除一些微小的低效问题，那我就是失职了。你会注意到，左边的 child 被压入堆栈后，它肯定会在下一次循环迭代中被弹出。根 push/pop 类似。我们不妨直接设置node。此外，还有一些多余的比较。这篇笔记的细节太多了，但这里有一个重新设计的 non-leaf 计数器（未经测试但应该可以正常工作）：

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;
}

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

计算叶图中的节点数

Counting the number of nodes in Leaf diagram

java

binary-search-tree

data-structures