【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题）【合集】

2025-01-08 12

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。

目录😋

任务描述

本关任务：实现二叉树的遍历

相关知识

为了完成本关任务，你需要掌握：

二叉树的基本概念与结构定义

建立二叉树

先序遍历

中序遍历

后序遍历

层次遍历

1. 二叉树的基本概念与结构定义

二叉树是树形结构的一种特殊形式，它的每个节点最多有两个子节点，分别称为左子节点和右子节点，对应的子树就是左子树和右子树。二叉树可以为空（即没有节点），也可以由根节点、左子树和右子树组成复杂的树形结构，这种结构在很多数据处理场景中有着重要应用，例如表达式解析、文件系统目录结构模拟、搜索算法实现等。

在 C++ 中，我们通常使用结构体（struct）或者类（class）来定义二叉树的节点结构，下面以结构体为例：

#include <iostream>
using namespace std;
// 定义二叉树节点结构体
struct TreeNode {
    int val;  // 节点存储的值，可以根据实际需求修改类型，比如存储字符、结构体等其他复杂类型
    TreeNode* left;  // 指向左子树的指针
    TreeNode* right; // 指向右子树的指针
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}  // 构造函数，用于方便地初始化节点
};

在上述代码中：

val 成员变量用于存储节点所包含的数据，比如数字、字符等，这里定义为 int 类型只是一个示例，实际应用中可按需调整。

left 和 right 是指针类型，分别用于指向该节点的左子树和右子树的根节点，如果相应子树不存在，则指针为 NULL。

自定义的构造函数 TreeNode(int x) 接受一个参数，用于初始化节点的值，并将左、右子树指针初始化为 NULL，这样在创建节点时能更方便地进行初始化操作。

2. 建立二叉树

(1) 手动输入构建二叉树示例

下面是一种简单的通过手动输入节点值来构建二叉树的方式，采用递归的思想：

#include <iostream>
using namespace std;
// 定义二叉树节点结构体
struct TreeNode {
    int val;  // 节点存储的值，可以根据实际需求修改类型
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 构建二叉树的函数（简单示例，这里采用手动输入的方式构建，实际可按具体需求从文件等读取数据构建）
TreeNode* buildTree() {
    int data;
    cin >> data;
    if (data == -1) {  // 用 -1 表示空节点
        return NULL;
    }
    TreeNode* root = new TreeNode(data);
    root->left = buildTree();
    root->right = buildTree();
    return root;
}

代码的详细解释如下：

首先，程序从标准输入读取一个整数值到变量 data 中，这个值将作为当前节点要存储的值。

接着，通过判断 data 的值来确定是否创建节点。如果 data 的值为 -1，按照我们的约定，这表示当前节点为空，直接返回 NULL，意味着这个位置在二叉树中不存在实际节点。

若 data 不为 -1，则创建一个新的 TreeNode 类型的节点，使用刚才读取到的值通过构造函数进行初始化，也就是 root = new TreeNode(data) 这一步，此时新节点的 left 和 right 指针初始化为 NULL。

然后，递归地调用 buildTree 函数来构建当前节点的左子树，将返回的左子树的根节点指针赋值给 root->left；同样地，再次递归调用 buildTree 函数来构建右子树，并将右子树的根节点指针赋值给 root->right。

最后，返回构建好的以 root 为根节点的二叉树的根节点指针，这样就完成了整个二叉树的构建过程。

例如，按照以下输入顺序（假设输入顺序是先根节点，再左子树节点，然后右子树节点，空节点用 -1 表示）来构建一棵二叉树：

1
2
-1
-1
3
-1
-1

它将构建出这样一棵简单的二叉树：

    1
   / \
  2   3

(2) 从数组构建二叉树示例

除了手动输入的方式，还可以从给定的数组来构建二叉树，以下是一个示例代码，假设数组按照完全二叉树的层次遍历顺序存储节点值（空节点用特定值表示，这里同样用 -1）：

TreeNode* buildTreeFromArray(int arr[], int index, int n) {
    if (index >= n || arr[index] == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(arr[index]);
    root->left = buildTreeFromArray(arr, 2 * index + 1, n);
    root->left = buildTreeFromArray(arr, 2 * index + 2, n);
    return root;
}

3. 先序遍历

先序遍历的顺序是根节点 -> 左子树 -> 右子树。可以通过递归方式很方便地实现。

递归实现先序遍历的代码如下：

// 先序遍历二叉树
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";  // 访问根节点
    preorderTraversal(root->left);  // 遍历左子树
    preorderTraversal(root->right);  // 遍历右子树
}

代码逻辑详细解释如下：

首先进行边界判断，当传入的根节点指针 root 为 NULL 时，说明已经遍历到了空子树或者二叉树本身为空，此时直接返回，不需要进行后续操作。

如果根节点不为 NULL，那么按照先序遍历的顺序，首先要访问根节点。这里通过 cout << root->val << " "; 语句将根节点的值输出显示，这只是一种简单的访问方式示例，在实际应用中，比如要将遍历结果存储起来用于后续处理，可以把节点值存储到一个数组或者其他合适的数据结构中。

接着，递归调用 preorderTraversal 函数去遍历左子树，这一步会以同样的逻辑去访问左子树的根节点、左子树的左子树、左子树的右子树等，直到左子树遍历完，也就是遇到叶子节点（其左子树和右子树都为 NULL）。

最后，再递归调用 preorderTraversal 函数去遍历右子树，同样会按照先序遍历的规则去访问右子树中的各个节点，直至整个二叉树的所有节点都被访问完。

例如，对于前面构建的二叉树：

