数据结构二叉树遍历实验报告简版.pdfVIP

数据结构二叉树遍历实验报告

数据结构二叉树遍历实验报告

1.实验目的

本实验旨在通过实现二叉树的前序、中序和后序遍历算法，加

深对二叉树遍历的理解，并验证算法的正确性。

2.实验原理

2.1二叉树

二叉树是一种特殊的树状数据结构，它的每个节点最多只能有

两个子节点。二叉树可以为空树，也可以是由根节点、左子树和右

子树组成的非空树。

2.2遍历算法

二叉树的遍历算法包括前序遍历、中序遍历和后序遍历。

-前序遍历：先访问根节点，然后依次递归访问左子树和右子

树。

-中序遍历：先递归访问左子树，然后访问根节点，最后递归

访问右子树。

-后序遍历：先递归访问左子树，然后递归访问右子树，最后

访问根节点。

3.实验过程

3.1数据结构设计

首先，我们需要设计表示二叉树的数据结构。在本次实验中，

二叉树的每个节点包含三个成员变量：值、左子节点和右子节点。

我们可以使用面向对象编程语言提供的类来实现。

具体实现如下：

```python

classTreeNode:

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

defpreorderTraversal(root):

ifnotroot:

return[]

stack=[]

result=[]

stack.append(root)

whilestack:

node=stack.pop()

result.append(node.val)

ifnode.right:

stack.append(node.right)

ifnode.left:

stack.append(node.left)

returnresult

```

3.3中序遍历算法

中序遍历算法的实现主要包括以下步骤：

1.若二叉树为空，则返回空列表。

2.创建一个栈，用于存储遍历过程中的节点。

3.创建一个指针指向根节点。

4.循环执行以下步骤，直到栈为空或指针为空：

-将当前节点及其所有左子节点入栈。

-弹出栈顶节点，并将其值添加到结果列表中。

-将指针指向弹出节点的右子节点。

具体实现如下：

```python

definorderTraversal(root):

ifnotroot:

return[]

stack=[]

result=[]

node=root

whilestackornode:

whilenode:

stack.append(node)

node=node.left

node=stack.pop()

result.append(node.val)

node=node.right

returnresult

```

3.4后序遍历算法

后序遍历算法的实现主要包括以下步骤：

1.若二叉树为空，则返回空列表。

2.创建两个栈，分别用于存储遍历过程中的节点和结果。

3.将根节点入栈1。

4.循环执行以下步骤，直到栈1为空：

-弹出栈1顶节点，并将其值添加到栈2中。