1．设计实现二叉树类，要求： （1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。 （2）实现二叉树层次遍历的非递归算法。

好的,我来为您设计并实现一个符合要求的二叉树类。这个类将包含前序、中序、后序遍历,层次遍历(非递归),查找和销毁函数。以下是Python实现的代码:

from collections import deque

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if not self.root:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left:
                self._insert_recursive(node.left, value)
            else:
                node.left = TreeNode(value)
        else:
            if node.right:
                self._insert_recursive(node.right, value)
            else:
                node.right = TreeNode(value)

    def pre_order(self, node):
        if node:
            print(node.value, end=' ')
            self.pre_order(node.left)
            self.pre_order(node.right)

    def in_order(self, node):
        if node:
            self.in_order(node.left)
            print(node.value, end=' ')
            self.in_order(node.right)

    def post_order(self, node):
        if node:
            self.post_order(node.left)
            self.post_order(node.right)
            print(node.value, end=' ')

    def level_order(self):
        if not self.root:
            return
        queue = deque([self.root])
        while queue:
            node = queue.popleft()
            print(node.value, end=' ')
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    def find(self, value):
        return self._find_recursive(self.root, value)

    def _find_recursive(self, node, value):
        if not node:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            return self._find_recursive(node.left, value)
        else:
            return self._find_recursive(node.right, value)

    def destroy_tree(self, node):
        if node:
            self.destroy_tree(node.left)
            self.destroy_tree(node.right)
            del node

    def __del__(self):
        self.destroy_tree(self.root)

这个实现包含了以下功能:

1. 插入节点(`insert`方法)
2. 前序遍历(`pre_order`方法)
3. 中序遍历(`in_order`方法)
4. 后序遍历(`post_order`方法)
5. 层次遍历(`level_order`方法,非递归实现)
6. 查找节点(`find`方法)
7. 销毁树(`destroy_tree`方法)

使用示例:

# 创建二叉树
tree = BinaryTree()
values = [5, 3, 7, 2, 4, 6, 8]
for v in values:
    tree.insert(v)

# 前序遍历
print("前序遍历:")
tree.pre_order(tree.root)
print()

# 中序遍历
print("中序遍历:")
tree.in_order(tree.root)
print()

# 后序遍历
print("后序遍历:")
tree.post_order(tree.root)
print()

# 层次遍历
print("层次遍历:")
tree.level_order()
print()

# 查找
print("查找值4:", tree.find(4))
print("查找值9:", tree.find(9))

# 销毁树
del tree

这个实现满足了您的要求:

1. 使用二叉链式存储结构(左、右子节点指针)
2. 实现了前序、中序、后序遍历
3. 实现了层次遍历的非递归算法
4. 包含了查找函数
5. 包含了销毁函数的实现

您可以根据需要进一步修改或扩展这个类,例如添加更多功能或优化现有方法。