c++输出二叉树遍历

以下是C++中二叉树前序、中序、后序遍历的递归和非递归实现，以及层序遍历和深度优先遍历的代码和讲解：

1.1 前序遍历（Preorder Traversal）：

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

// 非递归实现
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";
        if (node->right != NULL) {
            s.push(node->right);
        }
        if (node->left != NULL) {
            s.push(node->left);
        }
    }
}

1.2 中序遍历（Inorder Traversal）：

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

// 非递归实现
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (node != NULL || !s.empty()) {
        while (node != NULL) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

1.3 后序遍历（Postorder Traversal）：

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

// 非递归实现
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* node = root;
    TreeNode* lastVisited = NULL;
    while (node != NULL || !s.empty()) {
        while (node != NULL) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        if (node->right == NULL || node->right == lastVisited) {
            cout << node->val << " ";
            s.pop();
            lastVisited = node;
            node = NULL;
        } else {
            node = node->right;
        }
    }
}

1.4 层序遍历（Level Order Traversal）：

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

1.5 深度优先遍历（Depth First Traversal）：

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