用C++语言实现 实验内容 1．输入字符序列，建立二叉链表。 2．中序遍历二叉树:递归算法。 3．中序遍历二叉树:非递归算法。（最好也能实现先序，后序非递归算法） 4．求二叉树的高度 。 5．求二叉树的叶子个数。 6．编写一个主函数,调试上述算法。

好的,我来为您介绍如何使用C++语言实现这个二叉树实验内容。以下是详细的实现步骤和代码: 1. 首先,我们定义二叉树的节点结构: ```cpp struct TreeNode { char data; TreeNode* left; TreeNode* right; TreeNode(char val) : data(val), left(nullptr), right(nullptr) {} }; ``` 2. 创建二叉树的函数: ```cpp TreeNode* createTree() { char ch; cin >> ch; if (ch == '#') return nullptr; TreeNode* node = new TreeNode(ch); node->left = createTree(); node->right = createTree(); return node; } ``` 3. 中序遍历(递归): ```cpp void inorderTraversalRec(TreeNode* root) { if (!root) return; inorderTraversalRec(root->left); cout << root->data << " "; inorderTraversalRec(root->right); } ``` 4. 中序遍历(非递归): ```cpp void inorderTraversalIter(TreeNode* root) { stack<TreeNode*> s; TreeNode* current = root; while (current || !s.empty()) { while (current) { s.push(current); current = current->left; } current = s.top(); s.pop(); cout << current->data << " "; current = current->right; } } ``` 5. 求二叉树的高度: ```cpp int getHeight(TreeNode* root) { if (!root) return 0; return max(getHeight(root->left), getHeight(root->right)) + 1; } ``` 6. 求叶子节点个数: ```cpp int countLeaves(TreeNode* root) { if (!root) return 0; if (!root->left && !root->right) return 1; return countLeaves(root->left) + countLeaves(root->right); } ``` 7. 主函数: ```cpp int main() { cout << "请输入二叉树的节点序列(用#表示空节点):" << endl; TreeNode* root = createTree(); cout << "中序遍历(递归): "; inorderTraversalRec(root); cout << endl; cout << "中序遍历(非递归): "; inorderTraversalIter(root); cout << endl; cout << "二叉树的高度: " << getHeight(root) << endl; cout << "叶子节点个数: " << countLeaves(root) << endl; return 0; } ``` 这个实现包含了实验要求的所有内容。主函数中首先创建二叉树,然后分别进行递归和非递归的中序遍历,最后输出二叉树的高度和叶子节点个数。 注意:这个实现中只包含了中序遍历的非递归算法。如果需要先序和后序的非递归算法,我们可以使用类似的栈操作来实现。