企业官网建设流程全解析

概述

对二叉树的节点进行统计是理解和操作二叉树的基础任务，包括：节点总数、叶子节点数、度为1的节点数、度为2的节点数、树的高度（深度）等。这些统计信息不仅有助于分析树的结构特性，还能为后续的遍历、查找、插入和删除等操作提供重要依据。

节点定义

在开始节点统计前，首先需要明确二叉树的基本结构。一个二叉树由若干节点组成，每个节点最多有两个子节点：左子节点和右子节点。节点之间通过指针连接，形成层次结构。

我们通常使用结构体或类来定义二叉树的节点：nData用于表示节点值，pLeft和pRight分别指向左右子节点。初始状态下，左右指针为空，表示该节点为叶子节点。

struct TreeNode { int nData; TreeNode* pLeft; TreeNode* pRight; TreeNode(int nVal) : nData(nVal), pLeft(NULL), pRight(NULL) {} };

节点总数

节点总数是指二叉树中所有节点的个数，可以通过递归或迭代的方式进行统计。

递归法是最直观的方法：对于任意一个节点，其子树的节点总数等于左子树节点数 + 右子树节点数 + 1（当前节点）。其时间复杂度为O(n)，其中n是节点总数。其空间复杂度为O(h)，h为树的高度。

int CountNodes(TreeNode* pRoot) { if (pRoot == NULL) { return 0; } return 1 + CountNodes(pRoot->pLeft) + CountNodes(pRoot->pRight); }

迭代法可以使用栈模拟递归过程，进行前序、中序或后序遍历，每访问一个节点就计数加一。

int CountNodesIterative(TreeNode* pRoot) { if (pRoot == NULL) { return 0; } int nCount = 0; stack<TreeNode*> stk; stk.push(pRoot); while (!stk.empty()) { TreeNode* pNode = stk.top(); stk.pop(); nCount++; if (pNode->pRight) { stk.push(pNode->pRight); } if (pNode->pLeft) { stk.push(pNode->pLeft); } } return nCount; }

叶子节点数

叶子节点是指没有子节点的节点，也可以通过递归或迭代的方式进行统计。由于与上面的实现比较类似，这里就不再赘述了，示例代码如下。

int CountLeaves(TreeNode* pRoot) { if (pRoot == NULL) { return 0; } if (pRoot->pLeft == NULL && pRoot->pRight == NULL) { return 1; } return CountLeaves(pRoot->pLeft) + CountLeaves(pRoot->pRight); } int CountLeavesIterative(TreeNode* pRoot) { if (pRoot == NULL) { return 0; } int nCount = 0; stack<TreeNode*> stk; stk.push(pRoot); while (!stk.empty()) { TreeNode* pNode = stk.top(); stk.pop(); if (pNode->pLeft == NULL && pNode->pRight == NULL) { nCount++; } if (pNode->pRight) { stk.push(pNode->pRight); } if (pNode->pLeft) { stk.push(pNode->pLeft); } } return nCount; }

度为1的节点数

度为1的节点是指只有一个子节点的节点，即只有左或右，不同时存在。

int CountDegreeOne(TreeNode* pRoot) { if (pRoot == NULL) { return 0; } int nCount = 0; if ((pRoot->pLeft != NULL && pRoot->pRight == NULL) || (pRoot->pLeft == NULL && pRoot->pRight != NULL)) { nCount = 1; } return nCount + CountDegreeOne(pRoot->pLeft) + CountDegreeOne(pRoot->pRight); }

度为2的节点数

度为2的节点是指既有左子节点又有右子节点的节点，示例代码如下。

int CountDegreeTwo(TreeNode* pRoot) { if (pRoot == NULL) { return 0; } int nCount = (pRoot->pLeft != NULL && pRoot->pRight != NULL) ? 1 : 0; return nCount + CountDegreeTwo(pRoot->pLeft) + CountDegreeTwo(pRoot->pRight); }

树的高度

二叉树的高度是从根节点到最远叶子节点的最长路径上的节点数。递归定义为：树的高度 = max(左子树高度, 右子树高度) + 1。

int TreeHeight(TreeNode* pRoot) { if (pRoot == NULL) { return 0; } return 1 + max(TreeHeight(pRoot->pLeft), TreeHeight(pRoot->pRight)); }