C二叉树创建与遍历

491 views

C二叉树创建与遍历

image-20231216152139390

btree.h

#define ElemType int

struct Node {
    ElemType data;
    struct Node *left;
    struct Node *right;
};

struct Node *new_node(ElemType data);

struct Node *insert_node(struct Node *b, ElemType data);

void pre_order(struct Node *b);

void in_order(struct Node *b);

void post_order(struct Node *b);

btree.c

#include <stdio.h>
#include <malloc.h>
#include "../include/btree.h"

// 创建二叉树
struct Node *new_node(ElemType data)
{
    struct Node *b = (struct Node *)malloc(sizeof(struct Node));
    b->data = data;
    b->left = NULL;
    b->right = NULL;
    return b;
}

// 插入节点
struct Node *insert_node(struct Node *b, ElemType data)
{
    if (b == NULL)
    {
        return new_node(data);
    }
    else if (data <= b->data)
    {
        b->left = insert_node(b->left, data);
    }
    else
    {
        b->right = insert_node(b->right, data);
    }
    return b;
}

// 先序遍历 根左右
void pre_order(struct Node *b)
{
    if (b != NULL)
    {
        printf("%d", b->data);
        pre_order(b->left);
        pre_order(b->right);
    }
}

// 中序遍历 左根右
void in_order(struct Node *b)
{
    if (b != NULL)
    {
        in_order(b->left);
        printf("%d", b->data);
        in_order(b->right);
    }
}

// 后序遍历 左右根
void post_order(struct Node *b)
{
    if (b != NULL)
    {
        post_order(b->left);
        post_order(b->right);
        printf("%d", b->data);
    }
}

main.c

#include <stdio.h>
#include "../include/btree.h"

int main()
{
    struct Node *root = NULL;
    root = insert_node(root, 3);
    insert_node(root, 2);
    insert_node(root, 5);
    insert_node(root, 1);
    insert_node(root, 4);
    insert_node(root, 6);
    pre_order(root);
    printf("\n");
    in_order(root);
    printf("\n");
    post_order(root);
    printf("\n");
    return 0;
}