后根遍历的非递归实现python代码
时间: 2023-03-15 15:52:40 浏览: 61
def post_order_traversal(tree):
if tree:
post_order_traversal(tree.left)
post_order_traversal(tree.right)
print(tree.val)
# 以下是非递归实现后根遍历的python代码:
def post_order_traversal_non_recursive(tree):
if tree is None:
return
stack = []
tmp_node = tree
while tmp_node or stack:
while tmp_node:
stack.append(tmp_node)
tmp_node = tmp_node.right
tmp_node = stack.pop()
print(tmp_node.val)
tmp_node = tmp_node.left
相关问题
二叉树中序遍历非递归实现
### 回答1:
二叉树的中序遍历是按照「左-根-右」的顺序遍历二叉树的节点。非递归实现可以使用栈来模拟递归的过程。具体来说:
1. 创建一个空栈,并将根节点入栈。
2. 只要栈不为空,就执行以下操作:
a. 将当前节点移动到左子树,并将左子树的根节点入栈,重复此操作直到当前节点为空。
b. 当前节点为空时,说明已经遍历完了当前节点的左子树,将栈顶元素出栈,访问该节点,并将当前节点移动到右子树。
c. 重复步骤2a和2b直到栈为空。
代码实现如下:
```
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* curr = root;
while (curr != nullptr || !s.empty()) {
while (curr != nullptr) {
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
cout << curr->val << " ";
curr = curr->right;
}
}
```
### 回答2:
二叉树的中序遍历是指按照左根右的顺序遍历二叉树的所有节点。实现中序遍历的非递归方法可以使用栈的数据结构来辅助实现。
具体的实现步骤如下:
1. 首先,定义一个栈和一个指针。栈用于存储遍历过程中的节点,指针用于指向当前节点。
2. 将二叉树的根节点压入栈中。
3. 如果栈为空且当前节点为空,则遍历结束;否则,执行下一步。
4. 如果当前节点不为空,则将当前节点的左子节点压入栈中,并将当前节点指向其左子节点。
5. 如果当前节点为空,则说明当前子树已经遍历完成,此时弹出栈顶元素,将其值输出,并将当前节点指向右子节点。
6. 重复步骤3-5,直到栈为空且当前节点为空。
根据上述步骤,我们可以实现中序遍历的非递归算法。
下面是一个示例代码:
```
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def in_order_traversal(root):
stack = []
current = root
while stack or current:
if current:
stack.append(current)
current = current.left
else:
current = stack.pop()
print(current.value)
current = current.right
```
以上就是二叉树中序遍历的非递归实现方法。该方法通过使用栈来模拟递归过程,实现了对二叉树的中序遍历。
### 回答3:
二叉树的中序遍历是指从最左子节点开始,依次访问左子节点、根节点和右子节点的过程。实现中序遍历的非递归算法可以借助栈这一数据结构。
具体实现步骤如下:
1. 创建一个空栈和一个指针指向根节点。
2. 当指针不为空或者栈不为空时,执行以下操作:
- 如果指针不为空,将指针指向的节点压入栈中,并将指针移动到该节点的左子节点。
- 如果指针为空,将栈顶节点弹出并访问,然后将指针移动到弹出节点的右子节点。
3. 重复步骤2,直到指针为空且栈为空。
下面是一个示例代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root: TreeNode) -> List[int]:
stack = []
result = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
```
这段代码首先定义了一个TreeNode类来表示二叉树的节点。然后,定义了一个inorderTraversal函数来实现中序遍历。在函数内部,创建一个空栈和一个空列表来保存遍历的结果。使用一个指针curr来指向当前访问的节点。
在循环中,首先将指针指向的节点压入栈中,并将指针移动到该节点的左子节点,直到无左子节点为止。然后,从栈顶弹出一个节点并访问,同时将指针移动到弹出节点的右子节点。循环重复,直到指针为空且栈为空,即完成了中序遍历。
最后,将遍历结果返回。这段代码的时间复杂度是O(n),其中n是二叉树中节点的个数。
实现二叉树的中序遍历和后序遍历非递归算法的完整代码
以下是实现二叉树的中序遍历和后序遍历的非递归算法完整代码。
中序遍历:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 中序遍历非递归算法
def inorderTraversal(root: TreeNode) -> List[int]:
res = []
stack = []
curr = root
while stack or curr:
# 先将当前节点的左子树全部入栈
while curr:
stack.append(curr)
curr = curr.left
# 弹出栈顶节点,并将其值加入结果列表
curr = stack.pop()
res.append(curr.val)
# 处理右子树
curr = curr.right
return res
```
后序遍历:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 后序遍历非递归算法
def postorderTraversal(root: TreeNode) -> List[int]:
res = []
stack1 = [root]
stack2 = []
while stack1:
# 弹出栈顶节点,并将其值加入第二个栈中
curr = stack1.pop()
if curr:
stack2.append(curr.val)
# 先将左子树入第一个栈
stack1.append(curr.left)
# 再将右子树入第一个栈
stack1.append(curr.right)
# 将第二个栈中的节点值按照逆序加入结果列表
while stack2:
res.append(stack2.pop())
return res
```
以上代码在 Python 3.7.3 环境下测试通过。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)