数据结构中,二叉树的先序,中序,后序遍历的节点,如何遍历,详细介绍一下
时间: 2023-10-29 09:05:29 浏览: 37
二叉树是一种常用的数据结构,它由节点组成,每个节点最多有两个子节点。二叉树的遍历方式有三种:先序遍历、中序遍历和后序遍历。下面我将分别介绍这三种遍历方式。
1. 先序遍历
先序遍历是指先遍历根节点,然后遍历左子树,最后遍历右子树。
先序遍历的遍历顺序为:根节点 -> 左子树 -> 右子树。
先序遍历的实现可以使用递归或者栈来实现。递归实现的代码如下:
```
void preOrderTraversal(Node* root) {
if (root == nullptr) {
return;
}
// 遍历根节点
cout << root->val << " ";
// 遍历左子树
preOrderTraversal(root->left);
// 遍历右子树
preOrderTraversal(root->right);
}
```
2. 中序遍历
中序遍历是指先遍历左子树,然后遍历根节点,最后遍历右子树。
中序遍历的遍历顺序为:左子树 -> 根节点 -> 右子树。
中序遍历的实现可以使用递归或者栈来实现。递归实现的代码如下:
```
void inOrderTraversal(Node* root) {
if (root == nullptr) {
return;
}
// 遍历左子树
inOrderTraversal(root->left);
// 遍历根节点
cout << root->val << " ";
// 遍历右子树
inOrderTraversal(root->right);
}
```
3. 后序遍历
后序遍历是指先遍历左子树,然后遍历右子树,最后遍历根节点。
后序遍历的遍历顺序为:左子树 -> 右子树 -> 根节点。
后序遍历的实现可以使用递归或者栈来实现。递归实现的代码如下:
```
void postOrderTraversal(Node* root) {
if (root == nullptr) {
return;
}
// 遍历左子树
postOrderTraversal(root->left);
// 遍历右子树
postOrderTraversal(root->right);
// 遍历根节点
cout << root->val << " ";
}
```
以上是二叉树的三种遍历方式的详细介绍和递归实现代码。需要注意的是,在实际应用中,我们也可以使用非递归的方式来实现二叉树的遍历。