python树栈
时间: 2023-06-21 20:20:27 浏览: 55
树和栈都是非常常见的数据结构,Python也提供了相应的实现方法。下面是一些Python树和栈的示例代码:
1. 树的实现示例代码:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
2. 栈的实现示例代码:
```
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
def is_empty(self):
return len(self.stack) == 0
def peek(self):
if not self.is_empty():
return self.stack[-1]
def size(self):
return len(self.stack)
```
希望这些示例代码能够对你有所帮助!
相关问题
python用栈深度优先搜索
在Python中,可以使用栈来实现深度优先搜索(DFS)。深度优先搜索是一种用于遍历或搜索图或树的算法,它从起始节点开始,沿着一条路径尽可能深入地探索,直到无法继续为止,然后回溯到前一个节点,继续探索其他路径。
下面是一个使用栈实现深度优先搜索的示例代码:
```python
def dfs(graph, start):
visited = set() # 用于记录已访问的节点
stack = [start] # 使用栈来保存待访问的节点
while stack:
node = stack.pop() # 弹出栈顶节点
if node not in visited:
print(node) # 访问节点
visited.add(node)
neighbors = graph[node] # 获取当前节点的邻居节点
stack.extend(neighbors) # 将邻居节点加入栈中
# 示例图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
dfs(graph, 'A')
```
上述代码中,我们使用一个集合`visited`来记录已经访问过的节点,使用一个栈`stack`来保存待访问的节点。首先将起始节点加入栈中,然后进入循环,每次从栈中弹出一个节点,如果该节点未被访问过,则进行访问,并将其标记为已访问。然后将该节点的邻居节点加入栈中,继续下一轮循环。直到栈为空时,搜索结束。
树的遍历python
树的遍历有三种方式:前序遍历、中序遍历和后序遍历。下面是它们的python实现:
```python
# 定义一个二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 前序遍历:根节点 -> 左子树 -> 右子树
def preorderTraversal(root: TreeNode):
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
# 中序遍历:左子树 -> 根节点 -> 右子树
def inorderTraversal(root: TreeNode):
if not root:
return []
res = []
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
node = stack.pop()
res.append(node.val)
root = node.right
return res
# 后序遍历:左子树 -> 右子树 -> 根节点
def postorderTraversal(root: TreeNode):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
```
其中,前序遍历和中序遍历使用了栈的方式进行遍历,而后序遍历则是先遍历左子树和右子树,最后将结果逆序输出。