3.用二叉链表作为存储结构，建立一棵\n\n二叉树。 分别按先序、中序、后序和\n\n层次顺序遍历二叉树。 按中序顺序非\n\n递归遍历二叉树 编写交换二叉树中所\n\n有结点的左、右孩子的非递归算法。

### 回答1：
建立二叉树时，可以使用二叉链表作为存储结构。在二叉链表中，每个节点包含三个部分：数据域、左子树指针和右子树指针。通过不断插入节点，可以构建一棵二叉树。

按先序、中序、后序和层次顺序遍历二叉树时，可以使用递归或非递归的方式。其中，先序遍历的顺序是根节点、左子树、右子树；中序遍历的顺序是左子树、根节点、右子树；后序遍历的顺序是左子树、右子树、根节点；层次遍历的顺序是从上到下、从左到右。

按中序顺序非递归遍历二叉树时，可以使用栈来实现。首先将根节点入栈，然后将左子树全部入栈，直到没有左子树为止。然后弹出栈顶元素，访问该节点，再将右子树入栈。重复上述步骤，直到栈为空。

交换二叉树中所有节点的左、右孩子的非递归算法可以使用层次遍历实现。首先将根节点入队列，然后依次取出队列中的节点，交换该节点的左、右孩子，并将左、右孩子入队列。重复上述步骤，直到队列为空。

### 回答2：
二叉树是一种重要的数据结构，常被用于算法和编程中。二叉链表作为二叉树的存储结构之一，具有良好的可读性和易操作性。本文将介绍如何用二叉链表建立一棵二叉树，并分别按先序、中序、后序和层次顺序遍历二叉树，以及按中序顺序非递归遍历二叉树和交换二叉树中所有结点的左、右孩子的非递归算法。

二叉链表表示二叉树，包括一个指向左子树的左孩子指针、一个指向右子树的右孩子指针和一个保存根节点的数据域。二叉链表相比于链式存储和顺序存储更为灵活和易操作。对于一颗二叉树，我们可以通过递归的方式来建立它的二叉链表表示。

下面是建立一棵二叉树的示例代码：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) {
        return NULL;
    }
    int root_val = preorder[0];
    TreeNode* root = new TreeNode(root_val);
    int pos = find(inorder.begin(), inorder.end(), root_val) - inorder.begin();
    vector<int> inorder_left(inorder.begin(), inorder.begin() + pos);
    vector<int> inorder_right(inorder.begin() + pos + 1, inorder.end());
    vector<int> preorder_left(preorder.begin() + 1, preorder.begin() + 1 + inorder_left.size());
    vector<int> preorder_right(preorder.begin() + 1 + inorder_left.size(), preorder.end());
    root->left = buildTree(preorder_left, inorder_left);
    root->right = buildTree(preorder_right, inorder_right);
    return root;
}

可以看到，我们先取先序遍历数组的第一个元素作为根节点的值，并在中序遍历数组中找到根节点的位置。然后把中序遍历数组分为左子树和右子树两个部分，在先序遍历数组中分别取出左子树和右子树的元素，递归的调用建立左子树和右子树的函数，最后返回根节点即可。

接下来，我们分别介绍通过不同的遍历顺序来遍历二叉树。对于一棵二叉树，常用的四种遍历顺序分别是：先序遍历、中序遍历、后序遍历和层次遍历。

先序遍历顺序是，先输出当前节点的值，然后遍历左子树，最后遍历右子树。中序遍历顺序是，先遍历左子树，然后输出当前节点的值，最后遍历右子树。

后序遍历顺序是，先遍历左子树，然后遍历右子树，最后输出当前节点的值。层次遍历是，从上到下、从左到右依次遍历每个节点。

以下是二叉树四种遍历顺序的示例代码：

void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

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

对于中序遍历非递归遍历的算法，我们可以使用栈来实现。首先把当前节点入栈，然后遍历它的左子树，把左子树的所有节点都入栈。最后从栈中取出一个节点，输出这个节点的值，再遍历右子树即可。

以下是中序遍历非递归遍历的示例代码：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur || !s.empty()) {
        while (cur) {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        s.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

最后，我们来介绍如何交换二叉树中所有结点的左、右孩子的非递归算法。我们可以使用队列来实现交换，首先把根节点入队，然后在队列非空的情况下，弹出队首元素，交换其中的左右孩子，如果孩子不为空，则将左右孩子入队即可。

以下是交换二叉树中所有结点的左、右孩子的非递归算法示例代码：

TreeNode* invertTree(TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        TreeNode* left = node->left;
        node->left = node->right;
        node->right = left;
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }
    return root;
}

以上就是关于二叉树的建立和遍历，以及非递归交换左右孩子的介绍。二叉树作为一种基础的数据结构，我们需要掌握它的建立和遍历方法，这有助于我们在算法和编程中更好的使用它。

### 回答3：
二叉树是一种常见的数据结构，可以用二叉链表作为存储结构，下面将介绍如何建立、遍历和交换二叉树的算法。

1. 建立二叉树：可以按照先序遍历的顺序输入节点信息，如果是空节点则输入“#”，递归创建左右子树即可。

2. 先序遍历：对于当前节点，先输出节点值，再递归遍历左右子树。

3. 中序遍历：对于当前节点，先递归遍历左子树，再输出节点值，最后递归遍历右子树。

4. 后序遍历：对于当前节点，先递归遍历左右子树，最后输出节点值。

5. 层次遍历：利用队列先进先出的特性，先将根节点入队，然后从队首取出节点，输出节点值，并将其左右子节点入队，直到队列为空。

6. 中序非递归遍历：利用栈来实现，首先遍历其左子树，将节点入栈，然后依次出栈，输出节点值，并遍历右子树。

7. 交换二叉树中所以节点的左右孩子的非递归算法：实现思路与中序非递归遍历类似，对于每个节点，交换左右子节点，如果其左右子节点不为空，则将其入栈。依次出栈，交换节点的左右子节点，并将其子节点入栈，直到栈为空。

以上就是使用二叉链表存储结构建立、遍历和交换二叉树的算法，需要注意的是，根据不同的遍历方法会得到不同的遍历序列，这些序列存储了二叉树的所有节点信息，能够方便地实现二叉树的各种操作。