用递归、非递归两种方法遍历二叉树的源代码
时间: 2023-11-28 18:49:01 浏览: 36
递归遍历二叉树的代码:
```python
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder(node: Node):
if node is None:
return
inorder(node.left)
print(node.val)
inorder(node.right)
def preorder(node: Node):
if node is None:
return
print(node.val)
preorder(node.left)
preorder(node.right)
def postorder(node: Node):
if node is None:
return
postorder(node.left)
postorder(node.right)
print(node.val)
```
非递归遍历二叉树的代码:
```python
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder(node: Node):
stack = []
while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
print(node.val)
node = node.right
def preorder(node: Node):
stack = [node]
while stack:
node = stack.pop()
if node:
print(node.val)
stack.append(node.right)
stack.append(node.left)
def postorder(node: Node):
stack1 = [node]
stack2 = []
while stack1:
node = stack1.pop()
if node:
stack2.append(node)
stack1.append(node.left)
stack1.append(node.right)
while stack2:
node = stack2.pop()
print(node.val)
```
这里给出了中序、前序、后序三种遍历方式的代码,分别用递归和非递归的方式实现。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)