数据结构二叉树遍历实验报告
数据结构二叉树遍历实验报告
1. 实验目的
本实验旨在通过实现二叉树的前序、中序和后序遍历算法，加深对二叉树遍历的理解，并验证算法的正确性。
2. 实验原理
2.1 二叉树
二叉树是一种特殊的树状数据结构，它的每个节点最多只能有两个子节点。二叉树可以为空树，也可以是由根节点、左子树和右子树组成的非空树。
2.2 遍历算法
二叉树的遍历算法包括前序遍历、中序遍历和后序遍历。
- 前序遍历：先访问根节点，然后依次递归访问左子树和右子树。
- 中序遍历：先递归访问左子树，然后访问根节点，最后递归访问右子树。
- 后序遍历：先递归访问左子树，然后递归访问右子树，最后访问根节点。
3. 实验过程
3.1 数据结构设计
首先，我们需要设计表示二叉树的数据结构。在本次实验中，二叉树的每个节点包含三个成员变量：值、左子节点和右子节点。我们可以使用面向对象编程语言提供的类来实现。
具体实现如下：
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):        self.val = val
self.left = left
self.right = right
```
3.2 前序遍历算法
前序遍历算法的实现主要包括以下步骤：
1. 若二叉树为空，则返回空列表。
2. 创建一个栈，用于存储遍历过程中的节点。
3. 将根节点入栈。
4. 循环执行以下步骤，直到栈为空：
- 弹出栈顶节点，并将其值添加到结果列表中。
- 若当前节点存在右子节点，则将右子节点压入栈。  - 若当前节点存在左子节点，则将左子节点压入栈。具体实现如下：
```python
def preorderTraversal(root):
if not root:
return []
stack = []
result = []
stack.append(root)
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
```
3.3 中序遍历算法
中序遍历算法的实现主要包括以下步骤：
1. 若二叉树为空，则返回空列表。
2. 创建一个栈，用于存储遍历过程中的节点。
3. 创建一个指针指向根节点。
4. 循环执行以下步骤，直到栈为空或指针为空：  - 将当前节点及其所有左子节点入栈。
- 弹出栈顶节点，并将其值添加到结果列表中。  - 将指针指向弹出节点的右子节点。
具体实现如下：
```python
def inorderTraversal(root):
if not root:
return []
stack = []
二叉树前序中序后序图解result = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
result.append(node.val)
node = node.right
return result
```
3.4 后序遍历算法
后序遍历算法的实现主要包括以下步骤：1. 若二叉树为空，则返回空列表。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。