二叉树的遍历和中序遍历线索化

发布于：2025-04-13 ⋅ 阅读:(35) ⋅ 点赞:(0)

一、二叉树的遍历

二叉树遍历是指按照某种顺序访问二叉树中的每个节点，且每个节点仅被访问一次。常见的遍历方式有前序遍历、中序遍历、后序遍历和层序遍历，下面分别介绍它们的原理、方法及代码实现。

1.前序、中序、后序遍历

原理

  • 前序遍历：先访问根节点，再递归前序遍历左子树，最后递归前序遍历右子树。
  • 中序遍历：先递归中序遍历左子树，再访问根节点，最后递归中序遍历右子树。
  • 后序遍历：先递归后序遍历左子树，再递归后序遍历右子树，最后访问根节点。

代码实现

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

// 定义二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 前序遍历
void preOrder(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
}

// 中序遍历
void inOrder(TreeNode* root) {
    if (root != NULL) {
        inOrder(root->left);
        printf("%d ", root->data);
        inOrder(root->right);
    }
}

// 后序遍历
void postOrder(TreeNode* root) {
    if (root != NULL) {
        postOrder(root->left);
        postOrder(root->right);
        printf("%d ", root->data);
    }
}

// 释放二叉树内存
void freeTree(TreeNode* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int main() {
    // 构建一个简单的二叉树
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("前序遍历结果: ");
    preOrder(root);
    printf("\n");

    printf("中序遍历结果: ");
    inOrder(root);
    printf("\n");

    printf("后序遍历结果: ");
    postOrder(root);
    printf("\n");

    // 释放二叉树内存
    freeTree(root);

    return 0;
}

代码解释

  • TreeNode 结构体：定义了二叉树节点的结构，包含数据域 data 以及左右子节点指针 left 和 right。
  • createNode 函数：用于创建一个新的二叉树节点，分配内存并初始化节点的数据和指针。
  • preOrder 函数：实现前序遍历，先打印根节点数据，再递归遍历左子树和右子树。
  • inOrder 函数：实现中序遍历，先递归遍历左子树，再打印根节点数据，最后递归遍历右子树。
  • postOrder 函数：实现后序遍历，先递归遍历左子树和右子树，最后打印根节点数据。
  • main 函数：构建一个简单的二叉树，并分别调用前序、中序、后序遍历函数输出结果。

遍历结果推导

对于上述构建的二叉树：

       1
      / \
     2   3
    / \
   4   5
  • 前序遍历：先访问根节点 1，然后遍历左子树（左子树的根节点是 2，继续前序遍历左子树得到 4，再遍历 2 的右子树得到 5），最后遍历右子树（得到 3），所以前序遍历结果是 1 2 4 5 3。
  • 中序遍历：先遍历左子树（左子树的中序遍历顺序是 4 2 5），再访问根节点 1，最后遍历右子树（得到 3），所以中序遍历结果是 4 2 5 1 3。
  • 后序遍历：先遍历左子树（左子树的后序遍历顺序是 4 5 2），再遍历右子树（得到 3），最后访问根节点 1，所以后序遍历结果是 4 5 2 3 1。

2.层序遍历

原理

层序遍历是按照二叉树的层次，从上到下、从左到右依次访问每个节点。通常借助队列来实现，先将根节点入队，然后不断从队列中取出节点，访问该节点并将其左右子节点入队，直到队列为空。

代码实现

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

// 定义二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 定义队列节点结构
typedef struct QueueNode {
    TreeNode* treeNode;
    struct QueueNode* next;
} QueueNode;

// 定义队列结构
typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

// 入队操作
void enqueue(Queue* q, TreeNode* node) {
    QueueNode* newQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
    newQueueNode->treeNode = node;
    newQueueNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newQueueNode;
    } else {
        q->rear->next = newQueueNode;
        q->rear = newQueueNode;
    }
}

// 出队操作
TreeNode* dequeue(Queue* q) {
    if (q->front == NULL) {
        return NULL;
    }
    QueueNode* temp = q->front;
    TreeNode* treeNode = temp->treeNode;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return treeNode;
}

// 判断队列是否为空
int isEmpty(Queue* q) {
    return q->front == NULL;
}

// 层序遍历
void levelOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    while (!isEmpty(&q)) {
        TreeNode* current = dequeue(&q);
        printf("%d ", current->data);
        if (current->left != NULL) {
            enqueue(&q, current->left);
        }
        if (current->right != NULL) {
            enqueue(&q, current->right);
        }
    }
}

// 释放二叉树节点内存
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// 释放队列中可能残留的节点
void freeQueue(Queue* q) {
    while (!isEmpty(q)) {
        dequeue(q);
    }
}

int main() {
    // 构建一个简单的二叉树
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("层序遍历结果: ");
    levelOrder(root);
    printf("\n");

    // 释放二叉树节点内存
    freeTree(root);

    return 0;
}

