二叉树的创建及遍历，递归和非递归c++

二叉树的创建及遍历有很多种实现方式，下面我分别介绍一下递归和非递归的方式。

1. 递归实现二叉树的创建及遍历

定义二叉树节点的结构体：

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

二叉树的创建采用递归方式，每次递归处理左右子树：

TreeNode* createBinaryTree(vector<int>& nums, int index) {
    if (index >= nums.size() || nums[index] == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(nums[index]);
    root->left = createBinaryTree(nums, index * 2 + 1);
    root->right = createBinaryTree(nums, index * 2 + 2);
    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 << " ";
}

2. 非递归实现二叉树的遍历

前序遍历采用非递归方式，使用栈进行迭代，先将根节点压入栈中，然后循环处理栈中节点，每次处理一个节点时，先访问该节点，再将右子节点压入栈中，最后将左子节点压入栈中，这样可以保证左子节点先于右子节点被访问：

void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        cout << node->val << " ";
        if (node->right != NULL) st.push(node->right);
        if (node->left != NULL) st.push(node->left);
    }
}

中序遍历采用非递归方式，使用栈进行迭代，先将所有的左子节点压入栈中，然后循环处理栈中节点，每次处理一个节点时，先访问该节点，然后将右子节点压入栈中，这样可以保证左子树先于根节点被访问，右子树后于根节点被访问：

void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur != NULL || !st.empty()) {
        while (cur != NULL) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        cout << cur->val << " ";
        cur = cur->right;
    }
}

后序遍历采用非递归方式，使用栈进行迭代，需要使用两个栈，先将根节点压入第一个栈中，然后循环处理第一个栈中节点，每次处理一个节点时，将该节点的左子节点和右子节点分别压入第一个栈中，然后将该节点压入第二个栈中，这样可以保证左子树和右子树都先于根节点被访问，最后从第二个栈中依次弹出节点，即为后序遍历的结果：

void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> st1, st2;
    st1.push(root);
    while (!st1.empty()) {
        TreeNode* node = st1.top();
        st1.pop();
        st2.push(node);
        if (node->left != NULL) st1.push(node->left);
        if (node->right != NULL) st1.push(node->right);
    }
    while (!st2.empty()) {
        cout << st2.top()->val << " ";
        st2.pop();
    }
}