已知一棵树的节点关系,编程实现树的先根遍历
时间: 2024-03-17 09:40:25 浏览: 33
您好!树的先根遍历可以使用递归或者迭代的方式实现,下面是递归实现的示例代码:
```python
def pre_order(root):
if root is None:
return
print(root.val) # 先访问根节点
for child in root.children: # 遍历子节点
pre_order(child) # 对每个子节点进行先根遍历
```
其中,root表示树的根节点,children表示该节点的子节点列表。先访问根节点,然后对每个子节点进行先根遍历。
如果您需要迭代实现,则可以使用栈来辅助实现。具体实现方法请参考下面的示例代码:
```python
def pre_order(root):
if root is None:
return
stack = [root]
while stack:
node = stack.pop() # 弹出栈顶节点
print(node.val) # 访问节点
for child in node.children[::-1]: # 将子节点逆序入栈
stack.append(child)
```
在迭代实现中,我们使用栈来存储待访问的节点。首先将根节点入栈,然后不断弹出栈顶节点,访问该节点,并将其子节点逆序入栈。这样可以保证先访问左子树,再访问右子树。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![dll](https://img-home.csdnimg.cn/images/20210720083646.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)