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

Rossy Yan

发布于 2024-12-27 08:06:23

3810

文章被收录于专栏：【Educoder实训】头歌实践教学平台【Educoder实训】头歌实践教学平台

任务描述

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

相关知识

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

二叉树的基本概念与结构定义
建立二叉树
先序遍历
中序遍历
后序遍历
层次遍历

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 **********/