编写先序遍历算法
时间: 2023-07-26 13:06:02 浏览: 51
先序遍历是二叉树遍历的一种方式,遍历顺序为:根节点 -> 左子树 -> 右子树。以下是先序遍历的算法实现:
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` 实现了先序遍历,它首先输出当前节点的值,然后递归遍历左子树和右子树。如果当前节点为空,则函数直接返回。
相关问题
编写算法先序遍历二叉树
先序遍历二叉树的算法如下:
1. 如果二叉树为空,则返回。
2. 访问根节点。
3. 递归遍历左子树。
4. 递归遍历右子树。
以下是使用 Python 实现的代码:
```python
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def preorder_traversal(root):
if root:
print(root.data)
preorder_traversal(root.left)
preorder_traversal(root.right)
```
其中,Node 类表示二叉树的节点,包含左右子节点和数据。preorder_traversal 函数接收二叉树的根节点作为参数,按照先序遍历的顺序遍历整棵树,并打印出每个节点的数据。
用c++编写一段用先序遍历算法建立一个二叉树的完整代码
好的,下面是用 C++ 编写的完整代码,可以用先序遍历算法建立一个二叉树:
```cpp
#include<iostream>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v): val(v), left(NULL), right(NULL) {}
};
TreeNode* buildTree(){
int val;
cin >> val;
if(val == -1) // 空节点
return NULL;
TreeNode* root = new TreeNode(val);
root->left = buildTree();
root->right = buildTree();
return root;
}
int main(){
cout << "请输入二叉树的先序遍历序列(空节点用-1表示):" << endl;
TreeNode* root = buildTree();
return 0;
}
```
这个程序可以接受用户输入二叉树的先序遍历序列,其中空节点用 -1 表示,然后用先序遍历算法建立二叉树,并返回根节点指针。