二叉树的构造以及四种遍历算法实现代码
时间: 2023-08-31 13:19:09 浏览: 51
### 回答1:
二叉树的构造代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
idx = inorder.index(root_val)
root.left = build_tree(preorder[1:idx+1], inorder[:idx])
root.right = build_tree(preorder[idx+1:], inorder[idx+1:])
return root
```
四种遍历算法实现代码:
1. 前序遍历
```python
def preorder_traversal(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
2. 中序遍历
```python
def inorder_traversal(root):
if not root:
return []
res = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
```
3. 后序遍历
```python
def postorder_traversal(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
```
4. 层序遍历
```python
def level_order_traversal(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
```
### 回答2:
二叉树是一种常见的树形结构,每个节点最多有两个子节点。二叉树的构造可以递归地进行,可以通过节点的左子树和右子树来构建整棵树。
以下是一个二叉树的构造示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def construct_tree(nums):
if not nums:
return None
root = TreeNode(nums[0])
node_queue = [root]
front = 0
index = 1
while index < len(nums):
node = node_queue[front]
front += 1
item = nums[index]
index += 1
if item is not None:
node.left = TreeNode(item)
node_queue.append(node.left)
if index >= len(nums):
break
item = nums[index]
index += 1
if item is not None:
node.right = TreeNode(item)
node_queue.append(node.right)
return root
```
四种二叉树的遍历算法分别是前序遍历、中序遍历、后序遍历和层序遍历:
前序遍历(根-左-右)的实现代码如下:
```python
def preorder_traversal(root):
if not root:
return []
traversal = []
stack = [root]
while stack:
node = stack.pop()
traversal.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return traversal
```
中序遍历(左-根-右)的实现代码如下:
```python
def inorder_traversal(root):
if not root:
return []
traversal = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
traversal.append(node.val)
node = node.right
return traversal
```
后序遍历(左-右-根)的实现代码如下:
```python
def postorder_traversal(root):
if not root:
return []
traversal = []
stack = [root]
while stack:
node = stack.pop()
traversal.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return traversal[::-1]
```
层序遍历的实现代码如下:
```python
def levelorder_traversal(root):
if not root:
return []
traversal = []
queue = [root]
while queue:
level = []
size = len(queue)
for _ in range(size):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
traversal.append(level)
return traversal
```
以上是二叉树的构造以及四种遍历算法的实现代码。
### 回答3:
二叉树的构造是通过建立节点对象及其关系来实现的。每个节点包含一个数据域和两个指针域,分别指向左子节点和右子节点。根据节点间的关系,我们可以通过指针域建立起一个二叉树的结构。
接下来是四种遍历算法的代码实现:
1. 前序遍历(Preorder Traversal):先访问根节点,再递归遍历左子树,最后递归遍历右子树。
```Python
def preorder_traversal(node):
if node is not None:
print(node.data)
preorder_traversal(node.left)
preorder_traversal(node.right)
```
2. 中序遍历(Inorder Traversal):先递归遍历左子树,再访问根节点,最后递归遍历右子树。
```Python
def inorder_traversal(node):
if node is not None:
inorder_traversal(node.left)
print(node.data)
inorder_traversal(node.right)
```
3. 后序遍历(Postorder Traversal):先递归遍历左子树,再递归遍历右子树,最后访问根节点。
```Python
def postorder_traversal(node):
if node is not None:
postorder_traversal(node.left)
postorder_traversal(node.right)
print(node.data)
```
4. 层序遍历(Level Order Traversal):从上到下逐层遍历二叉树的节点。
```Python
from collections import deque
def level_order_traversal(root):
if root is None:
return
queue = deque()
queue.append(root)
while queue:
node = queue.popleft()
print(node.data)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
```
以上是二叉树构造和四种遍历算法的实现。可以根据不同的需求选择适合的遍历方式来操作二叉树的节点。