C语言编写中序遍历线索二叉树

我可以给你提供一个示例代码： void inOrder(struct node *root)
{
if (root != NULL)
{
inOrder(root->left);
printf("%d \n", root->data);
inOrder(root->right);
}
}

相关问题

c语言使用编写二叉树中序遍历线索化

好的，下面是使用C语言编写的二叉树中序遍历线索化的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    int ltag;
    int rtag;
} TreeNode;

// 创建二叉树
TreeNode* createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = createTree();
    node->right = createTree();
    node->ltag = 0;
    node->rtag = 0;
    return node;
}

// 中序遍历线索化
void inOrderThread(TreeNode *p, TreeNode **prev) {
    if (p != NULL) {
        inOrderThread(p->left, prev);
        if (p->left == NULL) {
            p->left = *prev;
            p->ltag = 1;
        }
        if (*prev != NULL && (*prev)->right == NULL) {
            (*prev)->right = p;
            (*prev)->rtag = 1;
        }
        *prev = p;
        inOrderThread(p->right, prev);
    }
}

// 中序遍历线索化后的遍历操作
void inOrderThreadTraverse(TreeNode *root) {
    TreeNode *p = root->left;
    while (p != root) {
        while (p->ltag == 1) {
            p = p->left;
        }
        printf("%d ", p->val);
        while (p->rtag == 0) {
            p = p->right;
            if (p == root) {
                return;
            }
            printf("%d ", p->val);
        }
        p = p->right;
    }
}

int main() {
    TreeNode *root = createTree();
    TreeNode *prev = NULL;
    inOrderThread(root, &prev);
    inOrderThreadTraverse(root);
    return 0;
}

在这个示例代码中，我们通过定义一个二叉树结构体来表示二叉树节点，其中 `ltag` 和 `rtag` 分别表示左右指针是否为线索指针。然后我们通过 `createTree()` 函数来创建一棵二叉树，通过 `inOrderThread()` 函数来对二叉树进行中序遍历线索化，最后通过 `inOrderThreadTraverse()` 函数来输出中序遍历线索化后的结果。

编程实现线索二叉树的下列基本操作。 （1）建立先序线索二叉树 （2）建立中序线索二叉树 （3）建立后序线索二叉树 （4）先序遍历线索二叉树 （5）中序遍历线索二叉树 （6）后序遍历线索二叉树 用C语言编写

线索二叉树是一种特殊的数据结构，用于存储每个节点除了常规的左指针和右指针外，还额外包含前驱（prev）和后继（next）指针，使得可以沿着线索追查到前驱或后继节点。以下是这些基本操作在C语言中的实现概述：

1. **建立** (1) 先序线索二叉树:

typedef struct Node {
    int data;
    struct Node* next; // 原有右指针
    struct Node* prev; // 添加前驱指针，默认指向NULL
} TreeNode;

void createPreorderTree(TreeNode** root, int arr[], int start, int end) {
    if (start > end) return;
    TreeNode* node = malloc(sizeof(TreeNode));
    node->data = arr[start];
    *root = node;
    node->next = NULL;
    
    // 添加线索，如果当前节点不是第一个节点，则连接前驱
    if (start != 0) (*root)->prev = arr[start - 1];

    // 继续创建右子树
    createPreorderTree(&node->next, arr, start + 1, end);
}

2. **建立** (2) 中序线索二叉树:

void createInorderTree(TreeNode** root, int arr[], int start, int end) {
    if (start > end) return;
    TreeNode* node = malloc(sizeof(TreeNode));
    TreeNode* temp = *root;
    
    // 找到插入位置
    while (temp && arr[start] < temp->data) temp = temp->left;
    
    node->data = arr[start];
    node->left = temp->left;
    temp->left = node;

    // 添加线索，如果在左子树中，则链接前驱，否则在前驱链上添加自身
    if (node->left != NULL) node->prev = node->left->prev;
    else if (temp != NULL) temp->prev->next = node;

    // 递归处理剩余部分
    createInorderTree(&node->right, arr, start + 1, end);
}

3. **建立** (3) 后序线索二叉树:

void createPostorderTree(TreeNode** root, int arr[], int start, int end) {
    if (start > end) return;
    TreeNode* node = malloc(sizeof(TreeNode));
    TreeNode* lastVisited = NULL;

    // 遍历完整棵树得到最后一个访问的节点
    for (TreeNode* current = *root; current != NULL; current = current->left)
        lastVisited = current;

    node->data = arr[start];
    node->left = node->right = NULL;

    // 将节点插入到后序序列
    if (lastVisited != NULL && lastVisited->right == NULL) {
        lastVisited->right = node;
        node->prev = lastVisited;
    } else {
        // 搜索并连接到前驱线索
        TreeNode* prevNode = lastVisited->prev;
        while (prevNode != NULL && prevNode->right != lastVisited) prevNode = prevNode->prev;
        prevNode->right = node;
        node->prev = prevNode;
        node->next = lastVisited;
    }

    createPostorderTree(&node->left, arr, start + 1, end);
}

4. **遍历** (4) 先序、中序和后序线索二叉树:

// 建立好线索后，可以直接使用标准的先序/中序/后序遍历函数，稍作修改即可加入线索检查
void inorderTraversal(TreeNode* root) {
    while (root) {
        printf("%d ", root->data); // 输出节点数据
        root = root->prev ? root->prev : root->right; // 根据线索继续遍历
    }
}
// 提供类似方法对先序和后序进行遍历