代码解释

  • QueueNode 结构体：定义了队列节点的结构，包含一个指向二叉树节点的指针 treeNode 和指向下一个队列节点的指针 next。
  • Queue 结构体：定义了队列的结构，包含队头指针 front 和队尾指针 rear。
  • initQueue 函数：初始化队列，将队头和队尾指针都置为 NULL。
  • enqueue 函数：将一个二叉树节点入队，创建一个新的队列节点并添加到队尾。
  • dequeue 函数：将队头节点出队，返回该节点对应的二叉树节点，并释放队列节点的内存。
  • isEmpty 函数：判断队列是否为空。
  • levelOrder 函数：实现层序遍历，先将根节点入队，然后不断从队列中取出节点，访问该节点并将其左右子节点入队，直到队列为空。
  • main 函数：构建一个简单的二叉树，并调用层序遍历函数输出结果。

遍历结果推导

对于上述构建的二叉树，层序遍历从根节点 1 开始，将其入队，然后取出 1 并访问，接着将 1 的左右子节点 2 和 3 入队；取出 2 并访问，将 2 的左右子节点 4 和 5 入队；依次取出 3、4、5 并访问，所以层序遍历结果是 1 2 3 4 5。

二、线索二叉树

原理

普通二叉树中存在大量的空指针域，线索二叉树就是利用这些空指针域来存储节点的前驱和后继信息，从而加快遍历速度。为了区分指针指向的是子节点还是前驱 / 后继节点，需要为每个节点增加两个标志位 ltag 和 rtag。

代码实现

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

// 定义线索二叉树节点结构
typedef struct ThreadedTreeNode {
    int data;
    struct ThreadedTreeNode *left;
    struct ThreadedTreeNode *right;
    int ltag;  // 左标志，0 表示指向左子节点，1 表示指向前驱节点
    int rtag;  // 右标志，0 表示指向右子节点，1 表示指向后继节点
} ThreadedTreeNode;

// 全局变量，用于记录前驱节点
ThreadedTreeNode *pre = NULL;

// 创建新节点
ThreadedTreeNode* createNode(int value) {
    ThreadedTreeNode* newNode = (ThreadedTreeNode*)malloc(sizeof(ThreadedTreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->ltag = 0;
    newNode->rtag = 0;
    return newNode;
}

// 中序线索化二叉树
void inorderThreading(ThreadedTreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderThreading(root->left);
    if (root->left == NULL) {
        root->left = pre;
        root->ltag = 1;
    }
    if (pre != NULL && pre->right == NULL) {
        pre->right = root;
        pre->rtag = 1;
    }
    pre = root;
    inorderThreading(root->right);
}

// 中序遍历线索二叉树
void inorderTraversal(ThreadedTreeNode* root) {
    ThreadedTreeNode *p = root;
    while (p != NULL) {
        while (p->ltag == 0) {
            p = p->left;
        }
        printf("%d ", p->data);
        while (p->rtag == 1) {
            p = p->right;
            printf("%d ", p->data);
        }
        p = p->right;
    }
}

// 释放线索二叉树节点内存
void freeThreadedTree(ThreadedTreeNode* root) {
    if (root == NULL) {
        return;
    }
    // 若左指针指向的是子节点而非线索，则递归释放左子树
    if (root->ltag == 0) {
        freeThreadedTree(root->left);
    }
    // 若右指针指向的是子节点而非线索，则递归释放右子树
    if (root->rtag == 0) {
        freeThreadedTree(root->right);
    }
    free(root);
}

int main() {
    // 构建一个简单的二叉树
    ThreadedTreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // 中序线索化
    inorderThreading(root);

    // 中序遍历线索二叉树
    printf("中序遍历线索二叉树结果：");
    inorderTraversal(root);
    printf("\n");

    // 释放线索二叉树节点内存
    freeThreadedTree(root);

    return 0;
}

代码解释

  • ThreadedTreeNode 结构体：定义了线索二叉树节点的结构，除了数据域和左右指针外，还增加了 ltag 和 rtag 标志位。
  • pre 全局变量：用于记录中序遍历过程中的前驱节点。
  • createNode 函数：创建新的线索二叉树节点，并初始化标志位。
  • inorderThreading 函数：对二叉树进行中序线索化。在中序遍历过程中，若节点的左指针为空，则将其指向前驱节点，并将 ltag 置为 1；若前驱节点的右指针为空，则将其指向当前节点，并将 rtag 置为 1。
  • inorderTraversal 函数：中序遍历线索二叉树。利用线索信息，快速找到节点的前驱和后继节点，实现高效遍历。
  • main 函数：构建一个简单的二叉树，调用 inorderThreading 函数进行中序线索化，再调用 inorderTraversal 函数进行中序遍历输出。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布