非递归实现树的前序遍历C++

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);
        }
    }
}

相关问题

请你使用C++编写程序对二叉树进行遍历，包括非递归和递归遍历 其中非递归遍历包括前序遍历，中序遍历，后序遍历 。递归遍历包括前序遍历，中序遍历，后序遍历 。并且接受设计思路

好的，我可以为您解答这个问题。首先，我们需要先了解二叉树的遍历方式，包括前序遍历、中序遍历和后序遍历。其中，前序遍历是先访问根节点，然后访问左子树和右子树；中序遍历是先访问左子树，然后访问根节点和右子树；后序遍历是先访问左子树和右子树，最后访问根节点。

接下来，我们分别介绍递归遍历和非递归遍历的实现思路。

1. 递归遍历

递归遍历二叉树的思路较为简单，我们只需要按照遍历方式的顺序递归访问每个节点即可。具体实现如下：

前序遍历：

void preOrderTraversal(TreeNode* root) {
    if(root != nullptr) {
        cout << root->val << " ";
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

中序遍历：

void inOrderTraversal(TreeNode* root) {
    if(root != nullptr) {
        inOrderTraversal(root->left);
        cout << root->val << " ";
        inOrderTraversal(root->right);
    }
}

后序遍历：

void postOrderTraversal(TreeNode* root) {
    if(root != nullptr) {
        postOrderTraversal(root->left);
        postOrderTraversal(root->right);
        cout << root->val << " ";
    }
}

2. 非递归遍历

非递归遍历二叉树需要借助栈结构来实现。我们先将根节点入栈，然后按照遍历方式的顺序依次访问每个节点，并将其子节点入栈。具体实现如下：

前序遍历：

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

中序遍历：

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

后序遍历：

void postOrderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* node = root;
    TreeNode* lastVisited = nullptr;
    while(node != nullptr || !st.empty()) {
        while(node != nullptr) {
            st.push(node);
            node = node->left;
        }
        node = st.top();
        if(node->right == nullptr || node->right == lastVisited) {
            st.pop();
            cout << node->val << " ";
            lastVisited = node;
            node = nullptr;
        } else {
            node = node->right;
        }
    }
}

以上就是二叉树遍历的递归和非递归实现思路和代码。需要注意的是，这里使用的是二叉树节点的结构体，其中包含左子树、右子树和节点值。同时，为了实现非递归遍历，我们需要借助栈结构来存储节点信息。

非递归实现树的前序遍历栈的代码C++

void preorder(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);
        }
    }
}