二叉树前序遍历非递归怎么实现，请给出完整代码

二叉树的前序遍历非递归实现方式如下：

1. 创建一个栈，用于存储遍历过程中访问的节点。

2. 从根节点开始，将根节点入栈。

3. 重复以下步骤直到栈为空：

- 取出栈顶元素并访问。
- 如果栈顶元素的右子节点不为空，将右子节点入栈。
- 如果栈顶元素的左子节点不为空，将左子节点入栈。

代码如下：

def preorder_traversal(root):
    if root is None:
        return

    stack = []
    node = root
    while stack or node:
        while node:
            print(node.val)  # 访问节点
            stack.append(node)
            node = node.left
        node = stack.pop()
        node = node.right

这段代码使用了一个栈来模拟递归过程，每遇到一个节点就将其入栈，然后遍历它的左子树。当左子树遍历完成后，就从栈中取出栈顶元素并遍历它的右子树。

需要注意的是，在取出栈顶元素时，需要将其出栈。这样可以保证每个节点只会被遍历一次，并且保证了遍历的顺序。

相关问题

二叉树前序遍历非递归怎么实现，请给出完整C语言代码

非递归实现二叉树前序遍历的方法是使用栈进行模拟递归的过程。具体步骤如下：

1. 将根节点入栈。
2. 取出栈顶节点并访问。
3. 如果栈顶节点有右子节点，就将右子节点入栈。
4. 如果栈顶节点有左子节点，就将左子节点入栈。
5. 重复步骤 2~4 直到栈为空。

下面是用 C 语言实现二叉树前序遍历的非递归代码：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树的节点结构
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

// 创建二叉树
// 传入的数组是前序遍历的结果
struct TreeNode* createTree(int* preorder, int preorderSize) {
  if (preorderSize == 0) return NULL; // 空树

  // 创建根节点
  struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
  root->val = preorder[0];

  // 在前序遍历序列中找到第一个大于根节点的元素，
  // 该元素之前的元素对应根节点的左子树，之后的元素对应根节点的右子树
  int i;
  for (i = 1; i < preorderSize; i++) {
    if (preorder[i] > root->val) break;
  }

  // 递归创建左右子树
  root->left = createTree(preorder + 1, i - 1);
  root->right = createTree(preorder + i, preorderSize - i);

  return root;
}

// 二叉树前序遍历的非递归实现

二叉树前序遍历非递归

二叉树的前序遍历是非递归的方式通常通过栈来实现。前序遍历的顺序是根节点 -> 左子树 -> 右子树。以下是步骤：

1. 创建一个空栈，并将根节点压入栈中。
2. 当栈不为空时，执行以下操作：
a. 弹出栈顶元素，访问它（即当前节点）。
b. 如果该节点有右子节点，将其压入栈中。
c. 如果该节点有左子节点，将其压入栈中。
3. 重复步骤2，直到栈为空。

这种方法避免了递归带来的函数调用开销，适合处理大数据量的情况。非递归前序遍历的伪代码可以表示为：

void preOrder(Node node) {
    Stack<Node> stack;
    stack.push(node);
    
    while (!stack.isEmpty()) {
        Node current = stack.pop();
        // 访问当前节点
        processNode(current);
        
        if (current.right != null)
            stack.push(current.right);
        if (current.left != null)
            stack.push(current.left);
    }
}