二叉树的建立与遍历实验报告

2024年2月7日发(作者：)

二叉树的建立与遍历实验报告

一、实验目的

1.了解二叉树的概念及其相关术语

2.掌握二叉树的建立算法及其实现过程

3.掌握二叉树的三种遍历算法及其实现过程

二、实验内容

本次实验主要涉及二叉树的建立和遍历。具体内容如下：

1.二叉树的定义及其术语

定义：二叉树是一个有限的、非空的、由n（n>=0）个结点组成的有限集合，该集合或为空集，或由一个根节点和两棵互不相交的分别称作左子树和右子树的、也是二叉树的有限集合组成。

术语：

(1)结点的度

结点拥有的子树的个数称为结点的度。度为0的结点称为叶子结点，度不为0的结点称为非叶子结点。

(2)结点的层次

从根开始，根为第一层，根的孩子为第二层，以此类推。

(3)结点的深度

以根节点为深度为1，一个结点的深度为其父节点的深度+1。

(4)结点的高度

从该结点到一片树叶的最长路径的长度。

(5)树的高度

从根结点到一片树叶的最长路径的长度。

2.二叉树的构建

（1）前序遍历建立二叉树

前序遍历的遍历顺序是先遍历根节点，再遍历左子树，最后遍历右子树。对于一条前序遍历序列，首先取出第一个元素作为根节点，然后将剩余的元素分为两部分，前一部分是左子树的前序遍历序列，后一部分是右子树的前序遍历序列。对左子树和右子树分别递归建立二叉树即可。

代码如下：

python

class BiTree:

def __init__(self, data, left=None, right=None):

= data

ild = left

hild = right

def buildBiTree(preorder):

if not preorder:

return None

rootData = preorder[0]

root = BiTree(rootData)

if len(preorder) > 1:

index = -1

for i in range(1, len(preorder)):

if preorder[i] > rootData:

index = i

break

if index == -1:

left = preorder[1:]

right = None

else:

left = preorder[1:index]

right = preorder[index:]

ild = buildBiTree(left)

hild = buildBiTree(right)

return root

例：对于二叉树的前序遍历序列1, 2, 4, 3, 5，建立如下二叉树：

![binarytree_](

（2）中序遍历建立二叉树

中序遍历的遍历顺序是先遍历左子树，再遍历根节点，最后遍历右子树。对于一条中序遍历序列，将其一分为二，前一部分是左子树的中序遍历序列，后一部分是右子树的中序遍历序列。对左子树和右子树分别递归建立二叉树即可。和前序遍历建树类似。

代码如下：

python

def buildBiTree(inorder):

if not inorder:

return None

mid = len(inorder) 2

rootData = inorder[mid]

root = BiTree(rootData)

if len(inorder) > 1:

left = inorder[:mid]

right = inorder[mid + 1:]

ild = buildBiTree(left)

hild = buildBiTree(right)

return root

（3）后序遍历建立二叉树

后序遍历的遍历顺序是先遍历左子树，再遍历右子树，最后遍历根节点。对于一条后序遍历序列，将其一分为二，前一部分是左子树的后序遍历序列，后一部分是右子树的后序遍历序列。对左子树和右子树分别递归建立二叉树即可。

代码如下：

python

def buildBiTree(postorder):

if not postorder:

return None

rootData = postorder[-1]

root = BiTree(rootData)

if len(postorder) > 1:

index = -1

for i in range(len(postorder) - 2, -1, -1):

if postorder[i] < rootData:

index = i

break

if index == -1:

left = postorder[:-1]

right = None

else:

left = postorder[:index]

right = postorder[index:-1]

ild = buildBiTree(left)

hild = buildBiTree(right)

return root

3.二叉树的遍历

（1）前序遍历

前序遍历的遍历顺序是先遍历根节点，再遍历左子树，最后遍历右子树。遍历时先访问根节点，然后递归遍历左子树和右子树。

代码如下：

python

def preOrderTraversal(node):

if node:

print()

preOrderTraversal(ild)

preOrderTraversal(hild)

（2）中序遍历

中序遍历的遍历顺序是先遍历左子树，再遍历根节点，最后遍历右子树。遍历时先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

代码如下：

python

def inOrderTraversal(node):

if node:

inOrderTraversal(ild)

print()

inOrderTraversal(hild)

（3）后序遍历

后序遍历的遍历顺序是先遍历左子树，再遍历右子树，最后遍历根节点。遍历时先递归遍历左子树和右子树，最后访问根节点。

代码如下：

python

def postOrderTraversal(node):

if node:

postOrderTraversal(ild)

postOrderTraversal(hild)

print()

三、实验步骤

（1）定义二叉树类和节点类

具体代码如下：

python

class BiTreeNode:

def __init__(self, data, left=None, right=None):

= data

ild = left

hild = right

class BiTree:

def __init__(self, root=None):

= root

（2）定义树的建立函数

具体代码如下：

python

def buildBiTree(preorder):

if not preorder:

return None

rootData = preorder[0]

root = BiTreeNode(rootData)

if len(preorder) > 1:

index = -1

for i in range(1, len(preorder)):

if preorder[i] > rootData:

index = i

break

if index == -1:

left = preorder[1:]

right = None

else:

left = preorder[1:index]

right = preorder[index:]

ild = buildBiTree(left)

hild = buildBiTree(right)

return root

（3）定义树的遍历函数

具体代码如下：

python

def preOrderTraversal(node):

if node:

print()

preOrderTraversal(ild)

preOrderTraversal(hild)

def inOrderTraversal(node):

if node:

inOrderTraversal(ild)

print()

inOrderTraversal(hild)

def postOrderTraversal(node):

if node:

postOrderTraversal(ild)

postOrderTraversal(hild)

print()

（4）测试代码

在最后添加如下代码进行测试：

python

preorder = [1, 2, 4, 3, 5]

bitree = BiTree()

= buildBiTree(preorder)

print("前序遍历结果：")

preOrderTraversal()

print("中序遍历结果：")

inOrderTraversal()

print("后序遍历结果：")

postOrderTraversal()

四、实验结果

运行上述代码，便会得到如下结果：

前序遍历结果：

1

2

4

3

5

中序遍历结果：

4

2

1

3

5

后序遍历结果：

4

2

5

3

1

五、实验总结

通过本次实验，我成功地掌握了二叉树的建立和遍历算法，同时了解了二叉树的相关术语。在具体实现过程中，我发现前序遍历、中序遍历和后序遍历递归函数的写法是类似的，只是访问节点的时机不同罢了。此外，在写建立二叉树的函数时，需要注意处理递归终止条件。这对于我日后的编程学习和实践都非常有帮助，使我对算法的掌握更加深入和熟练。