在下一步我要进行递归遍历,最终剩下的是未遍历的元素,即孤立点或非目标边缘
时间: 2024-02-26 21:53:06 浏览: 27
好的,那么在递归遍历过程中,`traverse` 函数会对输入的 `TLedge0`(目标边缘点的位置)和 `isvis`(标志位数组)进行修改,以记录目标边缘点是否被遍历过,最终返回剩余的未遍历的目标边缘点的位置和标志位数组。这些未遍历的目标边缘点就是孤立点或非目标边缘。`traverse` 函数的输入参数包括 `TLedge0`、`x`、`y` 和 `isvis`,分别表示目标边缘点的位置、当前待遍历点的坐标和标志位数组。输出参数包括修改后的 `TLedge0` 和 `isvis`,记录了遍历的结果。
相关问题
二叉树递归遍历和非递归遍历的时空复杂度
二叉树的递归遍历和非递归遍历的时空复杂度如下所示:
1. 递归遍历的时空复杂度:
- 时间复杂度:对于含有n个节点的二叉树,递归遍历的时间复杂度为O(n),因为每个节点都需要被访问一次。
- 空间复杂度:递归遍历的空间复杂度取决于递归调用的深度,即树的高度。在最坏情况下,二叉树的高度为n,所以递归遍历的空间复杂度为O(n)。
2. 非递归遍历的时空复杂度:
- 时间复杂度:对于含有n个节点的二叉树,非递归遍历的时间复杂度也为O(n),因为每个节点都需要被访问一次。
- 空间复杂度:非递归遍历使用了辅助数据结构栈来存储节点,所需的空间取决于栈的最大容量,即树的深度。在最坏情况下,二叉树的深度为n,所以非递归遍历的空间复杂度为O(n)。
二叉树的递归遍历和非递归遍历c语言代码
二叉树的遍历有三种方式:前序遍历、中序遍历和后序遍历。其中,递归遍历是比较常见的方式,而非递归遍历则需要借助栈的数据结构实现。
下面给出二叉树的递归遍历和非递归遍历的C语言代码实现:
1. 二叉树的递归遍历
前序遍历:
```
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); // 访问根节点
}
```
2. 二叉树的非递归遍历
前序遍历:
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
printf("%d ", node->val); // 访问节点
if (node->right != NULL) {
st.push(node->right); // 右子节点先入栈,保证左子节点先出栈
}
if (node->left != NULL) {
st.push(node->left);
}
}
}
```
中序遍历:
```
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
while (!st.empty() || node != NULL) {
if (node != NULL) { // 当前节点不为空,继续将其左子节点入栈
st.push(node);
node = node->left;
} else { // 当前节点为空,说明已经到达最左侧,开始出栈访问节点
node = st.top();
st.pop();
printf("%d ", node->val); // 访问节点
node = node->right; // 开始访问右子节点
}
}
}
```
后序遍历:
```
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> st1, st2;
st1.push(root);
while (!st1.empty()) {
TreeNode* node = st1.top();
st1.pop();
st2.push(node); // 先将当前节点入栈st2
if (node->left != NULL) {
st1.push(node->left); // 左子节点入栈st1
}
if (node->right != NULL) {
st1.push(node->right); // 右子节点入栈st1
}
}
while (!st2.empty()) { // 出栈访问节点
TreeNode* node = st2.top();
st2.pop();
printf("%d ", node->val);
}
}
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)