头歌数据结构深度优先遍历答案
时间: 2023-09-04 19:09:32 浏览: 147
深度优先遍历(DFS)是一种遍历树或图的算法,它从根节点开始,沿着树的深度遍历完整个树或图。在深度优先遍历中,先遍历当前节点的所有子节点,再回溯到当前节点的父节点,直到遍历完整个树或图。
在头歌数据结构中,深度优先遍历的实现通常使用递归或栈来实现。以下是一个使用递归的深度优先遍历的示例代码:
```
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 深度优先遍历函数,使用递归实现
void dfs(TreeNode* root) {
if (root == nullptr) {
return;
}
// 访问当前节点
cout << root->val << " ";
// 遍历左子树
dfs(root->left);
// 遍历右子树
dfs(root->right);
}
// 根据数组构造二叉树
TreeNode* buildTree(vector<int>& nums, int start, int end) {
if (start > end) {
return nullptr;
}
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildTree(nums, start, mid - 1);
root->right = buildTree(nums, mid + 1, end);
return root;
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
TreeNode* root = buildTree(nums, 0, nums.size() - 1);
dfs(root); // 输出:1 2 4 5 3 6 7
return 0;
}
```
上述代码中,首先定义了一个二叉树节点的结构体 `TreeNode`,然后定义了一个深度优先遍历的函数 `dfs`,使用递归的方式实现。在 `dfs` 函数中,如果当前节点为空,则直接返回;否则,先访问当前节点,然后递归遍历左子树和右子树。
在 `main` 函数中,首先构造了一个有序数组 `nums`,然后根据数组构造了一棵二叉树。最后调用 `dfs` 函数对二叉树进行深度优先遍历,输出遍历结果。
以上是一个简单的头歌数据结构深度优先遍历的示例代码。
阅读全文