二叉树的非递归遍历前序c的

前序遍历是一种常见的二叉树遍历顺序，它按照“根节点 -> 左子树 -> 右子树”的顺序访问每个节点。非递归前序遍历通常需要借助栈数据结构来辅助实现。以下是C语言中非递归方式实现前序遍历的步骤：

定义一个函数preorderTraversal，接受二叉树的根节点作为参数。
创建一个空栈，并将根节点压入栈中。
当栈不为空时，循环执行以下操作：
a. 弹出栈顶元素，输出当前节点值（因为是最先访问的，所以是前序的第一个）。
b. 如果该节点有右孩子，将其右孩子压入栈中。
c. 如果该节点有左孩子，将其左孩子压入栈中，因为我们需要保证左孩子始终在右孩子之前处理。
遍历完成后，返回。

void preorderTraversal(Node* root) {
if (root == NULL) return;
Stack* stack = createStack(); // 初始化一个栈
push(stack, root); // 根节点进栈

while (!isEmpty(stack)) {
Node* node = pop(stack);
printf("%d ", node->data); // 输出节点值
if (node->right != NULL) push(stack, node->right); // 先处理右子树
if (node->left != NULL) push(stack, node->left); // 再处理左子树
}
}
登录后复制