如何用非递归算法实现二叉树的先序遍历?
时间: 2024-06-16 11:07:18 浏览: 20
非递归算法实现二叉树的先序遍历可以使用栈来辅助实现。具体步骤如下:
1. 创建一个空栈,并将根节点入栈。
2. 循环执行以下步骤,直到栈为空:
- 弹出栈顶节点,并访问该节点。
- 如果该节点的右子节点不为空,则将右子节点入栈。
- 如果该节点的左子节点不为空,则将左子节点入栈。
下面是一个示例代码实现:
```python
def preorderTraversal(root):
if not root:
return []
stack = []
result = []
stack.append(root)
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
```
相关问题
用非递归算法写二叉树的先序遍历
非递归算法写二叉树的先序遍历需要借助栈来实现。具体步骤如下:
1. 建立一个栈,并将根节点压入栈中。
2. 当栈不为空时,执行以下操作:
- 弹出栈顶元素,将其值加入结果列表中。
- 如果该节点存在右子树,则将其右子节点压入栈中。
- 如果该节点存在左子树,则将其左子节点压入栈中。
3. 当所有节点都被遍历完后,返回结果列表。
下面是 Python 代码实现:
```python
def preorderTraversal(root):
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
其中,root 表示二叉树的根节点,val 表示该节点的值。
建立二叉树,并实现二叉树的遍历,先序遍历采用递归算法实现,层次遍历用非递归算法来实现
好的,我来解答你的问题。
首先,建立二叉树需要定义一个二叉树的节点,包含左右子节点和节点值。我们可以按照下面的方式定义节点类:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
```
接下来,我们可以用递归的方式实现二叉树的先序遍历。先序遍历的顺序是先遍历根节点,然后遍历左子树,最后遍历右子树。实现代码如下:
```python
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
```
最后,我们可以用非递归的方式实现二叉树的层次遍历。层次遍历的顺序是按照树的层次从上到下,从左到右遍历所有节点。我们可以用队列来实现非递归遍历。实现代码如下:
```python
def levelOrderTraversal(root):
if not root:
return []
res = []
queue = [root]
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
```
这样,我们就完成了建立二叉树,以及实现二叉树的遍历。希望对你有所帮助!