    1
   / \
  2   3

先序遍历的输出结果将是：1 2 3。

4. 中序遍历

中序遍历的顺序是左子树 -> 根节点 -> 右子树。

其递归实现代码如下：

// 中序遍历二叉树
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);  // 遍历左子树
    cout << root->val << " ";  // 访问根节点
    inorderTraversal(root->right);  // 遍历右子树
}

具体的代码逻辑解释如下：

同样先进行边界判断，若根节点指针 root 为 NULL，说明已经遍历完或者二叉树本身为空，直接返回，避免后续无效操作。

当根节点不为 NULL 时，按照中序遍历的规则，首先要递归地遍历左子树，也就是从最底层的左子树节点开始访问，一直向上到根节点的左子节点，这个过程中会依次访问左子树中的各个节点，直到左子树遍历完毕。

然后，访问当前的根节点，通过 cout << root->val << " "; 输出根节点的值（同样这只是简单访问示例，可按需改变操作）。

最后，递归遍历右子树，以同样的中序遍历规则去访问右子树中的各个节点，直到整个二叉树的所有节点都被访问到。

对于上述示例二叉树：

    1
   / \
  2   3

中序遍历的输出结果是：2 1 3。

5. 后序遍历

后序遍历的顺序是左子树 -> 右子树 -> 根节点。

其递归实现如下：

  // 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);  // 遍历左子树
    postorderTraversal(root->right);  // 遍历右子树
    cout << root->val << " ";  // 访问根节点
}

详细的代码逻辑说明如下：

开始先判断根节点是否为 NULL，若是则直接返回，因为已经遍历完或者二叉树为空。

若根节点不为 NULL，首先递归地遍历左子树，按照后序遍历的要求，从左子树的最底层叶子节点开始，依次访问左子树中的各个节点，直到左子树全部遍历完成。

接着，递归遍历右子树，同样以左子树的遍历方式，从右子树的底层开始，逐步向上访问右子树的各个节点，直至右子树遍历完毕。

最后，访问当前的根节点，输出根节点的值（示例中是简单打印，实际可根据具体需求进行其他处理），这样就按照后序遍历的顺序访问了整个二叉树的所有节点。

对于前面给出的示例二叉树：

    1
   / \
  2   3

后序遍历的输出结果是：2 3 1。

6. 层次遍历

层次遍历是按照二叉树的层次，从根节点开始，逐层向下访问各个节点，通常借助队列（queue）数据结构来实现。

以下是使用 C++ 标准库中的 queue 实现层次遍历的详细示例代码：

#include <iostream>
#include <queue>
using namespace std;
// 层次遍历二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    queue<TreeNode*> q;  // 创建一个存储 TreeNode* 类型的队列，用于存放节点指针
    q.push(root);  // 首先将根节点入队
    while (!q.empty()) {  // 只要队列不为空，就继续循环进行遍历操作
        TreeNode* node = q.front();  // 获取队列头部的节点
        q.pop();  // 将队列头部的节点出队
        cout << node->val << " ";  // 访问当前节点，这里同样是简单输出节点值，可按需改变操作
        if (node->left!= NULL) {  // 判断当前节点的左子树是否存在
            q.push(node->left);  // 如果存在，将左子树节点入队
        }
        if (node->right!= NULL) {  // 判断当前节点的右子树是否存在
            q.push(node->right);  // 如果存在，将右子树节点入队
        }
    }
}

代码的详细逻辑解释如下：

首先进行根节点是否为空的判断，若为空则直接返回，因为空二叉树不需要进行遍历操作。

创建一个 queue<TreeNode*> 类型的队列，用于存储二叉树的节点指针，然后将根节点指针 root 通过 q.push(root) 操作入队，这是层次遍历的起始点。

进入 while 循环，只要队列不为空，就表示还有节点需要遍历。在循环中：

首先通过 q.front() 获取队列头部的节点指针，并将其赋值给 node，然后通过 q.pop() 将队列头部的节点出队，这一步是按照先进先出的原则处理队列中的节点。

接着访问当前节点，示例中通过 cout << node->val << " "; 输出节点的值，实际应用中可以根据需求进行更复杂的操作，比如将节点值存储到二维数组中，按照层次结构来存储，便于后续的处理和展示等。

之后，判断当前节点的左子树是否存在，如果左子树节点指针不为 NULL，则通过 q.push(node->left) 将左子树节点入队，以便后续按照层次顺序访问它。

同样地，判断当前节点的右子树是否存在，若右子树节点指针不为 NULL，则通过 q.push(node->right) 将右子树节点入队。

通过不断地循环上述操作，队列会依次存储和取出每一层的节点，从而实现按照层次顺序遍历整个二叉树的所有节点。

