链式二叉树创建及遍历c++

链式二叉树，也称为线索二叉树，是一种特殊的二叉查找树结构，其中每个节点除了包含左右子指针外，还额外有一个前驱指针或后继指针，用于辅助双向查找。创建链式二叉树的基本步骤如下：

1. **创建节点**：
- 定义一个二叉树节点类，通常包括整型数据域、左指针、右指针以及前驱或后继指针。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* prev; // 前驱节点指针
    TreeNode* next; // 后继节点指针 (仅用于循环链表)
};

2. **初始化**：
- 创建新节点时，需要设置默认的前驱或后继指向空。

3. **插入操作**：
- 插入元素时，首先搜索相应位置，然后调整前后指针以保持线索连接的完整性。

4. **遍历**：
- 链式二叉树有多种遍历方式，常见的有顺序遍历（如先序、中序和后序），还有线索化的前序和后续遍历。以下是基本的线索化前序遍历示例：

   void inOrderTraversal(TreeNode* root) {
       if (root != nullptr) {
           if (root->prev == nullptr) { // 标志未访问过
               if (root->left != nullptr) {
                   inOrderTraversal(root->left);
               }
               std::cout << root->val << " ";
               if (root->right != nullptr) {
                   inOrderTraversal(root->right);
               }
               // 更新当前节点的前驱指针
               if (root->left != nullptr) {
                   root->left->next = root;
               } else {
                   root->prev->next = root;
               }
               root->prev = nullptr; // 移除线索
           } else {
               inOrderTraversal(root->prev); // 继续遍历前驱节点
           }
       }
   }