C++实现二叉树创建、遍历、高度计算及释放的完整代码

好的，下面是一个C++程序，用于实现你所描述的功能。程序包括创建二叉树、先序遍历、计算高度、层次遍历、统计结点数和叶子节点数，以及释放二叉树。 ```cpp #include <iostream> #include <queue> using namespace std; // 定义二叉树节点结构 struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char x) : val(x), left(nullptr), right(nullptr) {} }; // 创建二叉树 TreeNode* createTree() { // 手动创建二叉树 a(b(d,e(h(j,k(i,m(n)))),c(f,g(,i)))) TreeNode* a = new TreeNode('a'); TreeNode* b = new TreeNode('b'); TreeNode* c = new TreeNode('c'); TreeNode* d = new TreeNode('d'); TreeNode* e = new TreeNode('e'); TreeNode* f = new TreeNode('f'); TreeNode* g = new TreeNode('g'); TreeNode* h = new TreeNode('h'); TreeNode* i = new TreeNode('i'); TreeNode* j = new TreeNode('j'); TreeNode* k = new TreeNode('k'); TreeNode* m = new TreeNode('m'); TreeNode* n = new TreeNode('n'); a->left = b; a->right = c; b->left = d; b->right = e; e->left = h; h->left = j; h->right = k; k->left = i; k->right = m; m->right = n; c->left = f; c->right = g; g->right = i; return a; } // 先序遍历 void preOrder(TreeNode* root) { if (root == nullptr) return; cout << root->val << " "; preOrder(root->left); preOrder(root->right); } // 计算二叉树的高度 int getHeight(TreeNode* root) { if (root == nullptr) return 0; int leftHeight = getHeight(root->left); int rightHeight = getHeight(root->right); return max(leftHeight, rightHeight) + 1; } // 层次遍历 void levelOrder(TreeNode* root) { if (root == nullptr) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); cout << node->val << " "; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } // 统计结点数和叶子节点数 void countNodesAndLeaves(TreeNode* root, int& totalNodes, int& leafNodes) { if (root == nullptr) return; totalNodes++; if (root->left == nullptr && root->right == nullptr) { leafNodes++; } countNodesAndLeaves(root->left, totalNodes, leafNodes); countNodesAndLeaves(root->right, totalNodes, leafNodes); } // 释放二叉树 void releaseTree(TreeNode* root) { if (root == nullptr) return; releaseTree(root->left); releaseTree(root->right); delete root; } int main() { TreeNode* root = createTree(); cout << "先序遍历: "; preOrder(root); cout << endl; cout << "二叉树的高度: " << getHeight(root) << endl; cout << "层次遍历: "; levelOrder(root); cout << endl; int totalNodes = 0, leafNodes = 0; countNodesAndLeaves(root, totalNodes, leafNodes); cout << "总节点数: " << totalNodes << ", 叶子节点数: " << leafNodes << endl; releaseTree(root); return 0; } ``` 需要注意的逻辑点： 1. 节点创建：手动创建每个节点并连接它们，确保结构正确。 2. 先序遍历：递归遍历节点，先访问根节点，再访问左子树，最后访问右子树。 3. 释放二叉树：递归删除所有节点，避免内存泄漏。 ######[AI写代码神器 | 933点数解答 | 2024-12-05 00:09:45]