首页使用C++实现（1）完成二叉树二叉链表结构的定义（二）实现二叉链表的创建，先序、中序和后序遍历算法的实现。

使用C++实现（1）完成二叉树二叉链表结构的定义（二）实现二叉链表的创建，先序、中序和后序遍历算法的实现。

时间: 2024-12-08 10:22:38 浏览: 129

首先，让我们分步骤地定义二叉树的二叉链表结构：（一）二叉树二叉链表结构的定义（C++代码示例）: ```cpp // 定义节点结构体，包含值和左右子节点指针 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 定义二叉链表头结点 class BinaryTree { private: TreeNode* root; // 根节点 public: BinaryTree() : root(nullptr) {} // 构造函数，初始化为空 // 添加更多操作... }; ``` 接下来是二叉链表的创建及遍历算法实现：（二）二叉链表的创建： ```cpp // 插入节点到二叉树 void insert(TreeNode*& node, int value) { if (!node) { node = new TreeNode(value); } else if (value < node->val) { insert(node->left, value); } else { insert(node->right, value); } } // 创建空的二叉链表 void createEmptyBinaryTree(BinaryTree& tree) { tree.root = nullptr; } ``` ### 遍历算法实现（三种常用遍历方式）: 1. 先序遍历（根-左-右）: ```cpp void preOrderTraversal(TreeNode* node, vector<int>& result) { if (node) { result.push_back(node->val); preOrderTraversal(node->left, result); preOrderTraversal(node->right, result); } } ``` 2. 中序遍历（左-根-右）: ```cpp void inOrderTraversal(TreeNode* node, vector<int>& result) { if (node) { inOrderTraversal(node->left, result); result.push_back(node->val); inOrderTraversal(node->right, result); } } ``` 3. 后序遍历（左-右-根）: ```cpp void postOrderTraversal(TreeNode* node, vector<int>& result) { if (node) { postOrderTraversal(node->left, result); postOrderTraversal(node->right, result); result.push_back(node->val); } } ```

阅读全文