转载

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

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

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

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

2）如果遇到叶节点，则返回1

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

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

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

<b>private</b> <b>int</b> countLeaves(TreeNode node) {
    <b>if</b> (node == <b>null</b>)
      <b>return</b> 0;

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

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

<b>public</b> <b>int</b> countLeafNodesRecursively() {
    <b>return</b> countLeaves(root);
  }

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

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

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

1）如果根为空，则返回零。

2）以零开始计数

3）将根推入堆栈

4）循环直到堆栈不为空

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

6）增加计数

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

<b>public</b> <b>int</b> countLeafNodes() {
    <b>if</b> (root == <b>null</b>) {
      <b>return</b> 0;
    }

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

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

    <b>return</b> count;

  }
}

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

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

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

/ /

b f

/ / / /

c e g h

/ /

d k

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

<b>import</b> java.util.Stack;

<font><i>/*
 * 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 
 */</i></font><font>
</font>

<b>public</b> <b>class</b> Main {

  <b>public</b> <b>static</b> <b>void</b> main(String args) throws Exception {

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

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

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

  }

}

<b>class</b> BinaryTree {
  <b>static</b> <b>class</b> TreeNode {
    String value;
    TreeNode left, right;

    TreeNode(String value) {
      <b>this</b>.value = value;
      left = right = <b>null</b>;
    }

    <b>boolean</b> isLeaf() {
      <b>return</b> left == <b>null</b> ? right == <b>null</b> : false;
    }

  }

  </font><font><i>// root of binary tree</i></font><font>
  TreeNode root;

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

  <b>private</b> <b>int</b> countLeaves(TreeNode node) {
    <b>if</b> (node == <b>null</b>)
      <b>return</b> 0;

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

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

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

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

    <b>return</b> 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
</font>

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

原文 https://www.jdon.com/51896

正文到此结束