数据结构二叉树先序中序后序遍历代码
时间: 2023-11-16 11:01:41 浏览: 47
以下是二叉树先序、中序、后序遍历的代码实现:
```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 << " "; // 访问根节点
}
```
数据结构二叉树先序中序后序遍历递归输出
二叉树的先序遍历、中序遍历和后序遍历是三种常用的递归算法。先序遍历的顺序是根节点-左子树-右子树,中序遍历的顺序是左子树-根节点-右子树,后序遍历的顺序是左子树-右子树-根节点。
以下是二叉树先序、中序和后序遍历的递归输出的代码示例:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 先序遍历
def preorderTraversal(root):
if root is None:
return []
res = []
res.append(root.val)
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
# 中序遍历
def inorderTraversal(root):
if root is None:
return []
res = []
res += inorderTraversal(root.left)
res.append(root.val)
res += inorderTraversal(root.right)
return res
# 后序遍历
def postorderTraversal(root):
if root is None:
return []
res = []
res += postorderTraversal(root.left)
res += postorderTraversal(root.right)
res.append(root.val)
return res
# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 输出结果
print("先序遍历:", preorderTraversal(root))
print("中序遍历:", inorderTraversal(root))
print("后序遍历:", postorderTraversal(root))
```