//二叉树的二叉链表存储表示 typedef struct BiNode { /**************begin************/ /**************end************/ }BiTNode,*BiTree;

### C++ 二叉树 遍历与统计实现 以下是基于C++语言的二叉树先序遍历、中序遍历、后序遍历、深度计算以及节点统计的相关算法实现。 #### 定义二叉树结构 首先定义一个简单的二叉树节点类 `TreeNode` 和操作该树的方法： ```cpp #include <iostream> #include <stack> using namespace std; // 定义二叉树节点结构 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int data) : val(data), left(nullptr), right(nullptr) {} }; ``` --- #### 先序遍历 (Preorder Traversal) 先序遍历遵循 **根 -> 左子树 -> 右子树** 的顺序。可以采用递归或迭代两种方式实现。 ##### 递归方法 ```cpp void preorderRecursive(TreeNode* root) { if (!root) return; // 如果当前节点为空，返回 cout << root->val << " "; // 访问根节点 preorderRecursive(root->left); // 遍历左子树 preorderRecursive(root->right); // 遍历右子树 } ``` ##### 迭代方法 ```cpp void preorderIterative(TreeNode* root) { if (!root) return; // 如果树为空，直接退出 stack<TreeNode*> s; s.push(root); while (!s.empty()) { // 当栈不为空时循环 TreeNode* node = s.top(); s.pop(); cout << node->val << " "; // 输出当前节点 if (node->right) s.push(node->right); // 先压入右孩子（后处理） if (node->left) s.push(node->left); // 再压入左孩子（先处理） } } ``` --- #### 中序遍历 (Inorder Traversal) 中序遍历遵循 **左子树 -> 根 -> 右子树** 的顺序。 ##### 递归方法 ```cpp void inorderRecursive(TreeNode* root) { if (!root) return; // 如果当前节点为空，返回 inorderRecursive(root->left); // 遍历左子树 cout << root->val << " "; // 访问根节点 inorderRecursive(root->right); // 遍历右子树 } ``` ##### 迭代方法 ```cpp void inorderIterative(TreeNode* root) { if (!root) return; // 如果树为空，直接退出 stack<TreeNode*> s; TreeNode* curr = root; while (curr || !s.empty()) { // 当指针非空或者栈中有待处理节点时循环 while (curr) { // 将所有左子树压入栈 s.push(curr); curr = curr->left; } curr = s.top(); s.pop(); // 处理栈顶节点 cout << curr->val << " "; // 输出当前节点 curr = curr->right; // 移动到右子树 } } ``` --- #### 后序遍历 (Postorder Traversal) 后序遍历遵循 **左子树 -> 右子树 -> 根** 的顺序。 ##### 递归方法 ```cpp void postorderRecursive(TreeNode* root) { if (!root) return; // 如果当前节点为空，返回 postorderRecursive(root->left); // 遍历左子树 postorderRecursive(root->right); // 遍历右子树 cout << root->val << " "; // 访问根节点 } ``` ##### 迭代方法 由于后序遍历需要两次访问同一节点，因此可以通过辅助栈来模拟这种行为。 ```cpp void postorderIterative(TreeNode* root) { if (!root) return; // 如果树为空，直接退出 stack<TreeNode*> s1, s2; s1.push(root); while (!s1.empty()) { // 使用两个栈完成后序遍历 TreeNode* node = s1.top(); s1.pop(); s2.push(node); // 倒置输出顺序 if (node->left) s1.push(node->left); // 先压入左孩子 if (node->right) s1.push(node->right); // 再压入右孩子 } while (!s2.empty()) { // 最终从第二个栈依次弹出并打印 cout << s2.top()->val << " "; s2.pop(); } } ``` --- #### 深度计算 (Tree Depth Calculation) 通过递归求解树的最大深度。 ```cpp int maxDepth(TreeNode* root) { if (!root) return 0; // 空树高度为0 int leftHeight = maxDepth(root->left); // 获取左子树的高度 int rightHeight = maxDepth(root->right); // 获取右子树的高度 return max(leftHeight, rightHeight) + 1; // 返回较大者加1 } ``` --- #### 节点统计 (Node Counting) 同样可通过递归统计整个树中的节点数。 ```cpp int countNodes(TreeNode* root) { if (!root) return 0; // 空树节点数为0 return countNodes(root->left) + countNodes(root->right) + 1; // 统计左右子树和当前节点 } ``` --- ### 总结 以上代码实现了二叉树的主要功能，包括三种遍历方式及其对应的递归与迭代版本，同时还提供了深度计算和节点统计的功能[^1]。

这段代码是用来统计二叉树中结点个数的，使用的是二叉链表存储结构。其中CreateBiTree函数用来建立二叉树，按照先序遍历的顺序输入二叉树中结点的值，如果输入的是'#'代表该节点为空。NodeCount函数用来递归计算二叉树中结点的个数，如果是空树，返回0；否则返回左子树的结点个数+右子树的结点个数+1。最后在主函数中调用CreateBiTree和NodeCount函数，并输出结果。