2)编写中序遍历函数; 3)编写后序遍历函数; 4)编写先序遍历函数; 5)编写create函数,按照先序遍历方法根据输入的字母序列建立二叉树; 6)编写二叉排序树的创建函数(可用递归方法); 7)编写main( )函数,分别创建5)6)两种二叉树;然后分别调用中序、后序、先序遍历函数进行遍历。
时间: 2024-03-17 11:40:03 浏览: 18
2)中序遍历函数的实现如下:
```python
def inorderTraversal(root):
if not root:
return []
res = []
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
res.append(root.val)
root = root.right
return res
```
3)后序遍历函数的实现如下:
```python
def postorderTraversal(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.left)
stack.append(node.right)
return res[::-1]
```
4)先序遍历函数的实现如下:
```python
def preorderTraversal(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.right)
stack.append(node.left)
return res
```
5)按照先序遍历方法根据输入的字母序列建立二叉树的实现如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def create(preorder):
if not preorder:
return None
root_val = preorder.pop(0)
root = TreeNode(root_val)
root.left = create(preorder)
root.right = create(preorder)
return root
```
6)二叉排序树的创建函数的实现如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
```
7)main()函数的实现如下:
```python
if __name__ == '__main__':
# 先序遍历序列创建二叉树
preorder = [1, 2, 4, None, None, 5, None, None, 3, 6, None, None, 7, None, None]
root1 = create(preorder)
print("先序遍历结果:", preorderTraversal(root1))
print("中序遍历结果:", inorderTraversal(root1))
print("后序遍历结果:", postorderTraversal(root1))
# 二叉排序树的创建
root2 = None
vals = [5, 3, 8, 4, 6, 9, 2, 1, 7]
for val in vals:
root2 = insert(root2, val)
print("中序遍历结果:", inorderTraversal(root2))
print("后序遍历结果:", postorderTraversal(root2))
print("先序遍历结果:", preorderTraversal(root2))
```
这样,我们就完成了二叉树的创建和遍历。