编辑代码

#include <stdio.h>
#include "windows.h"

//线索化二叉树是一种对二叉树的空指针域进行利用的方法，目的是为了加快查找二叉树中某节点的前驱和后继的速度¹²。
// 线索化二叉树可以按照不同的遍历顺序进行线索化，如先序，中序，后序等³。
// 线索化二叉树的节点结构中除了数据域和左右孩子指针外，还有两个标识域，
// 用来区分左右指针是指向孩子节点还是指向前驱或后继节点⁴。
typedef int E;

// 查找二叉树
struct TreeNode {
    E element;
    struct TreeNode *left;
    struct TreeNode *right;
};

typedef struct TreeNode *Node;

// 创建节点
Node createNode(E element) {
    Node node = malloc(sizeof(struct TreeNode));
    if (node == NULL) return NULL;
    node->left = node->right = NULL;
    node->element = element;
    return node;
}

void preOrder(Node root) {
    if (root == NULL) return;
    preOrder(root->left);
    printf("%d ", root->element);
    preOrder(root->right);
}

// 循环实现
void insert(Node root, E element) {
    while (root) {
        if (root->element == element) return;
        // 小于 左边
        if (root->element > element) {
            if (root->left)
                root = root->left;
            else {
                Node node = createNode(element);
                root->left = node;
                return;
            }
        } else {          // 大于右边
            if (root->right)
                root = root->right;
            else {
                Node node = createNode(element);
                root->right = node;
                return;
            }
        }
    }
}

// 递归实现 插入操作
Node insert2(Node root, E element) {
    if (root == NULL) return createNode(element);
    if (root->element > element) {
            root->left = insert2(root->left, element);
    } else if (root->element < element) {
            root->right = insert2(root->right, element);
    }
    return root;
}

int find(Node root, E target) {
    if (root == NULL) return -1;
    if (root->element == target) return root->element;
    if (root->element > target)
        find(root->left, target);
    else find(root->right, target);
}

Node findMax(Node root) {
    if (root->right == NULL) return root;
    findMax(root->right);
}

// 二叉查找树 删除方法
Node delete(Node root, E target) {
    if (root == NULL) return NULL;

    if (root->element > target)
        root->left = delete(root->left, target);
    else if (root->element < target)
        root->right = delete(root->right, target);
    else {
            if (root->right && root->left) {
                Node Max = findMax(root->left);
                root->element = Max->element;
                root->left = delete(root->left, root->element);
            } else {
                Node tmp = root;
                if (root->right)
                    root = root->right;
                else
                    root = root->left;

                free(tmp);
            }
        }
    return root;
}

int main() {
    Node root = insert2(NULL, 18);
    insert2(root, 10);
    insert2(root, 20);
    insert2(root, 7);
    insert2(root, 5);
    insert2(root, 22);
    insert2(root, 9);
    preOrder(root);
    printf("\n");

    delete(root, 9);

    preOrder(root);
}