实现建立二叉树先序遍历中序遍历后序遍历用栈实现中序遍历输出叶子结点、个数输出结点、个数树深度退出的完整代码
时间: 2024-12-23 13:18:14 浏览: 0
二叉树遍历
在使用栈来实现二叉树的先序(Preorder)、中序(Inorder)、后序(Postorder)遍历以及特定需求如输出叶子节点、计算节点总数和树的深度时,首先我们需要创建一个二叉树节点结构,并设置相关的递归或迭代方法。这里是一个基本的Python示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 先序遍历 (根-左-右)
def preorder_traversal(root):
if root is not None:
print(root.val, end=" ") # 打印节点值
preorder_traversal(root.left) # 左子树
preorder_traversal(root.right) # 右子树
# 中序遍历 (左-根-右)
def inorder_traversal(root):
stack = []
current = root
while True:
while current is not None:
stack.append(current)
current = current.left
if not stack:
break
node = stack.pop()
print(node.val, end=" ")
current = node.right
# 输出所有叶子节点 (辅助函数)
def get_leaf_nodes(root):
leaves = []
if root is not None and root.left is None and root.right is None:
leaves.append(root.val)
return leaves
# 计算节点总数
def count_nodes(root):
if root is None:
return 0
else:
return 1 + count_nodes(root.left) + count_nodes(root.right)
# 计算树的深度
def depth_of_tree(root):
if root is None:
return 0
else:
left_depth = depth_of_tree(root.left)
right_depth = depth_of_tree(root.right)
return max(left_depth, right_depth) + 1
# 示例用法
# 创建二叉树...
# ...
root = ... # 初始化你的二叉树根节点
print("前序遍历: ", end="")
preorder_traversal(root)
print("\n中序遍历: ", end="")
inorder_traversal(root)
leaf_nodes = get_leaf_nodes(root)
print(f"叶节点: {leaf_nodes}")
print(f"叶节点数量: {len(leaf_nodes)}")
node_count = count_nodes(root)
print(f"节点总数: {node_count}")
tree_depth = depth_of_tree(root)
print(f"树的深度: {tree_depth}\n")
```
请注意,你需要根据实际需要调整这些函数,并提供二叉树的实例化代码。上述代码假设了二叉树的节点结构和一些基本操作已经定义好。如果你还没有定义这些,那么你需要首先定义`TreeNode`类。
阅读全文