树结构及相关算法编程实验报告

一、实验目的

1. 掌握树结构的基本概念和性质；
2. 掌握树的遍历算法：先序遍历、中序遍历、后序遍历和层次遍历；
3. 掌握树的存储方式：双亲表示法、孩子兄弟表示法、二叉树等；
4. 掌握树的基本操作：创建、插入、删除、查找等；
5. 通过编程实现以上内容，加深对树结构和算法的理解。

二、实验内容

1. 设计一个程序，实现二叉树的创建，插入和删除操作；
2. 设计一个程序，实现二叉树的先序遍历、中序遍历、后序遍历和层次遍历算法；
3. 设计一个程序，实现树的孩子兄弟表示法存储方式；
4. 设计一个程序，实现树的前序遍历、后序遍历和层次遍历算法；
5. 分析以上程序的时间复杂度和空间复杂度。

三、实验过程及结果

1. 二叉树的创建、插入和删除操作

二叉树的创建、插入和删除操作是二叉树基本操作之一，下面是基于链式存储结构的二叉树的实现代码。

# 定义二叉树结点类
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 定义二叉树类
class BinaryTree:
    def __init__(self):
        self.root = None
    
    # 创建二叉树
    def create(self, values):
        if not values:
            return None
        self.root = TreeNode(values[0])
        queue = [self.root]
        front = 0
        index = 1
        while index < len(values):
            node = queue[front]
            front += 1
            if values[index] != None:
                node.left = TreeNode(values[index])
                queue.append(node.left)
            index += 1
            if index < len(values) and values[index] != None:
                node.right = TreeNode(values[index])
                queue.append(node.right)
            index += 1
    
    # 插入结点
    def insert(self, value):
        if not self.root:
            self.root = TreeNode(value)
            return
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            if not node.left:
                node.left = TreeNode(value)
                return
            elif not node.right:
                node.right = TreeNode(value)
                return
            else:
                queue.append(node.left)
                queue.append(node.right)

    # 删除结点
    def delete(self, value):
        if not self.root:
            return
        if self.root.value == value:
            self.root = None
            return
        parent = None
        node = self.root
        queue = [node]
        while queue:
            node = queue.pop(0)
            if node.value == value:
                if parent.left == node:
                    parent.left = None
                else:
                    parent.right = None
                return
            parent = node
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

2. 二叉树的先序遍历、中序遍历、后序遍历和层次遍历算法

二叉树的遍历算法是二叉树基本操作之一，下面是基于递归的二叉树遍历算法的实现代码。

# 定义二叉树结点类
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 定义二叉树类
class BinaryTree:
    def __init__(self):
        self.root = None
    
    # 创建二叉树
    def create(self, values):
        if not values:
            return None
        self.root = TreeNode(values[0])
        queue = [self.root]
        front = 0
        index = 1
        while index < len(values):
            node = queue[front]
            front += 1
            if values[index] != None:
                node.left = TreeNode(values[index])
                queue.append(node.left)
            index += 1
            if index < len(values) and values[index] != None:
                node.right = TreeNode(values[index])
                queue.append(node.right)
            index += 1
    
    # 插入结点
    def insert(self, value):
        if not self.root:
            self.root = TreeNode(value)
            return
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            if not node.left:
                node.left = TreeNode(value)
                return
            elif not node.right:
                node.right = TreeNode(value)
                return
            else:
                queue.append(node.left)
                queue.append(node.right)

    # 删除结点
    def delete(self, value):
        if not self.root:
            return
        if self.root.value == value:
            self.root = None
            return
        parent = None
        node = self.root
        queue = [node]
        while queue:
            node = queue.pop(0)
            if node.value == value:
                if parent.left == node:
                    parent.left = None
                else:
                    parent.right = None
                return
            parent = node
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    # 先序遍历
    def pre_order_traverse(self, root):
        if not root:
            return
        print(root.value, end=' ')
        self.pre_order_traverse(root.left)
        self.pre_order_traverse(root.right)

    # 中序遍历
    def in_order_traverse(self, root):
        if not root:
            return
        self.in_order_traverse(root.left)
        print(root.value, end=' ')
        self.in_order_traverse(root.right)

    # 后序遍历
    def post_order_traverse(self, root):
        if not root:
            return
        self.post_order_traverse(root.left)
        self.post_order_traverse(root.right)
        print(root.value, end=' ')

    # 层次遍历
    def level_order_traverse(self, root):
        if not root:
            return
        queue = [root]
        while queue:
            node = queue.pop(0)
            print(node.value, end=' ')
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

3. 树的孩子兄弟表示法存储方式

树的孩子兄弟表示法存储方式是树的一种常用存储方式，下面是基于孩子兄弟表示法的树的实现代码。

# 定义树结点类
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.child = None
        self.sibling = None

# 定义树类
class Tree:
    def __init__(self):
        self.root = None
    
    # 创建树
    def create(self, values):
        if not values:
            return None
        self.root = TreeNode(values[0])
        parent = self.root
        for value in values[1:]:
            if value == None:
                parent = parent.sibling
            else:
                node = TreeNode(value)
                if not parent.child:
                    parent.child = node
                else:
                    sibling = parent.child
                    while sibling.sibling:
                        sibling = sibling.sibling
                    sibling.sibling = node
                parent = node
    
    # 前序遍历
    def pre_order_traverse(self, root):
        if not root:
            return
        print(root.value, end=' ')
        self.pre_order_traverse(root.child)
        self.pre_order_traverse(root.sibling)

    # 后序遍历
    def post_order_traverse(self, root):
        if not root:
            return
        self.post_order_traverse(root.child)
        print(root.value, end=' ')
        self.post_order_traverse(root.sibling)

    # 层次遍历
    def level_order_traverse(self, root):
        if not root:
            return
        queue = [root]
        while queue:
            node = queue.pop(0)
            print(node.value, end=' ')
            if node.child:
                queue.append(node.child)
            if node.sibling:
                queue.append(node.sibling)

四、实验总结

本次实验主要学习了树结构及相关算法的基本概念和性质，掌握了树的存储方式和基本操作，以及树的遍历算法，包括先序遍历、中序遍历、后序遍历和层次遍历算法。通过编程实现了二叉树和树的孩子兄弟表示法存储方式的创建、插入和删除操作，以及二叉树和树的前序遍历、后序遍历和层次遍历算法，并对其时间复杂度和空间复杂度进行了分析。通过本次实验的学习，加深了对树结构和算法的理解，提高了编程能力和实践能力。