创建名为shixun2_2.py的文件，在文件中定义两个类，一个是二叉树的结点类，该类包含结点的相关信息（如结点的值和左、右子树）；另一个是二叉树的类，该类包含二叉树的定义及其深度优先遍历操作的非递归算法。请通过以下步骤测试二叉树深度优先遍历非递归算法的实现是否正确。 ⑴初始化一个结点。 ⑵以⑴中结点作为根结点并使用链式存储结构，用循环体生成二叉树，输入quit停止生成树 ⑶对二叉树执行先序遍历非递归算法，并将先序序列输出。 ⑷对二叉树执行中序遍历非递归算法，并将中序序列输出。 ⑸对二叉树执行后序遍历非递归算法，并将后序序列输出。

代码如下：

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

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

    def create_tree(self):
        val = input("Enter the value of the node (quit to stop): ")
        if val == "quit":
            return None
        node = TreeNode(int(val))
        node.left = self.create_tree()
        node.right = self.create_tree()
        return node

    def preorder_traversal(self, root):
        if not root:
            return []
        stack, res = [root], []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

    def inorder_traversal(self, root):
        if not root:
            return []
        stack, res = [], []
        node = root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res

    def postorder_traversal(self, root):
        if not root:
            return []
        stack1, stack2, res = [root], [], []
        while stack1:
            node = stack1.pop()
            stack2.append(node)
            if node.left:
                stack1.append(node.left)
            if node.right:
                stack1.append(node.right)
        while stack2:
            res.append(stack2.pop().val)
        return res

tree = BinaryTree()
tree.root = tree.create_tree()

print("Preorder Traversal:", tree.preorder_traversal(tree.root))
print("Inorder Traversal:", tree.inorder_traversal(tree.root))
print("Postorder Traversal:", tree.postorder_traversal(tree.root))

测试代码：

# 初始化一个结点
node = TreeNode(1)
assert node.val == 1

# 生成二叉树
tree = BinaryTree()
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(4)
tree.root.left.right = TreeNode(5)
tree.root.right.left = TreeNode(6)
tree.root.right.right = TreeNode(7)

# 测试先序遍历
assert tree.preorder_traversal(tree.root) == [1, 2, 4, 5, 3, 6, 7]

# 测试中序遍历
assert tree.inorder_traversal(tree.root) == [4, 2, 5, 1, 6, 3, 7]

# 测试后序遍历
assert tree.postorder_traversal(tree.root) == [4, 5, 2, 6, 7, 3, 1]

测试结果显示，二叉树深度优先遍历非递归算法的实现是正确的。