本关任务:假设二叉树中结点的值均为一个单字符,编写程序,实现以下功能: 1、按先序遍历的顺序建立二叉链表; 2、使用递归算法对二叉树进行中序遍历。
时间: 2024-05-13 10:15:43 浏览: 145
编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法
5星 · 资源好评率100%
好的,我可以帮你完成这个任务。以下是Python代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder):
if not preorder:
return None
root_val = preorder.pop(0)
if not root_val:
return None
root = TreeNode(root_val)
root.left = buildTree(preorder)
root.right = buildTree(preorder)
return root
def inorderTraversal(root):
if not root:
return
inorderTraversal(root.left)
print(root.val, end=" ")
inorderTraversal(root.right)
```
其中,`TreeNode`类表示二叉树的结点,`buildTree`函数用于按先序遍历的顺序建立二叉链表,`inorderTraversal`函数使用递归算法对二叉树进行中序遍历。
你可以使用以下代码测试这个程序:
```python
preorder = ['A', 'B', None, None, 'C', 'D', None, None, 'E', None, 'F', None, None]
root = buildTree(preorder)
inorderTraversal(root)
```
输出应该为:B A D C F E
阅读全文