【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
目录😋
任务描述
相关知识
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 -11 / \ 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 **********/
测试结果
