计算完全二叉树中的节点数量

给定一个由 N 个节点组成的完全二叉树的根节点，我们的任务是找出给定二叉树中的节点总数。

示例：

> 输入：

>

> !image

>

> 输出： 7

>

> 输入：

>

> !image

>

> 输出： 5

在练习中尝试!
朴素方法： 解决这个问题的简单方法是对给定的树进行 DFS（深度优先搜索）遍历，并统计其中的节点数量。遍历结束后，打印获得的节点总数。

C++

// C++ program for the above approach
#include 
using namespace std;

// Structure of a Tree Node
class node {
public:
    int data;
    node* left;
    node* right;
};

// Function to get the count of nodes
// in complete binary tree
int totalNodes(node* root)
{
    if (root == NULL)
        return 0;

    int l = totalNodes(root->left);
    int r = totalNodes(root->right);

    return 1 + l + r;
}

// Helper function to allocate a new node
// with the given data
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return (Node);
}

// Driver Code
int main()
{
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(9);
    root->right->right = newNode(8);
    root->left->left->left = newNode(6);
    root->left->left->right = newNode(7);
    cout << totalNodes(root);
    return 0;
}

CODEBLOCK_b06e45c4


Python

# Python program for the above approach
# Structure of a Tree Node

class node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

        
# Function to get the count of nodes
# in complete binary tree
def totalNodes(root):
  # Base case
    if(root == None):
        return 0

    # Find the left height and the
    # right heights
    l = totalNodes(root.left)
    r = totalNodes(root.right)

    return 1 + l + r

  
# Helper Function to allocate a new node
# with the given data
def newNode(data):
    Node = node(data)
    return Node

# Driver code
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.right.left = newNode(9)
root.right.right = newNode(8)
root.left.left.left = newNode(6)
root.left.left.right = newNode(7)

print(totalNodes(root))

# This code is contributed by Yash Agarwal(yashagarwal2852002)

`

C#

//C# code for the above approach
using System;

class GFG
{
    // tree node
    public class node
    {
        public int data;
        public node left, right;
        public node()
        {
            data = 0;
            left = right = null;
        }

    }

    // Function to get the count of nodes
    // in complete binary tree
    static int totalNodes(node root)
    {
        if (root == null)
            return 0;

        int l = totalNodes(root.left);
        int r = totalNodes(root.right);

        return 1 + l + r;
    }

    // Helper function to allocate a new node