怎么遍历线索二叉树提供代码和案例

线索二叉树是一种特殊的二叉搜索树，它通过添加额外的线索信息（称为前驱和后继指针），使得遍历操作变得更加直接和高效。在线索二叉树中，每个节点除了常规的左右孩子指针外，还包含了指向其前驱节点（如果存在）和后继节点（如果不存在左孩子）的指针。

遍历线索二叉树通常有三种基本方式：前序、中序和后序遍历。以下是这些遍历方法的基本示例，假设我们有一个线索二叉树的结构：

// 线索二叉树节点定义
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *pred; // 前驱指针
    struct TreeNode *suc; // 后继指针
};

// 前序遍历（根-左-右）
void inOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        // 遍历当前节点
        cout << root->val << " ";
        
        // 如果当前节点没有左孩子，那么它的后继就是前驱的右孩子
        if (!root->left) {
            cout << "(No left child - next is " << root->pred->right->val << ")";
        } else {
            // 普通情况下的后继指针
            cout << "(Next is " << root->suc->val << ")";
        }
        
        // 继续遍历左子树和当前节点的后继
        inOrderTraversal(root->left);
        inOrderTraversal(root->suc);
    }
}

// 中序遍历（左-根-右）
void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        cout << root->val << " ";
        
        // 类似于前序遍历，处理后继指针
        if (!root->right) {
            cout << "(No right child - next is " << root->pred->right->val << ")";
        } else {
            cout << "(Next is " << root->suc->val << ")";
        }
        inOrderTraversal(root->right);
    }
}

// 后序遍历（左-右-根）
void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        inOrderTraversal(root->right);
        cout << root->val << " ";
        
        // 后序遍历不需要特殊处理后继指针，因为已经遍历过了
    }
}