【408考点之数据结构】二叉树的遍历及线索二叉树

二叉树的遍历及线索二叉树

一、二叉树的遍历

二叉树的遍历是指按照一定的顺序访问二叉树中所有节点。常见的遍历方法有前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）、后序遍历（Postorder Traversal）和层次遍历（Level Order Traversal）。

1. 前序遍历（Preorder Traversal）：

   • 过程：访问根节点 -> 前序遍历左子树 -> 前序遍历右子树
   • 代码实现：

   void preorderTraversal(TreeNode *root) {
       if (root) {
           printf("%d ", root->data);
           preorderTraversal(root->left);
           preorderTraversal(root->right);
       }
   }
   1
   2
   3
   4
   5
   6
   7

2. 中序遍历（Inorder Traversal）：

   • 过程：中序遍历左子树 -> 访问根节点 -> 中序遍历右子树
   • 代码实现：

   void inorderTraversal(TreeNode *root) {
       if (root) {
           inorderTraversal(root->left);
           printf("%d ", root->data);
           inorderTraversal(root->right);
       }
   }
   1
   2
   3
   4
   5
   6
   7

3. 后序遍历（Postorder Traversal）：

   • 过程：后序遍历左子树 -> 后序遍历右子树 -> 访问根节点
   • 代码实现：

   void postorderTraversal(TreeNode *root) {
       if (root) {
           postorderTraversal(root->left);
           postorderTraversal(root->right);
           printf("%d ", root->data);
       }
   }
   1
   2
   3
   4
   5
   6
   7

4. 层次遍历（Level Order Traversal）：

   • 过程：按照层次从上到下、从左到右依次访问各节点
   • 代码实现：

   #include <stdio.h>
   #include <stdlib.h>
   #define MAX_QUEUE_SIZE 100
   
   typedef struct TreeNode {
       int data;
       struct TreeNode *left;
       struct TreeNode *right;
   } TreeNode;
   
   typedef struct {
       TreeNode *data[MAX_QUEUE_SIZE];
       int front;
       int rear;
   } Queue;
   
   void initQueue(Queue *q) {
       q->front = q->rear = 0;
   }
   
   int isQueueEmpty(Queue *q) {
       return q->front == q->rear;
   }
   
   void enqueue(Queue *q, TreeNode *node) {
       if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front) {
           printf("Queue is full\n");
           return;
       }
       q->data[q->rear] = node;
       q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
   }
   
   TreeNode* dequeue(Queue *q) {
       if (isQueueEmpty(q)) {
           printf("Queue is empty\n");
           return NULL;
       }
       TreeNode *node = q->data[q->front];
       q->front = (q->front + 1) % MAX_QUEUE_SIZE;
       return node;
   }
   
   void levelOrderTraversal(TreeNode *root) {
       if (!root) return;
       Queue q;
       initQueue(&q);
       enqueue(&q, root);
       while (!isQueueEmpty(&q)) {
           TreeNode *node = dequeue(&q);
           printf("%d ", node->data);
           if (node->left) enqueue(&q, node->left);
           if (node->right) enqueue(&q, node->right);
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55

二、线索二叉树

线索二叉树是一种特殊的二叉树，通过对空指针加以利用，使得二叉树的遍历更加高效。在线索二叉树中，每个节点的空指针指向在某种遍历方式下的前驱或后继节点。

1. 线索的定义：

   • 前驱（Predecessor）：在某种遍历方式下，当前节点的前一个节点。
   • 后继（Successor）：在某种遍历方式下，当前节点的后一个节点。

2. 线索二叉树的类型：

   • 前序线索二叉树（Preorder Threaded Binary Tree）：前序遍历下的前驱和后继。
   • 中序线索二叉树（Inorder Threaded Binary Tree）：中序遍历下的前驱和后继。
   • 后序线索二叉树（Postorder Threaded Binary Tree）：后序遍历下的前驱和后继。

3. 线索二叉树的结构定义：

   typedef struct ThreadedTreeNode {
       int data;
       struct ThreadedTreeNode *left;
       struct ThreadedTreeNode *right;
       int ltag; // 0: left指向左孩子, 1: left指向前驱
       int rtag; // 0: right指向右孩子, 1: right指向后继
   } ThreadedTreeNode;
   1
   2
   3
   4
   5
   6
   7

4. 中序线索二叉树的建立：

   void createInorderThread(ThreadedTreeNode *root, ThreadedTreeNode **pre) {
       if (root) {
           createInorderThread(root->left, pre);
           if (!root->left) {
               root->left = *pre;
               root->ltag = 1;
           }
           if (*pre && !(*pre)->right) {
               (*pre)->right = root;
               (*pre)->rtag = 1;
           }
           *pre = root;
           createInorderThread(root->right, pre);
       }
   }
   
   void createInorderThreadTree(ThreadedTreeNode *root) {
       ThreadedTreeNode *pre = NULL;
       if (root) {
           createInorderThread(root, &pre);
           if (pre->right == NULL) {
               pre->rtag = 1;
           }
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25

5. 中序线索二叉树的遍历：

   void inorderThreadedTraversal(ThreadedTreeNode *root) {
       ThreadedTreeNode *p = root;
       while (p) {
           while (p->ltag == 0) {
               p = p->left;
           }
           printf("%d ", p->data);
           while (p->rtag == 1 && p->right != NULL) {
               p = p->right;
               printf("%d ", p->data);
           }
           p = p->right;
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14

使用场景

1. 表达式树的构建和求值：通过中序遍历和后序遍历，可以有效地对表达式进行解析和求值。
2. 数据库查询优化：使用线索二叉树可以加快查询速度，减少查询时间。
3. 文件系统管理：层次遍历用于文件系统目录的遍历，便于管理和查找文件。
4. 数据压缩与编码：霍夫曼树利用二叉树结构实现高效的编码和解码。