【408考点之数据结构】树和森林的基本概念、二叉树转森林、以及树和森林的遍历

树和森林的基本概念、二叉树转森林、以及树和森林的遍历

一、树和森林的基本概念

树（Tree） 是一种重要的非线性数据结构，由n(n≥0)个节点组成，其中有一个根节点和若干子树，这些子树又是若干树的集合。

森林（Forest） 是m(m≥0)棵互不相交的树的集合。也就是说，森林是由多棵树组成的集合。

二、二叉树转森林

将一棵二叉树转化为森林的过程如下：

1. 删除二叉树的根节点：将根节点删除，二叉树会分成两棵子树。
2. 将两棵子树分别作为森林中的两棵树：删除根节点后，左子树和右子树分别成为森林中的两棵树。

具体步骤如下：

1. 选择一个节点作为根，将其左子树的根节点的右子树作为第一棵树，右子树的根节点的左子树作为第二棵树。
2. 重复该过程直到处理完所有节点。

三、树和森林的遍历

树和森林的遍历方法主要包括深度优先遍历和广度优先遍历。

1. 深度优先遍历（Depth First Traversal）：包括先序遍历、中序遍历和后序遍历。

   • 先序遍历（Preorder Traversal）：

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

     void preorderTraversal(TreeNode *root) {
         if (root) {
             printf("%d ", root->data);
             preorderTraversal(root->left);
             preorderTraversal(root->right);
         }
     }
     

   • 中序遍历（Inorder Traversal）：

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

     void inorderTraversal(TreeNode *root) {
         if (root) {
             inorderTraversal(root->left);
             printf("%d ", root->data);
             inorderTraversal(root->right);
         }
     }
     

   • 后序遍历（Postorder Traversal）：

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

     void postorderTraversal(TreeNode *root) {
         if (root) {
             postorderTraversal(root->left);
             postorderTraversal(root->right);
             printf("%d ", root->data);
         }
     }
     

2. 广度优先遍历（Breadth First 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);
       }
   }