建立二叉树,并实现二叉树的遍历,先序遍历采用递归算法实现,层次遍历用非递归算法来实现
时间: 2024-03-10 08:43:32 浏览: 83
好的,我来解答你的问题。
首先,建立二叉树需要定义一个二叉树的节点,包含左右子节点和节点值。我们可以按照下面的方式定义节点类:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
```
接下来,我们可以用递归的方式实现二叉树的先序遍历。先序遍历的顺序是先遍历根节点,然后遍历左子树,最后遍历右子树。实现代码如下:
```python
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
```
最后,我们可以用非递归的方式实现二叉树的层次遍历。层次遍历的顺序是按照树的层次从上到下,从左到右遍历所有节点。我们可以用队列来实现非递归遍历。实现代码如下:
```python
def levelOrderTraversal(root):
if not root:
return []
res = []
queue = [root]
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
```
这样,我们就完成了建立二叉树,以及实现二叉树的遍历。希望对你有所帮助!
阅读全文
相关推荐
















