头歌数据结构深度优先遍历答案
时间: 2023-06-27 16:04:17 浏览: 89
深度优先遍历(Depth First Search,DFS)是一种用于遍历或搜索树或图的算法。其基本思想是从根节点开始,沿着一条路径尽可能深地搜索直到无法继续为止,然后回溯到上一个节点,再沿着另一条路径继续搜索,直到所有节点都被访问为止。
对于头歌数据结构的深度优先遍历,可以采用递归或栈的方式实现。具体步骤如下:
1. 从根节点开始遍历,将其标记为已访问。
2. 沿着任意一条未访问过的边继续遍历,直至遇到叶子节点或已访问过的节点。
3. 如果遇到叶子节点,则回溯到上一个节点,继续遍历其它子节点。
4. 如果遇到已访问过的节点,则回溯到上一个节点。
5. 重复步骤2~4,直至所有节点都被访问。
在具体实现中,可以使用递归方式实现深度优先遍历,代码如下:
```c++
void dfs(TreeNode *root) {
if (root == nullptr) {
return;
}
// 访问当前节点
cout << root->val << " ";
// 遍历左子树
dfs(root->left);
// 遍历右子树
dfs(root->right);
}
```
也可以使用栈方式实现深度优先遍历,代码如下:
```c++
void dfs(TreeNode *root) {
if (root == nullptr) {
return;
}
stack<TreeNode *> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode *cur = stk.top();
stk.pop();
// 访问当前节点
cout << cur->val << " ";
// 将右子树入栈
if (cur->right != nullptr) {
stk.push(cur->right);
}
// 将左子树入栈
if (cur->left != nullptr) {
stk.push(cur->left);
}
}
}
```