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

目录😋

任务描述

相关知识

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

2. 建立二叉树

3. 先序遍历

4. 中序遍历

5. 后序遍历

6. 层次遍历

测试说明

通关代码

测试结果

---

任务描述

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

相关知识

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

1. 二叉树的基本概念与结构定义
2. 建立二叉树
3. 先序遍历
4. 中序遍历
5. 后序遍历
6. 层次遍历

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

---

测试结果