试编写一个对二叉树T进行先根遍历的非递归算法。

非递归的先根遍历算法需要使用栈来存储未遍历的节点，具体实现步骤如下：

1. 将根节点入栈。
2. 当栈不为空时，执行以下操作：
- 弹出栈顶节点，并访问该节点。
- 如果该节点有右子树，则将右子树入栈。
- 如果该节点有左子树，则将左子树入栈。

以下是Python实现代码：

def preorder_traversal(root):
    if not root:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

其中，root是二叉树的根节点，val是节点的值。result是存储遍历结果的列表。

相关问题

用伪码语言编写一个对二叉树T进行先根遍历的非递归算法。

以下是对二叉树T进行先根遍历的非递归算法的伪代码：

Stack stack; // 创建一个栈
stack.push(T); // 将二叉树T的根节点压入栈中

while(!stack.isEmpty()) {
  Node node = stack.pop(); // 弹出栈顶节点
  visit(node); // 访问该节点

  // 将右子节点和左子节点依次压入栈中
  if(node.right != null) {
    stack.push(node.right);
  }
  if(node.left != null) {
    stack.push(node.left);
  }
}

注解：
- `Stack` 表示栈，可以使用数组或链表实现。
- `Node` 表示二叉树节点，包含左右子节点和数据等属性。
- `visit(node)` 表示访问节点的操作，例如输出节点数据值等。

二叉树采用二叉链表存储，试写出对二叉树的先序遍历非递归算法

二叉树的先序遍历非递归算法需要借助栈来实现，具体步骤如下：

1. 首先将根节点入栈。

2. 循环执行以下操作，直到栈为空：

a. 弹出栈顶元素，并访问它的值。

b. 如果该节点有右子树，将其右子树入栈。

c. 如果该节点有左子树，将其左子树入栈。

下面是该算法的Python代码实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def preorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

其中，TreeNode是二叉树节点的定义，preorderTraversal函数接受一个根节点，返回该二叉树的先序遍历结果。