如何计算二叉树中叶节点的数量 - Java迭代和递归算法

19-03-13 jdon
              

二叉树叶节点总数的递归算法

计算叶节点总数的算法与关于打印叶节点的问题非常相似。 以下是要遵循的实际步骤:

1)如果节点为空返回0,这也是我们递归算法的基本情况

2)如果遇到叶节点,则返回1

3)左、右子树重复该过程。

4)返回左、右子树叶节点的和

下面是基于上述逻辑的示例代码

private int countLeaves(TreeNode node) {
    if (node == null)
      return 0;

    if (node.isLeaf()) {
      return 1;
    } else {
      return countLeaves(node.left) + countLeaves(node.right);
    }
  }

也许您注意到这个方法是私有的,我已经在BinaryTree类中声明了这个方法。为了在外部访问它,我创建了另一个方法countLeafNodesRecursivel(),如下所示:

 

public int countLeafNodesRecursively() {
    return countLeaves(root);
  }

这样做有两个原因,最初的方法需要一个起始节点,它应该是root。 客户端只需调用此方法就可以了,因为Bin已经可以使用BinaryTree类。 然后,包装方法将根传递给计算叶节点的实际方法。 包装方法是公共的,这样客户端就可以访问它,而实际的方法是私有的,这样任何人都无法看到它,开发人员将来可以在不影响客户端的情况下更改实现。这实际上是揭示需要参数的递归方法的标准模式。

二叉树叶节点总数的迭代算法

叶节点计数的递归算法非常简单,迭代算法也非常简单。类似于迭代的InOrder遍历示例,我们使用了一个堆栈来遍历二叉树。下面是迭代算法获得二叉树叶节点总数的步骤:

1)如果根为空,则返回零。

2)以零开始计数

3)将根推入堆栈

4)循环直到堆栈不为空

5)弹出最后一个节点,推送最后一个节点的左右子节点(如果它们不为空)。

6)增加计数

在循环结束时,计数包含叶节点的总数。下面是基于上述逻辑和算法的示例代码:

public int countLeafNodes() {
    if (root == null) {
      return 0;
    }

    Stack stack = new Stack<>();
    stack.push(root);
    int count = 0;

    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      if (node.left != null)
        stack.push(node.left);
      if (node.right != null)
        stack.push(node.right);
      if (node.isLeaf())
        count++;
    }

    return count;

  }
}

你可以看到逻辑非常简单。这个算法的时间复杂度是O(N),因为您需要访问二叉树的所有节点来计算叶节点的总数。堆栈是一个后进先出的数据结构,我们使用了jdk实现java.util.stack,它还扩展了vector类。

用Java程序计算二叉树中叶节点的数量

这是用Java计算给定二叉树中叶节点总数的完整程序。 该程序演示了递归和迭代算法来解决这个问题。在此程序中,我们将使用以下二叉树进行测试。

            a

           / \

         b    f

        / \   / \

      c   e  g  h

     /               \ 

   d                 k 

由于此树中有四个叶节点(D、E、G和K),所以您的程序应该打印4个。CountLeafNodesRecursive()方法使用递归解决此问题,CountLeafNodes()不使用递归解决此问题。两种方法前面已作阐述。

import java.util.Stack;

/*
 * Java Program to count all leaf nodes of binary tree 
 * with and without recursion.
 * input : a
 *        / \
 *       b   f
 *      / \  / \
 *     c   e g  h
 *    /         \ 
 *   d           k 
 * 
 * output: 4 
 */


public class Main {

  public static void main(String args) throws Exception {

    // let's create a binary tree
    BinaryTree bt = new BinaryTree();
    bt.root = new BinaryTree.TreeNode("a");
    bt.root.left = new BinaryTree.TreeNode("b");
    bt.root.right = new BinaryTree.TreeNode("f");
    bt.root.left.left = new BinaryTree.TreeNode("c");
    bt.root.left.right = new BinaryTree.TreeNode("e");
    bt.root.left.left.left = new BinaryTree.TreeNode("d");
    bt.root.right.left = new BinaryTree.TreeNode("g");
    bt.root.right.right = new BinaryTree.TreeNode("h");
    bt.root.right.right.right = new BinaryTree.TreeNode("k");

    // count all leaf nodes of binary tree using recursion
    System.out
        .println("total number of leaf nodes of binary tree in Java (recursively)");
    System.out.println(bt.countLeafNodesRecursively());

    // count all leaf nodes of binary tree without recursion
    System.out
        .println("count of leaf nodes of binary tree in Java (iteration)");
    System.out.println(bt.countLeafNodes());

  }

}

class BinaryTree {
  static class TreeNode {
    String value;
    TreeNode left, right;

    TreeNode(String value) {
      this.value = value;
      left = right = null;
    }

    boolean isLeaf() {
      return left == null ? right == null : false;
    }

  }

  // root of binary tree
  TreeNode root;

  /**
   * Java method to calculate number of leaf node in binary tree.
   * 
   * @param node
   * @return count of leaf nodes.
   */
  public int countLeafNodesRecursively() {
    return countLeaves(root);
  }

  private int countLeaves(TreeNode node) {
    if (node == null)
      return 0;

    if (node.isLeaf()) {
      return 1;
    } else {
      return countLeaves(node.left) + countLeaves(node.right);
    }
  }

  /**
   * Java method to count leaf nodes using iteration
   * 
   * @param root
   * @return number of leaf nodes
   * 
   */
  public int countLeafNodes() {
    if (root == null) {
      return 0;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    int count = 0;

    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      if (node.left != null)
        stack.push(node.left);
      if (node.right != null)
        stack.push(node.right);
      if (node.isLeaf())
        count++;
    }

    return count;

  }
}

Output
total number of leaf nodes of a binary tree in Java (recursively)
4
count of leaf nodes of a binary tree in Java (iteration)
4

这就是如何用Java计算二叉树中叶节点的数量。