数据结构二叉树的遍历代码

以下是二叉树的三种遍历方式的代码实现：

1. 先序遍历

def pre_order_traversal(root):
    if root:
        print(root.val)
        pre_order_traversal(root.left)
        pre_order_traversal(root.right)

2. 中序遍历

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.val)
        in_order_traversal(root.right)

3. 后序遍历

def post_order_traversal(root):
    if root:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.val)

相关问题

数据结构C语言二叉树遍历

二叉树遍历是指按照某种顺序依次遍历二叉树中各个节点，常用的遍历方式有前序遍历、中序遍历和后序遍历。在C语言中，我们可以通过递归或者使用栈来实现二叉树的遍历。以下是使用递归实现的代码模板：

//定义二叉树节点
typedef struct TreeNode{
int val;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;

//前序遍历
void PreorderTraversal(TreeNode* root){
if(root == NULL){
return;
}
printf("%d ", root->val);
PreorderTraversal(root->left);
PreorderTraversal(root->right);
}

//中序遍历
void InorderTraversal(TreeNode* root){
if(root == NULL){
return;
}
InorderTraversal(root->left);
printf("%d ", root->val);
InorderTraversal(root->right);
}

//后序遍历
void PostorderTraversal(TreeNode* root){
if(root == NULL){
return;
}
PostorderTraversal(root->left);
PostorderTraversal(root->right);
printf("%d ", root->val);
}

以上是常见的二叉树遍历方式，根据不同的需求选择不同的遍历方式即可。

数据结构构建二叉树遍历

二叉树的遍历方式主要有三种：前序遍历、中序遍历和后序遍历。

前序遍历的顺序是：根节点 -> 左子树 -> 右子树，即先访问根节点，再访问左子树，最后访问右子树。

中序遍历的顺序是：左子树 -> 根节点 -> 右子树，即先访问左子树，再访问根节点，最后访问右子树。

后序遍历的顺序是：左子树 -> 右子树 -> 根节点，即先访问左子树，再访问右子树，最后访问根节点。

二叉树的遍历可以使用递归或者栈来实现。以前序遍历为例，递归实现的代码如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def preorderTraversal(root: TreeNode) -> List[int]:
    res = []
    def dfs(node):
        if not node:
            return
        res.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return res

栈实现的代码如下：

def preorderTraversal(root: TreeNode) -> List[int]:
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        res.append(node.val)
        stack.append(node.right)
        stack.append(node.left)
    return res

其中，递归实现中的dfs函数表示对以node为根节点的子树进行前序遍历，栈实现中的stack保存的是待访问的节点，先将右子节点入栈，再将左子节点入栈，以确保先访问左子树。