写一段代码实现二叉树的建立并实现先序遍历,中序遍历和后序遍历
时间: 2024-05-12 21:14:37 浏览: 10
二叉树的建立可以使用递归方式实现,具体代码如下:
```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_val = preorder[0]
root_index = inorder.index(root_val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index+1:]
left_preorder = preorder[1:len(left_inorder)+1]
right_preorder = preorder[len(left_inorder)+1:]
root = TreeNode(root_val)
root.left = buildTree(left_preorder, left_inorder)
root.right = buildTree(right_preorder, right_inorder)
return root
```
其中,`preorder` 表示先序遍历序列,`inorder` 表示中序遍历序列。递归过程中,首先取出先序遍历序列的第一个节点作为根节点,然后在中序遍历序列中找到根节点的位置,将中序遍历序列分成左子树和右子树两部分,同时也需要将先序遍历序列中对应的左子树和右子树提取出来,递归处理左子树和右子树,最终返回根节点。
接下来是三种遍历方式的代码实现:
```python
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
def inorderTraversal(root):
if not root:
return []
res = inorderTraversal(root.left)
res += [root.val]
res += inorderTraversal(root.right)
return res
def postorderTraversal(root):
if not root:
return []
res = postorderTraversal(root.left)
res += postorderTraversal(root.right)
res += [root.val]
return res
```
其中,先序遍历的顺序是根节点、左子树、右子树;中序遍历的顺序是左子树、根节点、右子树;后序遍历的顺序是左子树、右子树、根节点。以上三个函数返回的都是一个列表,包含了按照对应顺序遍历后的节点值。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)