C/C++数据结构之二叉树的节点统计

概述对二叉树的节点进行统计是理解和操作二叉树的基础任务包括节点总数、叶子节点数、度为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; stackTreeNode* 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; stackTreeNode* 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)); }