当前位置:   article > 正文

【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);
          }
      }
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
    • 中序遍历(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
    • 后序遍历(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
  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);
        }
    }
    
    • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/781242
推荐阅读
相关标签
  

闽ICP备14008679号