编写链表遍历的递归算法。
时间: 2023-04-06 20:01:40 浏览: 56
可以的,链表遍历的递归算法如下:
void traverse(Node* head) {
if (head == NULL) {
return;
}
printf("%d ", head->val);
traverse(head->next);
}
其中,Node 是链表节点的结构体,包含一个整数 val 和一个指向下一个节点的指针 next。递归函数 traverse 接收一个指向链表头节点的指针 head,如果 head 为空指针,则直接返回;否则,先输出当前节点的值,再递归遍历下一个节点。
相关问题
二叉树层次遍历递归算法
二叉链表存储结构是一种常用的二叉树存储方式,可以用来实现二叉树的层次遍历、先序遍历和中序遍历的非递归算法。
二叉树的层次遍历可以使用队列来实现。从根节点开始,将其入队,然后依次出队,并将其左右子节点入队,直到队列为空。这样就可以按照层次遍历的顺序输出二叉树的所有节点。
先序遍历的非递归算法可以使用栈来实现。从根节点开始,将其入栈,然后依次出栈,并将其右子节点和左子节点入栈,直到栈为空。这样就可以按照先序遍历的顺序输出二叉树的所有节点。
中序遍历的非递归算法也可以使用栈来实现。从根节点开始,将其入栈,然后将其左子节点入栈,直到左子节点为空。然后依次出栈,并将其右子节点入栈,直到栈为空。这样就可以按照中序遍历的顺序输出二叉树的所有节点。
编写先序遍历算法
先序遍历是二叉树遍历的一种方式,遍历顺序为:根节点 -> 左子树 -> 右子树。以下是先序遍历的算法实现:
1. 如果当前节点为空,则返回。
2. 对于当前节点,先输出当前节点的值。
3. 递归遍历当前节点的左子树。
4. 递归遍历当前节点的右子树。
以下是先序遍历的算法实现示例(假设二叉树使用链表存储):
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_traversal(root: TreeNode):
if not root:
return
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
```
代码中的 `TreeNode` 类定义了二叉树的节点结构。函数 `preorder_traversal` 实现了先序遍历,它首先输出当前节点的值,然后递归遍历左子树和右子树。如果当前节点为空,则函数直接返回。