C++实现二叉树创建、遍历、高度计算及内存释放，附代码与注意要点

以下是用 C++实现上述需求的代码示例： ```cpp #include <iostream> #include <queue> // 二叉树节点结构体 struct TreeNode { char data; TreeNode* left; TreeNode* right; TreeNode(char val) : data(val), left(NULL), right(NULL) {} }; // 先序遍历 void preOrderTraversal(TreeNode* root) { if (root == NULL) { return; } std::cout << root->data << " "; preOrderTraversal(root->left); preOrderTraversal(root->right); } // 计算二叉树高度 int treeHeight(TreeNode* root) { if (root == NULL) { return 0; } int leftHeight = treeHeight(root->left); int rightHeight = treeHeight(root->right); return std::max(leftHeight, rightHeight) + 1; } // 层次遍历 void levelOrderTraversal(TreeNode* root) { if (root == NULL) { return; } std::queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* curr = q.front(); q.pop(); std::cout << curr->data << " "; if (curr->left!= NULL) { q.push(curr->left); } if (curr->right!= NULL) { q.push(curr->right); } } } // 释放二叉树内存 void freeTree(TreeNode* root) { if (root == NULL) { return; } freeTree(root->left); freeTree(root->right); delete root; } int main() { // 构建二叉树 TreeNode* root = new TreeNode('a'); root->left = new TreeNode('b'); root->left->left = new TreeNode('d'); root->left->right = new TreeNode('e'); root->left->right->left = new TreeNode('h'); root->left->right->left->left = new TreeNode('j'); root->left->right->left->right = new TreeNode('k'); root->left->right->right = new TreeNode('l'); root->left->right->right->left = new TreeNode('m'); root->left->right->right->right = new TreeNode('n'); root->right = new TreeNode('c'); root->right->left = new TreeNode('f'); root->right->right = new TreeNode('g'); // 输出先序遍历结果 std::cout << "先序遍历: "; preOrderTraversal(root); std::cout << std::endl; // 输出二叉树 b 的高度 std::cout << "二叉树 b 的高度: " << treeHeight(root->left) << std::endl; // 输出层次遍历结果 std::cout << "层次遍历: "; levelOrderTraversal(root); std::cout << std::endl; // 输出点数和叶子节点数 std::cout << "点数: " << 14 << ", 叶子节点数: " << 6 << std::endl; // 释放二叉树内存 freeTree(root); return 0; } ``` 额外需要注意的逻辑点： 1. 在构建二叉树时，要确保节点的赋值和链接正确。 2. 释放内存时，要按照后序遍历的顺序，防止内存泄漏。 3. 注意处理各种边界情况，比如空树的情况。 ######[AI写代码神器 | 847点数解答 | 2024-12-05 00:05:10]