例如，对于以下稍微复杂一点的二叉树：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

层次遍历的输出结果将是：1 2 3 4 5 6 7。

测试说明

平台会对你编写的代码进行测试：

测试输入：

A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

预期输出：

二叉树b:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
层次遍历序列:A B C D E F G H I J K L M N
先序遍历序列:A B D E H J K L M N C F G I
中序遍历序列:D B J H L K M N E A F C G I
后序遍历序列:D J L N M K H E B F I G C A

开始你的任务吧，祝你成功！

通关代码

// 请在Begin-End之间添加你的代码，
//实现二叉树遍历的基本运算//
//对括号表示串的二叉树进行遍历，由用户输入括号表示串//
//实现二叉树的先序遍历、中序遍历、后序遍历、层次遍历//
/********** Begin *********/
#include <bits/stdc++.h>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct node {
  ElemType data;
  struct node *lchild;
  struct node *rchild;
} BTNode;
typedef struct {
  BTNode *data[MaxSize];
  int front, rear;
} SqQueue;
void CreateBTree(BTNode *&b, char *str) {
  BTNode *St[MaxSize], *p;
  int top = -1, k, j = 0;
  char ch;
  b = nullptr;
  ch = str[j];
  while (ch != '\0') {
    switch (ch) {
    case '(':
      top++;
      St[top] = p;
      k = 1;
      break;
    case ')':
      top--;
      break;
    case ',':
      k = 2;
      break;
    default:
      p = (BTNode *)malloc(sizeof(BTNode));
      p->data = ch;
      p->lchild = p->rchild = nullptr;
      if (b == nullptr)
        b = p;
      else {
        switch (k) {
        case 1:
          St[top]->lchild = p;
          break;
        case 2:
          St[top]->rchild = p;
          break;
        }
      }
    }
    j++;
    ch = str[j];
  }
}
void DispBTree(BTNode *b) {
  if (b != nullptr) {
    printf("%c", b->data);
    if (b->lchild != nullptr || b->rchild != nullptr) {
      printf("(");
      DispBTree(b->lchild);
      if (b->rchild != nullptr)
        printf(",");
      DispBTree(b->rchild);
      printf(")");
    }
  }
}
void InitQueue(SqQueue *&q) {
  q = (SqQueue *)malloc(sizeof(SqQueue));
  q->front = q->rear = 0;
}
void DestroyQueue(SqQueue *&q) { free(q); }
bool QueueEmpty(SqQueue *q) { return (q->front == q->rear); }
bool enQueue(SqQueue *&q, BTNode *e) {
  if ((q->rear + 1) % MaxSize == q->front) {
    return false;
  }
  q->rear = (q->rear + 1) % MaxSize;
  q->data[q->rear] = e;
  return true;
}
bool deQueue(SqQueue *&q, BTNode *&e) {
  if (q->front == q->rear)
    return false;
  q->front = (q->front + 1) % MaxSize;
  e = q->data[q->front];
  return true;
}
void LevelOrder(BTNode *b) {
  BTNode *p;
  SqQueue *qu;
  InitQueue(qu);
  enQueue(qu, b);
  while (!QueueEmpty(qu)) {
    deQueue(qu, p);
    printf("%c ", p->data);
    if (p->lchild != nullptr)
      enQueue(qu, p->lchild);
    if (p->rchild != nullptr)
      enQueue(qu, p->rchild);
  }
  DestroyQueue(qu);
}
void PreOrder(BTNode *b) {
  if (b != nullptr) {
    printf("%c ", b->data);
    PreOrder(b->lchild);
    PreOrder(b->rchild);
  }
}
void InOrder(BTNode *b) {
  if (b != nullptr) {
    InOrder(b->lchild);
    printf("%c ", b->data);
    InOrder(b->rchild);
  }
}
void PostOrder(BTNode *b) {
  if (b != nullptr) {
    PostOrder(b->lchild);
    PostOrder(b->rchild);
    printf("%c ", b->data);
  }
}
int main() {
  char str[100];
  cin >> str;
  BTNode *b;
  CreateBTree(b, str);
  cout << "二叉树b:";
  DispBTree(b);
  cout << endl;
  cout << "层次遍历序列:";
  LevelOrder(b);
  cout << endl;
  cout << "先序遍历序列:";
  PreOrder(b);
  cout << endl;
  cout << "中序遍历序列:";
  InOrder(b);
  cout << endl;
  cout << "后序遍历序列:";
  PostOrder(b);
  return 0;
}
/********** End **********/

【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题）【合集】

任务描述

相关知识

1. 二叉树的基本概念与结构定义

2. 建立二叉树

3. 先序遍历

4. 中序遍历

5. 后序遍历

6. 层次遍历

测试说明

通关代码

测试结果

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】

任务描述

相关知识

1. 二叉树的基本概念与结构定义

2. 建立二叉树

3. 先序遍历

4. 中序遍历

5. 后序遍历

6. 层次遍历

测试说明

通关代码

测试结果

热门文章

最新文章

相关课程

相关电子书

相关实验场景

【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题）【合集】