编程实现“二叉树”的创建、先序遍历、中序遍历和后序遍历。
时间: 2023-08-04 14:05:27 浏览: 51
好的,下面是实现二叉树的 Python 代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
index = inorder.index(preorder[0])
root.left = buildTree(preorder[1:index+1], inorder[:index])
root.right = buildTree(preorder[index+1:], inorder[index+1:])
return root
def preorderTraversal(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
def inorderTraversal(root):
if not root:
return []
result = []
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
result.append(root.val)
root = root.right
return result
def postorderTraversal(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
```
`buildTree` 函数可以根据先序遍历和中序遍历构建二叉树,返回根节点;`preorderTraversal` 函数实现先序遍历,`inorderTraversal` 函数实现中序遍历,`postorderTraversal` 函数实现后序遍历。
例如,如果要创建一棵二叉树,先序遍历为 `[3, 9, 20, 15, 7]`,中序遍历为 `[9, 3, 15, 20, 7]`,可以这样调用:
```python
root = buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
```
然后可以分别调用 `preorderTraversal`、`inorderTraversal` 和 `postorderTraversal` 函数,得到对应的遍历结果:
```python
print(preorderTraversal(root)) # [3, 9, 20, 15, 7]
print(inorderTraversal(root)) # [9, 3, 15, 20, 7]
print(postorderTraversal(root)) # [9, 15, 7, 20, 3]
```