实现二叉树A(B(D,E(H(J,K(L,M(N)))),C(F,G(,I)))的先序遍历、中序遍历和后序遍历的递归和非递归算法
时间: 2024-02-05 16:04:52 浏览: 27
先给出二叉树A(B(D,E(H(J,K(L,M(N)))),C(F,G(,I)))的结构图:
```
A
/ \
B C
/ \ / \
D E F G
/ / \
H I null
/ \
J K
/ \
L M
/
N
```
1. 先序遍历
递归算法:
```python
def preorder_recursive(root):
if not root:
return
print(root.val, end=' ')
preorder_recursive(root.left)
preorder_recursive(root.right)
```
非递归算法:
```python
def preorder_iterative(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val, end=' ')
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
```
2. 中序遍历
递归算法:
```python
def inorder_recursive(root):
if not root:
return
inorder_recursive(root.left)
print(root.val, end=' ')
inorder_recursive(root.right)
```
非递归算法:
```python
def inorder_iterative(root):
if not root:
return
stack = []
node = root
while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
print(node.val, end=' ')
node = node.right
```
3. 后序遍历
递归算法:
```python
def postorder_recursive(root):
if not root:
return
postorder_recursive(root.left)
postorder_recursive(root.right)
print(root.val, end=' ')
```
非递归算法:
```python
def postorder_iterative(root):
if not root:
return
stack1, stack2 = [root], []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
node = stack2.pop()
print(node.val, end=' ')
```
其中,后序遍历的非递归算法需要用到两个栈,第一个栈用来存储结点,第二个栈用来按照后序遍历的顺序输出结点。具体实现是先将根结点压入第一个栈,然后循环执行以下操作:从第一个栈中弹出当前结点,将其压入第二个栈中,再依次将当前结点的左右子结点压入第一个栈中。当第一个栈为空时,说明所有结点都已经遍历完毕,此时只需要依次弹出第二个栈中的结点即可得到后序遍历的结果。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)