C++前序遍历实现报错：void类型赋值给node*类型问题求助

错误原因 #

C++标准库中std::stack的pop()方法是**无返回值（void）**的，它仅执行弹出栈顶元素的操作，不会返回该元素。你直接将S.pop()赋值给node*类型的变量root，必然触发"Assigning to 'node *' from incompatible type 'void'"的类型不兼容错误。

另外你的preOrderTraversalS函数声明返回node*，但函数内部没有任何return语句，这会导致未定义行为，需要修正返回值类型。

修正方案 #

1. 先通过stack::top()获取栈顶的node*指针，再调用pop()弹出元素
2. 将preOrderTraversalS的返回值类型改为void（因为函数仅做遍历输出，无需返回节点）

修正后的完整代码 #

#include <iostream>
#include <stack>

using namespace std;

class node {
public:
  int data;
  node *left;
  node *right;

  node(int d) {
    this->data = d;
    this->left = NULL;
    this->right = NULL;
  }
};

void preOrderTraversalR(node *root) {
  if (root) {
    cout << root->data << " ";
    preOrderTraversalR(root->left);
    preOrderTraversalR(root->right);
  }
}

void preOrderTraversalS(node *root){
    stack<node*> S;
    while(true){
        while(root){
            cout << root->data << " ";
            S.push(root);
            root = root->left;
        }
        if(S.empty()) break;
        root = S.top(); // 先获取栈顶元素
        S.pop();        // 再弹出栈顶元素
        root = root->right;
    }
}

node *createTree(node *root) {
  int val;
  cout << "Enter Node: ";
  cin >> val;

  if (val == -1) {
    return NULL;
  }
  root = new node(val);

  cout << "Enter node left of " << val << " : ";
  root->left = createTree(root->left);
  cout << "Enter node right of " << val << " : ";
  root->right = createTree(root->right);

  return root;
}

// 测试输入：8 3 1 -1 -1 6 4 -1 -1 7 -1 -1 10 -1 14 13 -1 -1
int main() {
  node *root = NULL;
  root = createTree(root);

  cout << "\n递归前序遍历结果：";
  preOrderTraversalR(root);
  
  cout << "\n栈实现前序遍历结果：";
  preOrderTraversalS(root);
  cout << endl;
}

额外说明 #

• 修正了createTree函数中的逻辑错误：原代码先创建节点再判断val == -1，会导致创建值为-1的无效节点，现在调整为先判断再创建节点
• 在preOrderTraversalS的输出中添加了空格，让遍历结果更易读
• 在main函数中添加了栈实现遍历的调用，方便测试

内容的提问来源于stack exchange，提问作者muffin