C++的 二叉树算法代码

以下是一个简单的 C 二叉树的例子，包括二叉树的创建、插入、删除、遍历等操作。

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

// 二叉树结点
typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

// 创建二叉树
Node* create_tree(int data) {
    Node *root = (Node*)malloc(sizeof(Node));
    root->data = data;
    root->left = NULL;
    root->right = NULL;
    return root;
}

// 插入结点
void insert_node(Node *root, int data) {
    if (data < root->data) {
        if (root->left == NULL) {
            Node *new_node = (Node*)malloc(sizeof(Node));
            new_node->data = data;
            new_node->left = NULL;
            new_node->right = NULL;
            root->left = new_node;
        } else {
            insert_node(root->left, data);
        }
    } else {
        if (root->right == NULL) {
            Node *new_node = (Node*)malloc(sizeof(Node));
            new_node->data = data;
            new_node->left = NULL;
            new_node->right = NULL;
            root->right = new_node;
        } else {
            insert_node(root->right, data);
        }
    }
}

// 删除结点
Node* delete_node(Node *root, int data) {
    if (root == NULL) {
        return NULL;
    }
    if (data < root->data) {
        root->left = delete_node(root->left, data);
    } else if (data > root->data) {
        root->right = delete_node(root->right, data);
    } else {
        if (root->left == NULL) {
            Node *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node *temp = root->left;
            free(root);
            return temp;
        }
        Node *temp = root->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        root->data = temp->data;
        root->right = delete_node(root->right, temp->data);
    }
    return root;
}

// 前序遍历
void pre_order(Node *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        pre_order(root->left);
        pre_order(root->right);
    }
}

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

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

int main() {
    Node *root = create_tree(5);
    insert_node(root, 3);
    insert_node(root, 7);
    insert_node(root, 2);
    insert_node(root, 4);
    insert_node(root, 6);
    insert_node(root, 8);
    
    printf("pre_order: ");
    pre_order(root);
    printf("\n");
    printf("in_order: ");
    in_order(root);
    printf("\n");
    printf("post_order: ");
    post_order(root);
    printf("\n");
    
    root = delete_node(root, 5);
    
    printf("pre_order: ");
    pre_order(root);
    printf("\n");
    printf("in_order: ");
    in_order(root);
    printf("\n");
    printf("post_order: ");
    post_order(root);
    printf("\n");
    
    return 0;
}

这个例子实现了二叉树的创建、插入、删除和遍历操作。其中，创建二叉树的函数 `create_tree` 接受一个整数作为参数，返回一个根结点为该整数的二叉树。插入结点的函数 `insert_node` 接受一个根结点和一个整数作为参数，将该整数插入到二叉树中。删除结点的函数 `delete_node` 接受一个根结点和一个整数作为参数，删除二叉树中的该整数结点。遍历操作包括前序遍历、中序遍历和后序遍历，分别使用递归方式实现。最后，演示了删除结点后的遍历结果，以验证删除操作的正确性。