0801学习笔记

数据结构-代码实现

下文为三种二叉树遍历的c语言代码实现，包括：

前序遍历：
1. 递归
2. 非递归
中序遍历
1. 递归
2. 非递归
后序遍历
1. 递归
2. 非递归

以下为头文件tree.h对各种数据结构和函数的定义

#include "stack.h"
#define TREE_DATATYPE int

typedef struct Btree
{
    TREE_DATATYPE data;
    struct Btree *left_child;
    struct Btree *right_child;
    //....
} Btree;
void bt_printf(Btree *node);

Btree *bt_new_node(TREE_DATATYPE value);

// Preorder Traversal
void bt_pre_rec(Btree *node, void (*visit)(Btree *));
void bt_pre_nonrec(Btree *root, void (*visit)(Btree *));
// Inorder Traversal
void bt_in_rec(Btree *root, void (*visit)(Btree *));
void bt_in_nonrec(Btree *root, void (*visit)(Btree *));
// Postorder Traversal
void bt_post_rec(Btree *root, void (*visit)(Btree *));
void bt_post_rec(Btree *root, void (*visit)(Btree *));

然后是各个代码的具体实现，在Btree.c

void bt_printf(Btree *node);

Btree *bt_new_node(TREE_DATATYPE value)
{
    Btree *node = (Btree *)malloc(sizeof(Btree));
    if (!node)
    {
        perror("malloc failed");
        exit(1);
    }
    node->data = value;
    node->left_child = NULL;
    node->right_child = NULL;
    return node;
}

Btree *bt_new_node(TREE_DATATYPE value);

void bt_printf(Btree *node)
{
    if (node)
    {
        printf("%d ", node->data);
    }
}

Preorder

递归

void bt_pre_rec(Btree *node, void (*visit)(Btree *));

void bt_pre_rec(Btree *node, void(*visit)(Btree *))
{
    if (!node)
    {
        return;
    }
    visit(node); // Visit the current node
    bt_pre_rec(node->left_child, visit);
    bt_pre_rec(node->right_child, visit);
}

非递归

void bt_pre_nonrec(Btree *root, void (*visit)(Btree *));

void bt_pre_nonrec(Btree *root, void(*visit)(Btree *))
{

    // Standard Algorithm:
    // pop a node;
    // visit the node;
    // push its right child;
    // push its left child;
    if (!root)
        return;

    Btree *p = root;
    StaticStack stack;
    ss_init(&stack);
    ss_push(&stack, (DATATYPE)p); // Push the root node onto the stack

    while (!ss_is_empty(&stack))
    {
        DATATYPE value;
        ss_pop(&stack, &value);
        p = (Btree *)value; // Pop the top node from the stack

        if (!p)
            continue; // If the popped node is NULL, skip it

        // Process the current node
        visit(p);

        // Push right child first so that left child is processed first
        if (p->right_child)
        {
            ss_push(&stack, (DATATYPE)p->right_child);
        }
        if (p->left_child)
        {
            ss_push(&stack, (DATATYPE)p->left_child);
        }
    }
    // my poor attempt at a non-recursive preorder traversal
    // {
    //     visit the current node
    //     printf("%d ", p->data);

    //     if (p->right_child){
    //         ss_push(&stack, (DATATYPE) p->right_child);
    //     }

    //     if (p->left_child)
    //     {
    //         p = p->left_child;
    //     }
    //     else if (ss_is_empty(&stack))
    //     {
    //         break; // Exit if the stack is empty
    //     }
    //     else
    //     {
    //         DATATYPE value;
    //         ss_pop(&stack, &value);
    //         p = (Btree *) value;
    //     }

    // }
}

Inorder

递归

void bt_in_rec(Btree *root, void (*visit)(Btree *));

void bt_in_rec(Btree *root, void(*visit)(Btree *))
{
    if (!root)
    {
        return;
    }
    bt_in_rec(root->left_child, visit);
    visit(root); // Visit the current node
    bt_in_rec(root->right_child, visit);
}

非递归

`void bt_in_nonrec(Btree root, void (visit)(Btree *));`

void bt_in_nonrec(Btree *root,void(*visit)(Btree *))
{
    if (!root)
        return;
    StaticStack stack;
    ss_init(&stack);
    Btree *p = root;
    while (p || !ss_is_empty(&stack))
    {
        while (p)
        {
            ss_push(&stack, (DATATYPE)p);
            p = p->left_child;
        }
        DATATYPE value;
        ss_pop(&stack, &value);
        p = (Btree *)value; // Pop the top node from the stack
        visit(p);          // Visit the current node
        p = p->right_child; // Move to the right child
    }
}

Postorder

递归

void bt_post_rec(Btree *root, void (*visit)(Btree *));

void bt_post_rec(Btree *root, void(*visit)(Btree *))
{
    if (!root)
    {
        return;
    }
    bt_post_rec(root->left_child, visit);
    bt_post_rec(root->right_child, visit);
    visit(root);
}

非递归

void bt_post_rec(Btree *root, void (*visit)(Btree *));

void bt_post_nonrec(Btree *root, void(*visit)(Btree *))
{
    if (!root)
        return;
    StaticStack stack;
    ss_init(&stack);
    Btree *p = root;
    Btree *last_visit = NULL;
    while (p || !ss_is_empty(&stack))
    {
        while (p)
        {
            ss_push(&stack, (DATATYPE)p);
            p = p->left_child;
        }
        DATATYPE value;
        ss_top(&stack, &value);
        p = (Btree *)value; // Pop the top node from the stack
        if (!p)
            continue; // If the popped node is NULL, skip it

        if (!p->right_child || p->right_child == last_visit)
        {
            // If there is no right child or the right child has been visited
            ss_pop(&stack, &value);
            visit(p); // Visit the current node
            last_visit = p; // Update last visited node
            p = NULL;       // Set p to NULL to continue backtracking
        }
        else
        {
            p = p->right_child; // Move to the right child
        }
    }
}