写出使用十字链表结构 实现深度优先遍历的代码
时间: 2023-02-11 21:20:34 浏览: 72
下面是一个使用十字链表结构实现深度优先遍历的代码示例:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def dfs(node):
if node is None:
return
print(node.data)
dfs(node.left)
dfs(node.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
dfs(root)
```
代码中定义了一个 Node 类,表示树上的节点。每个节点有一个数据域和左右指针。 dfs 函数实现了深度优先遍历,递归地遍历左右子树。在 main 函数中,通过构建一颗树并调用 dfs 函数来遍历树的每个节点。
相关问题
写出使用十字链表结构实现深度优先遍历的c++代码
```c
void DFS(Node* root) {
Node* p = root;
printf("%d ", p->data);
if (p->firstChild != NULL) {
DFS(p->firstChild);
}
if (p->nextSibling != NULL) {
DFS(p->nextSibling);
}
}
```
其中,Node 结构体中包含三个指针:
- `int data`:节点的数据值
- `Node* firstChild`:指向第一个子节点的指针
- `Node* nextSibling`:指向下一个兄弟节点的指针
代码中,递归函数 DFS() 接受一个 Node 指针作为参数,输出该节点的数据,然后分别访问它的第一个子节点和下一个兄弟节点。
在外部调用时,传入根节点即可:
```c
int main() {
DFS(root);
return 0;
}
```
这个代码是深度优先遍历,那么如果是宽度优先遍历,那就需要使用队列进行实现.
```c
void BFS(Node* root) {
queue<Node*> q;
Node* p = root;
printf("%d ", p->data);
q.push(p);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
p = temp->firstChild;
while (p != NULL) {
printf("%d ", p->data);
q.push(p);
p = p->nextSibling;
}
}
}
```
邻接链表的深度优先遍历唯一吗
邻接链表的深度优先遍历并不唯一。深度优先遍历是一种图遍历算法,其过程中会按照某种规则访问图中的节点,其中邻接链表是一种常用的存储图结构的方式。在深度优先遍历邻接链表时,可以采用递归或者栈的方式实现。不同的实现方式可能会导致遍历的顺序不同,但是只要保证每个节点都能被访问到且不重复,就可以达到深度优先遍历的目的。