什么叫宣传类网站,网站建设 内容缺乏,电子商务网站开发教程论文6,个人站长网站需要注册公司吗目录#x1f60b;
任务描述
相关知识
1. 二叉树的基本概念与结构定义
2. 建立二叉树
3. 先序遍历
4. 中序遍历
5. 后序遍历
6. 层次遍历
测试说明
通关代码
测试结果 任务描述 本关任务#xff1a;实现二叉树的遍历 相关知识 为了完成本关任务#xff0c;你需要掌…目录
任务描述
相关知识
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;}queueTreeNode* 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); // 如果存在将右子树节点入队}}
} 代码的详细逻辑解释如下 首先进行根节点是否为空的判断若为空则直接返回因为空二叉树不需要进行遍历操作。创建一个 queueTreeNode* 类型的队列用于存储二叉树的节点指针然后将根节点指针 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 **********/测试结果
