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

void preorder(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) st.push(node->right);
        if (node->left) st.push(node->left);
    }
}

相关问题

一棵n个结点的完全二叉树用向量作存储结构，用非递归算法实现对该二叉树进行前序遍历。用顺序存储结构和栈c++代码实现

在C++中，我们可以使用数组（顺序存储结构）和标准库中的`stack`容器来实现对完全二叉树的非递归前序遍历。首先，我们需要创建一个结构体或类来表示节点，然后定义一个函数来进行遍历。这里是一个简单的示例：

#include <iostream>
using namespace std;

// 定义节点结构，假设每个节点有一个整数值
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

class BinaryTree {
private:
    TreeNode* root; // 根节点指针
    vector<TreeNode*> nodes; // 存储所有节点的向量

public:
    BinaryTree(int n) : root(nullptr), nodes(n, nullptr) {}

    // 添加节点到向量中，并处理完全二叉树特性
    void addNode(TreeNode* node, int index) {
        if (index >= nodes.size()) {
            nodes.resize(index + 1);
        }
        nodes[index] = node;
        if (node->left != nullptr) {
            addNode(node->left, 2 * index + 1); // 左孩子
        }
        if (node->right != nullptr) {
            addNode(node->right, 2 * index + 2); // 右孩子
        }
    }

    // 非递归前序遍历
    void preOrderTraversal() {
        stack<TreeNode*> s;
        if (root != nullptr) {
            s.push(root);
        }
        while (!s.empty()) {
            TreeNode* curr = s.top();
            cout << curr->val << " "; // 访问当前节点
            s.pop(); // 出栈

            // 如果左孩子存在，添加到栈顶
            if (curr->left != nullptr) {
                s.push(curr->left);
            }

            // 然后访问右孩子，因为完全二叉树右侧不存在，所以不需要单独处理
        }
    }
};

int main() {
    int n = 5; // 指定完全二叉树的节点数
    BinaryTree tree(n);

    // 假设添加了一些节点，此处略去具体操作
    // ...

    tree.preOrderTraversal(); // 前序遍历
    return 0;
}

在这个代码中，我们首先初始化了一个`BinaryTree`类，它有根节点指针和一个存储节点的动态数组。`addNode`函数用于构建完全二叉树的结构，而`preOrderTraversal`则利用栈数据结构实现了非递归的前序遍历。

问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能： 1…建立树 2…前序遍历树 3…中序(非递归)遍历树 4…后序遍历树 0…结束

好的，针对您的问题，我可以给出一个C++代码示例，实现一个简单的菜单，并调用相应的函数功能，代码如下：

#include<iostream>
#include<stack>

using namespace std;

//定义二叉树结点结构体
struct TreeNode{
    char data;  //存储二叉树结点的数据
    TreeNode* left;   //存储二叉树结点的左子树
    TreeNode* right;  //存储二叉树结点的右子树
};

//创建二叉树
void createBinaryTree(TreeNode* &root){
    char ch;
    cin>>ch;
    if(ch == '#'){
        root = NULL;
    }
    else{
        root = new TreeNode;
        root->data = ch;
        createBinaryTree(root->left);
        createBinaryTree(root->right);
    }
}

//前序遍历二叉树
void preOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    cout<<root->data<<" ";   //访问结点
    preOrder(root->left);   //前序遍历左子树
    preOrder(root->right);  //前序遍历右子树
}

//中序遍历二叉树（非递归）
void inOrder(TreeNode* root){
    stack<TreeNode*> s;   //定义一个栈
    TreeNode* p = root;
    while(p != NULL || !s.empty()){
        //将左子树的所有结点入栈
        while(p != NULL){
            s.push(p);
            p = p->left;
        }
        //此时栈顶结点为最左边的结点
        p = s.top();
        s.pop();
        cout<<p->data<<" ";  //访问结点
        //访问右子树
        p = p->right;
    }
}

//后序遍历二叉树
void postOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    postOrder(root->left);   //后序遍历左子树
    postOrder(root->right);  //后序遍历右子树
    cout<<root->data<<" ";   //访问结点
}

int main(){
    TreeNode* root;   //定义二叉树的根节点
    int choice;
    while(1){
        cout<<"------------------"<<endl;
        cout<<"1…建立树"<<endl;
        cout<<"2…前序遍历树"<<endl;
        cout<<"3…中序(非递归)遍历树"<<endl;
        cout<<"4…后序遍历树"<<endl;
        cout<<"0…结束"<<endl;
        cout<<"------------------"<<endl;
        cout<<"请输入您的选择：";
        cin>>choice;
        switch(choice){
            case 1:   //建立二叉树
                cout<<"请输入二叉树的结点，以'#'代表空结点："<<endl;
                createBinaryTree(root);   //创建二叉树
                break;
            case 2:   //前序遍历二叉树
                cout<<"前序遍历结果："<<endl;
                preOrder(root);    //前序遍历二叉树
                cout<<endl;
                break;
            case 3:   //中序遍历二叉树（非递归）
                cout<<"中序遍历结果："<<endl;
                inOrder(root);     //中序遍历二叉树（非递归）
                cout<<endl;
                break;
            case 4:   //后序遍历二叉树
                cout<<"后序遍历结果："<<endl;
                postOrder(root);   //后序遍历二叉树
                cout<<endl;
                break;
            case 0:   //结束程序
                cout<<"程序已结束！"<<endl;
                return 0;
            default:   //输入错误提示
                cout<<"您的输入有误，请重新输入！"<<endl;
                break;
        }
    }
    return 0;
}

在这份代码中，我们通过一个while循环实现了一个简单的菜单，用户可以根据菜单选择相应的操作，包括建立二叉树、前序遍历二叉树、中序遍历二叉树（非递归实现）和后序遍历二叉树。当用户选择结束操作时，程序会退出while循环，结束程序。