实现二叉树先序遍历的递归算法
时间: 2023-11-14 18:29:33 浏览: 37
二叉树先序遍历的递归算法如下:
1. 先访问根节点
2. 遍历左子树
3. 遍历右子树
具体实现如下:
代码如下:
void preorder_traversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " "; // 访问根节点
preorder_traversal(root->left); // 遍历左子树
preorder_traversal(root->right); // 遍历右子树
}
相关问题
二叉树先序遍历递归算法
二叉树先序遍历的递归算法如下:
1. 如果二叉树为空,则返回。
2. 访问根节点。
3. 对根节点的左子树进行先序遍历。
4. 对根节点的右子树进行先序遍历。
代码实现如下(假设二叉树的节点类型为Node):
```python
def preorder_traversal(root):
if root:
print(root.val) # 访问根节点
preorder_traversal(root.left) # 先序遍历左子树
preorder_traversal(root.right) # 先序遍历右子树
```
在上述代码中,我们首先判断了二叉树是否为空,如果不为空则依次执行访问根节点、先序遍历左子树、先序遍历右子树的操作。这样递归进行下去,直到遍历完整个二叉树。
实现先序线索二叉树上的先序遍历 递归算法
实现先序线索二叉树的先序遍历递归算法可以按照以下步骤:
1. 如果当前结点的左孩子不为 NULL,递归遍历当前结点的左孩子。
2. 访问当前结点。
3. 如果当前结点的右孩子不为 NULL,递归遍历当前结点的右孩子。
需要注意的是,由于是线索二叉树,遍历时需要判断当前结点是否有左线索或右线索,如果有的话,需要按照线索指向的结点进行遍历。
此处给出一个示例代码:
```c++
void preOrderThreadedTree(TreeNode *root) {
TreeNode *p = root;
while (p) {
if (p->leftChildThread == false) {
p = p->leftChild;
} else {
visit(p);
if (p->rightChildThread == false) p = p->rightChild;
else {
// 找到该结点的后继结点
while (p && p->rightChildThread) {
p = p->rightChild;
visit(p);
}
p = p->rightChild;
}
}
}
}
```
其中,TreeNode 表示线索二叉树的结点,leftChild 和 rightChild 分别表示左孩子和右孩子,leftChildThread 和 rightChildThread 分别表示左线索和右线索。visit函数用于访问结点(即输出结点的值)。