采用二叉链表存储结构，完成二叉树的层次遍历，先序遍历的非递归算法和中序遍历的非递归算法。

二叉链表存储结构是一种常用的二叉树存储方式，可以用来实现二叉树的层次遍历、先序遍历和中序遍历的非递归算法。

二叉树的层次遍历可以使用队列来实现。从根节点开始，将其入队，然后依次出队，并将其左右子节点入队，直到队列为空。这样就可以按照层次遍历的顺序输出二叉树的所有节点。

先序遍历的非递归算法可以使用栈来实现。从根节点开始，将其入栈，然后依次出栈，并将其右子节点和左子节点入栈，直到栈为空。这样就可以按照先序遍历的顺序输出二叉树的所有节点。

中序遍历的非递归算法也可以使用栈来实现。从根节点开始，将其入栈，然后将其左子节点入栈，直到左子节点为空。然后依次出栈，并将其右子节点入栈，直到栈为空。这样就可以按照中序遍历的顺序输出二叉树的所有节点。

相关问题

采用二叉链表存储结构，完成二叉树的层次遍历，先序遍历的非递归算法和中序遍历的非递归算法的代码

二叉树的层次遍历非递归算法：

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

def levelOrder(root):
    if not root:
        return []
    res = []
    queue = [root]
    while queue:
        level = []
        for i in range(len(queue)):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)
    return res

先序遍历的非递归算法：

def preOrder(root):
    if not root:
        return []
    stack = [root]
    res = []
    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(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

(1)采用二叉链表存储结构，完成二叉树的层次遍历，先序遍历的非递归算法和中序遍历的非递归算法。

二叉链表存储结构是二叉树的常见存储方式，每个节点包括数据域、左子节点指针和右子节点指针。以下是二叉树的层次遍历、先序遍历和中序遍历的非递归算法实现。

1. 层次遍历

层次遍历需要借助队列来实现。从根节点开始，先将根节点入队，然后不断从队列中弹出节点，输出其数据域，同时将其左右子节点入队，直到队列为空。

void levelOrderTraversal(BiTree T){
    if(T == NULL) return;
    queue<BiTree> q;
    q.push(T);
    while(!q.empty()){
        BiTree node = q.front();
        q.pop();
        cout << node->data << " ";
        if(node->left) q.push(node->left);
        if(node->right) q.push(node->right);
    }
}

2. 先序遍历

先序遍历的非递归实现需要借助栈来实现。从根节点开始，将其压入栈中。然后不断从栈中弹出节点，输出其数据域，并将其右子节点压入栈中，再将其左子节点压入栈中。由于栈是先进后出的数据结构，所以先压入左子节点，保证左子节点先被访问。

void preOrderTraversal(BiTree T){
    if(T == NULL) return;
    stack<BiTree> s;
    s.push(T);
    while(!s.empty()){
        BiTree node = s.top();
        s.pop();
        cout << node->data << " ";
        if(node->right) s.push(node->right);
        if(node->left) s.push(node->left);
    }
}

3. 中序遍历

中序遍历的非递归实现也需要借助栈来实现。从根节点开始，将其压入栈中，然后不断将其左子节点压入栈中，直到最左子节点。然后从栈中弹出节点，输出其数据域，并将其右子节点压入栈中，进行下一轮循环。

void inOrderTraversal(BiTree T){
    if(T == NULL) return;
    stack<BiTree> s;
    BiTree node = T;
    while(node != NULL || !s.empty()){
        while(node != NULL){
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->data << " ";
        node = node->right;
    }
}