C语言前序遍历二叉树

以下是C语言实现二叉树前序遍历的递归和非递归方法：

1.递归方法：

void PreOrderTraverse(BiTree T) {
    if (T) {
        printf("%d ", T->data); //访问当前结点
        PreOrderTraverse(T->lchild); //遍历当前结点的左子树
        PreOrderTraverse(T->rchild); //遍历当前结点的右子树
    }
}

2.非递归方法：

void PreOrderTraverse(BiTree T) {
    if (!T) {
        return;
    }
    BiTree stack[MAXSIZE];
    int top = -1;
    stack[++top] = T;
    while (top != -1) {
        BiTree p = stack[top--];
        printf("%d ", p->data); //访问当前结点
        if (p->rchild) {
            stack[++top] = p->rchild; //先将右子树入栈
        }
        if (p->lchild) {
            stack[++top] = p->lchild; //再将左子树入栈
        }
    }
}

相关问题

使用c语言编写前序遍历二叉树

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

struct node
{
int data;
struct node *left;
struct node *right;
};

struct node *create_node(int data)
{
struct node *new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

void preorder(struct node *root)
{
if(root != NULL)
{
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}

int main()
{
struct node *root = create_node(1);
root->left = create_node(2);
root->right = create_node(3);
root->left->left = create_node(4);
root->left->right = create_node(5);

printf("Preorder traversal of binary tree is: ");
preorder(root);

return 0;
}

C语言堆栈实现二叉树前序遍历

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

#define MAXSIZE 100

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

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

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

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

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

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

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

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

int main() {
    TreeNode *root = (TreeNode *) malloc(sizeof(TreeNode));
    root->data = 'A';
    root->left = (TreeNode *) malloc(sizeof(TreeNode));
    root->left->data = 'B';
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (TreeNode *) malloc(sizeof(TreeNode));
    root->right->data = 'C';
    root->right->left = (TreeNode *) malloc(sizeof(TreeNode));
    root->right->left->data = 'D';
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (TreeNode *) malloc(sizeof(TreeNode));
    root->right->right->data = 'E';
    root->right->right->left = NULL;
    root->right->right->right = NULL;
    printf("Preorder traversal: ");
    preOrder(root);
    printf("\n");
    return 0;
}