c语言编程笔录

首页 >   > 笔记大全

笔记大全

c语言二叉树的前序遍历编程

更新时间:2023-09-11

前序遍历概述

前序遍历是二叉树遍历的一种方式之一,它的遍历顺序是先遍历父节点,然后再遍历左子节点,最后遍历右子节点。前序遍历的代码实现可以通过递归或迭代的方式来完成。

递归实现前序遍历

#include 

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

// 递归实现前序遍历
void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    // 先遍历根节点
    printf("%d ", root->data);
    
    // 再遍历左子节点
    preorderTraversal(root->left);
    
    // 最后遍历右子节点
    preorderTraversal(root->right);
}

迭代实现前序遍历

#include 
#include 

// 栈节点的定义
struct StackNode {
    struct TreeNode* treeNode;
    struct StackNode* next;
};

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

// 栈的定义
struct Stack {
    struct StackNode* top;
};

// 创建一个空栈
struct Stack* createStack() {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = NULL;
    return stack;
}

// 判断栈是否为空
int isEmpty(struct Stack* stack) {
    return stack->top == NULL;
}

// 入栈
void push(struct Stack* stack, struct TreeNode* treeNode) {
    struct StackNode* node = (struct StackNode*)malloc(sizeof(struct StackNode));
    node->treeNode = treeNode;
    node->next = stack->top;
    stack->top = node;
}

// 出栈并返回出栈节点
struct TreeNode* pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        return NULL;
    }
    struct StackNode* topNode = stack->top;
    struct TreeNode* treeNode = topNode->treeNode;
    stack->top = topNode->next;
    free(topNode);
    return treeNode;
}

// 迭代实现前序遍历
void iterativePreorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    // 创建一个空栈
    struct Stack* stack = createStack();
    
    // 将根节点入栈
    push(stack, root);
    
    while (!isEmpty(stack)) {
        // 弹出栈顶节点
        struct TreeNode* node = pop(stack);
        
        // 访问节点的值
        printf("%d ", node->data);
        
        // 先将右子节点入栈,使其后出栈
        if (node->right != NULL) {
            push(stack, node->right);
        }
        
        // 再将左子节点入栈,使其先出栈
        if (node->left != NULL) {
            push(stack, node->left);
        }
    }
}

总结

通过上述代码示例,我们可以看到前序遍历的实现方式。递归实现的前序遍历从根节点开始,先输出根节点的值,然后递归遍历左子树和右子树。迭代实现的前序遍历使用了栈来辅助实现,先将根节点入栈,然后循环弹出栈顶节点并输出其值,同时将右子节点先入栈,再将左子节点入栈。

前序遍历是一个常用的树遍历方式,它可以用来实现一些基于树结构的算法和问题,如查找某个节点是否存在于二叉树中、计算二叉树的高度等。在实际应用中,根据具体需求选择递归或迭代的实现方式,以及合适的数据结构辅助完成前序遍历操作。