建立二叉树,并实现二叉树的遍历,先序遍历采用递归算法实现,层次遍历用非递归算法来实现
时间: 2024-03-10 07:44:19 浏览: 38
好的,下面是代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def build_tree(self, vals):
def dfs(i):
if i >= len(vals) or vals[i] is None:
return None
node = TreeNode(vals[i])
node.left = dfs(2 * i + 1)
node.right = dfs(2 * i + 2)
return node
self.root = dfs(0)
def preorder_traversal(self):
def dfs(node):
if not node:
return
print(node.val, end=' ')
dfs(node.left)
dfs(node.right)
dfs(self.root)
print()
def level_traversal(self):
if not self.root:
return
queue = [self.root]
while queue:
node = queue.pop(0)
print(node.val, end=' ')
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
print()
```
其中,`TreeNode` 表示二叉树的节点,`BinaryTree` 表示二叉树。`build_tree` 方法根据输入的列表构建二叉树,`preorder_traversal` 方法实现了先序遍历(递归实现),`level_traversal` 方法实现了层次遍历(非递归实现)。
示例:
```python
tree = BinaryTree()
tree.build_tree([1, 2, 3, 4, 5, None, 7])
tree.preorder_traversal() # 1 2 4 5 3 7
tree.level_traversal() # 1 2 3 4 5 7
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](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)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)