编写先序遍历算法

先序遍历是二叉树遍历的一种方式，遍历顺序为：根节点 -> 左子树 -> 右子树。以下是先序遍历的算法实现：

1. 如果当前节点为空，则返回。
2. 对于当前节点，先输出当前节点的值。
3. 递归遍历当前节点的左子树。
4. 递归遍历当前节点的右子树。

以下是先序遍历的算法实现示例（假设二叉树使用链表存储）：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder_traversal(root: TreeNode):
    if not root:
        return
    print(root.val)
    preorder_traversal(root.left)
    preorder_traversal(root.right)

代码中的 `TreeNode` 类定义了二叉树的节点结构。函数 `preorder_traversal` 实现了先序遍历，它首先输出当前节点的值，然后递归遍历左子树和右子树。如果当前节点为空，则函数直接返回。

相关问题

C++编写先序遍历的非递归算法

下面是C++编写的先序遍历非递归算法：

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        if (root != nullptr) {
            s.push(root);  // 将根节点入栈
        }
        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();  // 弹出栈顶节点
            res.push_back(node->val);  // 将节点值加入到结果中
            if (node->right != nullptr) {
                s.push(node->right);  // 右子树入栈
            }
            if (node->left != nullptr) {
                s.push(node->left);  // 左子树入栈
            }
        }
        return res;
    }
};

该算法利用了栈来模拟递归过程，先将根节点入栈，然后每次弹出栈顶节点，并将其值加入到结果中，接着将右子树和左子树依次入栈。

编写先序遍历的非递归算法，显示二叉树的先序序列

先序遍历的非递归算法可以使用栈来实现。具体步骤如下：

1. 将根节点入栈。
2. 当栈不为空时，执行以下操作：
a. 弹出栈顶节点，并将其值输出。
b. 如果该节点有右子节点，则将右子节点入栈。
c. 如果该节点有左子节点，则将左子节点入栈。
3. 遍历结束。

下面是一个示例代码：

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";
        if (node->right != nullptr) {
            s.push(node->right);
        }
        if (node->left != nullptr) {
            s.push(node->left);
        }
    }
}

假设有如下二叉树：

    1
   / \
  2   3
 / \   \
4   5   6

使用上述算法遍历该二叉树的先序序列为：1 2 4 5 3 6。