采用二叉链表存储结构,完成二叉树的层次遍历,先序遍历的非递归算法和中序遍历的非递归算法的代码
时间: 2023-12-03 16:05:03 浏览: 118
二叉树先序遍历的非递归算法具体实现
5星 · 资源好评率100%
二叉树的层次遍历可以使用队列来实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def levelOrder(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
```
先序遍历的非递归算法可以使用栈来实现:
```python
def preorderTraversal(root):
if not root:
return []
res = []
stack = [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
```
中序遍历的非递归算法也可以使用栈来实现:
```python
def inorderTraversal(root):
if not root:
return []
res = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
```
以上是 Python 的代码示例,使用其他语言实现也可以根据相应语言的特性进行相应的调整。
阅读全文