数据结构二叉树先序中序后序遍历代码
时间: 2023-11-16 08:01:41 浏览: 105
以下是二叉树先序、中序、后序遍历的代码实现:
```python
# 先序遍历
def preorder_traversal(root):
if root:
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
# 中序遍历
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
# 后序遍历
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val)
```
其中,`root`表示二叉树的根节点,`val`表示节点的值,`left`和`right`分别表示左子树和右子树。
先序遍历的顺序是:根节点 -> 左子树 -> 右子树。
中序遍历的顺序是:左子树 -> 根节点 -> 右子树。
后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
相关问题
数据结构二叉树先序中序后序遍历递归
二叉树的先序、中序和后序遍历是通过递归实现的。先序遍历指的是先访问根节点,然后依次对左子树和右子树进行先序遍历;中序遍历指的是先对左子树进行中序遍历,然后访问根节点,最后对右子树进行中序遍历;后序遍历指的是先对左子树进行后序遍历,然后对右子树进行后序遍历,最后访问根节点。
递归实现先序遍历的代码如下:
```
void preOrderTraversal(TreeNode *root) {
if (root == nullptr) {
return;
}
cout << root->val << " "; // 访问根节点
preOrderTraversal(root->left); // 先序遍历左子树
preOrderTraversal(root->right); // 先序遍历右子树
}
```
递归实现中序遍历的代码如下:
```
void inOrderTraversal(TreeNode *root) {
if (root == nullptr) {
return;
}
inOrderTraversal(root->left); // 中序遍历左子树
cout << root->val << " "; // 访问根节点
inOrderTraversal(root->right); // 中序遍历右子树
}
```
递归实现后序遍历的代码如下:
```
void postOrderTraversal(TreeNode *root) {
if (root == nullptr) {
return;
}
postOrderTraversal(root->left); // 后序遍历左子树
postOrderTraversal(root->right); // 后序遍历右子树
cout << root->val << " "; // 访问根节点
}
```
数据结构C++二叉树的代码实现先序中序后序遍历
```C++
//定义二叉树结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
先序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
//中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
//后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
```
--相关问题--:
1. 如何构建一棵二叉树?
2. 二叉树的其他遍历方式有
阅读全文