创建二叉树,分别以先序遍历、中序遍历、后序遍历访问二叉树,并输出二叉树的叶子结点
时间: 2023-07-10 21:06:27 浏览: 95
对所建立的二叉树分别进行先序、中序和后序遍历,并输出结果。
4星 · 用户满意度95%
好的,我可以为您提供一个Python实现的例子。如下:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root = Node(preorder[0])
idx = inorder.index(root.val)
root.left = buildTree(preorder[1:idx+1], inorder[:idx])
root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
return root
def preorderTraversal(root):
if not root:
return
print(root.val, end=' ')
preorderTraversal(root.left)
preorderTraversal(root.right)
def inorderTraversal(root):
if not root:
return
inorderTraversal(root.left)
print(root.val, end=' ')
inorderTraversal(root.right)
def postorderTraversal(root):
if not root:
return
postorderTraversal(root.left)
postorderTraversal(root.right)
print(root.val, end=' ')
def getLeafNodes(root):
if not root:
return []
elif not root.left and not root.right:
return [root.val]
else:
return getLeafNodes(root.left) + getLeafNodes(root.right)
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
print('先序遍历:', end='')
preorderTraversal(root)
print()
print('中序遍历:', end='')
inorderTraversal(root)
print()
print('后序遍历:', end='')
postorderTraversal(root)
print()
print('叶子节点:', getLeafNodes(root))
```
其中,我们定义了一个 `Node` 类作为二叉树的节点,包含节点值、左子节点和右子节点。`buildTree` 函数根据先序遍历和中序遍历结果构建二叉树。`preorderTraversal`、`inorderTraversal` 和 `postorderTraversal` 分别表示先序遍历、中序遍历和后序遍历,通过递归实现。`getLeafNodes` 函数用于返回二叉树的叶子节点值。
你可以运行代码,看一下输出结果。
阅读全文