采用二叉链表法表示二叉树，设计并实现二叉树遍历的递归算法和非递归算法；

二叉树的遍历有三种方式：先序遍历、中序遍历和后序遍历。以下是二叉树的递归和非递归遍历算法的实现。

## 递归遍历算法

### 先序遍历

先访问根节点，然后递归访问左子树和右子树。

def preorder_traversal(root):
    if root:
        print(root.val)
        preorder_traversal(root.left)
        preorder_traversal(root.right)

### 中序遍历

先递归访问左子树，然后访问根节点，最后递归访问右子树。

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val)
        inorder_traversal(root.right)

### 后序遍历

先递归访问左子树和右子树，最后访问根节点。

def postorder_traversal(root):
    if root:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val)

## 非递归遍历算法

### 先序遍历

使用栈来模拟递归过程，先将根节点入栈，然后循环执行以下操作：弹出栈顶元素并访问，将其右子节点入栈，再将其左子节点入栈。注意入栈顺序，因为栈是后进先出的结构。

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

### 中序遍历

使用栈来模拟递归过程，先将所有左子节点入栈，然后循环执行以下操作：弹出栈顶元素并访问，将其右子节点入栈，再将其右子节点的所有左子节点入栈。

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

### 后序遍历

使用两个栈来模拟递归过程，先将根节点入栈1，然后循环执行以下操作：弹出栈1顶元素并入栈2，将其左子节点入栈1，再将其右子节点入栈1。最后将栈2中的元素依次弹出并访问。

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