深度优先搜索 前序遍历

深度优先搜索（DFS，Depth-First Search）是一种用于遍历或搜索树或图的算法。在深度优先搜索中，算法会尽可能深地沿着树或图的分支进行搜索，直到搜索的分支结束，然后回溯到上一个节点继续搜索其他分支。这种搜索方式是通过递归或栈实现的。

前序遍历是深度优先搜索在树结构中的一种遍历方式，它包括以下三个步骤：
1. 访问根节点；
2. 递归地进行前序遍历左子树；
3. 递归地进行前序遍历右子树。

前序遍历的一个特点是，它保证在访问节点的子节点之前访问该节点本身，这使得前序遍历非常适合执行某些特定操作，比如复制一个树结构。

以一个简单的二叉树为例，前序遍历的顺序通常是：根节点 -> 左子树 -> 右子树。

相关问题

树的深度优先遍历是前序遍历中序遍历和后序遍历吗

树的深度优先遍历包括前序遍历、中序遍历和后序遍历，它们的遍历顺序规则分别为：

前序遍历(Preorder traversal)：遍历顺序规则为【DLR | 即当前结点, 左孩子, 右孩子】。

中序遍历(Inorder Traversal)：遍历顺序规则为【LDR | 即左孩子, 当前结点, 右孩子】。

后序遍历(Postorder Traversal)：遍历顺序规则为【LRD | 即左孩子, 右孩子, 当前结点】。

因此，深度优先遍历不是前序遍历、中序遍历和后序遍历的统称，而是包括了这三种遍历方式。

下面是C++代码实现：

递归实现：

// 前序遍历
void preorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// 中序遍历
void inorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// 后序遍历
void postorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

非递归实现：

// 前序遍历
void preorder(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);
        }
    }
}

// 中序遍历
void inorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (node != nullptr || !s.empty()) {
        while (node != nullptr) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

// 后序遍历
void postorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        TreeNode* node = s1.top();
        s1.pop();
        s2.push(node);
        if (node->left != nullptr) {
            s1.push(node->left);
        }
        if (node->right != nullptr) {
            s1.push(node->right);
        }
    }
    while (!s2.empty()) {
        cout << s2.top()->val << " ";
        s2.pop();
    }
}

深度优先前序遍历二叉树代码

深度优先前序遍历二叉树是一种常用的遍历方式，它的代码实现如下：

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

def preorderTraversal(root):
    if root is None:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

上述代码中，我们使用了一个栈来辅助实现深度优先前序遍历。首先，我们将根节点入栈。然后，从栈中弹出一个节点，将其值加入结果列表中，并依次将右子节点和左子节点入栈。重复这个过程，直到栈为空。