用堆栈实现二叉树的前序遍历

1. 创建一个空栈，将根节点入栈。
2. 当栈不为空时，执行以下操作：
1. 弹出栈顶元素，并输出它的值。
2. 先将右子节点（如果有）入栈。
3. 再将左子节点（如果有）入栈。
3. 重复步骤2，直到栈为空。

代码实现（假设二叉树节点的数据结构为Node，包括值、左子节点和右子节点）：

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

相关问题

堆栈实现二叉树前序遍历

二叉树前序遍历的顺序为：根节点 -> 左子树 -> 右子树。因此可以使用堆栈来实现。

具体实现步骤如下：

1. 将根节点入栈。

2. 循环执行以下操作：

- 取出栈顶节点，输出其值。

- 如果该节点存在右子树，将右子树入栈。

- 如果该节点存在左子树，将左子树入栈。

3. 当栈为空时，遍历完成。

代码实现如下：

public void preOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

c语言用堆栈实现二叉树的前序遍历

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

#define MAX_SIZE 100

typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

typedef struct Stack {
TreeNode *data[MAX_SIZE];
int top;
} Stack;

void initStack(Stack *stack) {
stack->top = -1;
}

int isStackEmpty(Stack *stack) {
return stack->top == -1;
}

int isStackFull(Stack *stack) {
return stack->top == MAX_SIZE - 1;
}

void push(Stack *stack, TreeNode *node) {
if (isStackFull(stack)) {
printf("Stack is full!\n");
return;
}
stack->top++;
stack->data[stack->top] = node;
}

TreeNode *pop(Stack *stack) {
if (isStackEmpty(stack)) {
printf("Stack is empty!\n");
return NULL;
}
TreeNode *node = stack->data[stack->top];
stack->top--;
return node;
}

TreeNode *createTreeNode(char data) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

TreeNode *createBinaryTree() {
char data;
scanf("%c", &data);
if (data == '#') {
return NULL;
}
TreeNode *node = createTreeNode(data);
node->left = createBinaryTree();
node->right = createBinaryTree();
return node;
}

void preorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
Stack stack;
initStack(&stack);
push(&stack, root);
while (!isStackEmpty(&stack)) {
TreeNode *node = pop(&stack);
printf("%c ", node->data);
if (node->right) {
push(&stack, node->right);
}
if (node->left) {
push(&stack, node->left);
}
}
}

int main() {
TreeNode *root = createBinaryTree();
printf("Preorder traversal:");
preorderTraversal(root);
printf("\n");
return 0;
}