c++二叉树的建立与遍历

在C++中，二叉树是一种常见的数据结构，通常由节点组成，每个节点包含两个指针，分别指向其左孩子和右孩子。建立二叉树的过程一般通过递归的方式完成，可以按照前序、中序、后序遍历或者层次遍历来进行。 **建立二叉树**： 1. **创建节点**：首先定义一个节点类，包含值、左子节点和右子节点的指针。 ```cpp struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; ``` 2. **构造函数**：根据给定的元素序列，使用递归或迭代的方式来构建树。例如，前序遍历（根-左-右）可以这样实现： ```cpp void buildTree(TreeNode*& root, vector<int>& nums) { if (nums.empty()) return; root = new TreeNode(nums[0]); buildTree(root->left, nums.begin() + 1); buildTree(root->right, nums.begin() + 1 + nums[0] * 2); } ``` **遍历二叉树**： 1. **前序遍历（根-左-右）**：对于当前节点，先访问它，然后递归地遍历左子树和右子树。 2. **中序遍历（左-根-右）**：先遍历左子树，然后访问根节点，最后遍历右子树。 3. **后序遍历（左-右-根）**：先遍历左子树和右子树，然后访问根节点。 4. **层次遍历（水平顺序）**：从上到下，从左到右逐层遍历。 ```cpp // 前序遍历示例 void preOrder(TreeNode* node) { if (node) { cout << node->val << " "; preOrder(node->left); preOrder(node->right); } } // 中序遍历示例 void inOrder(TreeNode* node) { if (node) { inOrder(node->left); cout << node->val << " "; inOrder(node->right); } } // 后序遍历示例 void postOrder(TreeNode* node) { if (node) { postOrder(node->left); postOrder(node->right); cout << node->val << " "; } } // 层次遍历示例（非递归） void levelOrder(TreeNode* root) { 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); } } ```