以下是一个基于C++的示例程序，用于创建二叉树，并进行先序、中序和后序遍历，同时计算二叉树的高度、叶子节点数量以及给定节点的度。程序包含两个函数：`bitree(height)` 和 `bitree(hlo)`，分别用于按高度创建二叉树和按高度、叶子节点和节点度进行操作。 首先，我们定义二叉树的节点结构： ```cpp #include <iostream> #include <queue> using namespace std; // 定义二叉树节点结构 struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char x) : val(x), left(NULL), right(NULL) {} }; // 创建二叉树（完全二叉树） TreeNode* createCompleteBinaryTree(int height) { if (height <= 0) return NULL; queue<TreeNode*> q; TreeNode* root = new TreeNode('A' + (1 << (height - 1)) - 1); // 根节点 q.push(root); int currentVal = root->val + 1; for (int i = 1; i < height; ++i) { int levelSize = (1 << i) - 1; for (int j = 0; j < levelSize; ++j) { TreeNode* node = q.front(); q.pop(); if (currentVal <= 'A' + (1 << height) - 2) { node->left = new TreeNode(currentVal++); q.push(node->left); } if (currentVal <= 'A' + (1 << height) - 2) { node->right = new TreeNode(currentVal++); q.push(node->right); } } } return root; } // 先序遍历 void preorderTraversal(TreeNode* root) { if (root == NULL) return; cout << root->val << " "; preorderTraversal(root->left); preorderTraversal(root->right); } // 中序遍历 void inorderTraversal(TreeNode* root) { if (root == NULL) return; inorderTraversal(root->left); cout << root->val << " "; inorderTraversal(root->right); } // 后序遍历 void postorderTraversal(TreeNode* root) { if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); cout << root->val << " "; } // 计算二叉树高度 int getHeight(TreeNode* root) { if (root == NULL) return 0; return 1 + max(getHeight(root->left), getHeight(root->right)); } // 计算叶子节点数量 int countLeaves(TreeNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return countLeaves(root->left) + countLeaves(root->right); } // 计算节点的度（0, 1, 或 2） int getNodeDegree(TreeNode* root, TreeNode* node) { if (node == NULL) return -1; // 节点不存在 int degree = 0; if (node->left != NULL) ++degree; if (node->right != NULL) ++degree; return degree; } // 主函数功能菜单 void mainMenu() { int choice; int height; char nodeVal; TreeNode* root = NULL; while (true) { cout << "\n功能菜单:\n"; cout << "1. 按高度创建二叉树并进行遍历\n"; cout << "2. 按高度、叶子节点和节点度操作\n"; cout << "0. 退出\n"; cout << "请选择: "; cin >> choice; if (choice == 0) break; if (choice == 1) { cout << "输入二叉树高度: "; cin >> height; root = createCompleteBinaryTree(height); cout << "先序遍历: "; preorderTraversal(root); cout << "\n中序遍历: "; inorderTraversal(root); cout << "\n后序遍历: "; postorderTraversal(root); cout << "\n二叉树高度: " << getHeight(root) << endl; } else if (choice == 2) { cout << "输入二叉树高度: "; cin >> height; root = createCompleteBinaryTree(height); cout << "输入要查询度的节点值 (字符): "; cin >> nodeVal; TreeNode* targetNode = root; queue<TreeNode*> q; q.push(root); bool found = false; while (!q.empty() && !found) { TreeNode* node = q.front(); q.pop(); if (node->val == nodeVal) { found = true; cout << "节点 " << nodeVal << " 的度: " << getNodeDegree(root, node) << endl; } else { if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } if (!found) cout << "节点 " << nodeVal << " 不存在!" << endl; cout << "二叉树高度: " << getHeight(root) << endl; cout << "叶子节点数量: " << countLeaves(root) << endl; } else { cout << "无效选择，请重新选择!" << endl; } } } int main() { mainMenu(); return 0; } ``` 代码说明： 1. TreeNode结构：定义了二叉树的节点，包含节点的值、左子节点和右子节点。 2. createCompleteBinaryTree函数：使用队列按层次创建完全二叉树，节点值从'A'开始递增。 3. 遍历函数：`preorderTraversal`、`inorderTraversal`和`postorderTraversal`分别实现先序、中序和后序遍历。 4. getHeight函数：计算二叉树的高度。 5. countLeaves函数：计算二叉树中的叶子节点数量。 6. getNodeDegree函数：计算给定节点的度（0、1或2）。 7. mainMenu函数：主函数功能菜单，用于选择创建二叉树和进行各种操作。 使用方法： 1. 编译并运行程序。 2. 根据提示选择功能菜单中的选项。 3. 输入相应的参数（如二叉树高度、节点值等）进行操作。 这个示例程序是一个基本的二叉树操作框架，可以根据实际需求进行扩展和修改。 [2024-11-13 11:40:36 | AI写代码神器 | 1625点数解答]