二叉树层次遍历递归算法

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

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

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

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

相关问题

C++生成二叉树实现遍历，先序遍历采用递归算法，层次遍历采用非递归算法

好的，下面是C++生成二叉树实现遍历的代码，先序遍历采用递归算法，层次遍历采用非递归算法：

#include <iostream>
#include <queue>
using namespace std;

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

// 生成二叉树
void createTree(TreeNode*& root) {
    int val;
    cin >> val;
    if (val == -1) {
        root = NULL;
        return;
    }
    root = new TreeNode(val);
    createTree(root->left);
    createTree(root->right);
}

// 先序遍历（递归）
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 层次遍历（非递归）
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);
        }
    }
}

int main() {
    TreeNode* root;
    createTree(root);
    cout << "先序遍历结果：";
    preorderTraversal(root);
    cout << endl;
    cout << "层次遍历结果：";
    levelOrderTraversal(root);
    cout << endl;
    return 0;
}

我已经完成了你的要求，请问还有其他问题吗？

建立二叉树，并实现二叉树的遍历，先序遍历采用递归算法实现，层次遍历用非递归算法来实现

好的，我来解答你的问题。

首先，建立二叉树需要定义一个二叉树的节点，包含左右子节点和节点值。我们可以按照下面的方式定义节点类：

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

接下来，我们可以用递归的方式实现二叉树的先序遍历。先序遍历的顺序是先遍历根节点，然后遍历左子树，最后遍历右子树。实现代码如下：

def preorderTraversal(root):
    if not root:
        return []
    res = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

最后，我们可以用非递归的方式实现二叉树的层次遍历。层次遍历的顺序是按照树的层次从上到下，从左到右遍历所有节点。我们可以用队列来实现非递归遍历。实现代码如下：

def levelOrderTraversal(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

这样，我们就完成了建立二叉树，以及实现二叉树的遍历。希望对你有所帮助！