编辑代码

#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) {
        if (root->left) insert2(root->left, element);
        else
            root->left = insert2(root->left, element);
    } else if (root->element < element) {
        if (root->right)
            insert2(root->right, element);
        else
            root->right = insert2(root->right, element);
    }
}

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);
}

int delete(Node root, E element) {
    if (root == NULL) return -1;
    Node tmp;
    if (root->element == element) {
        // 要删除节点为两种的情况
        if (root->right && root->left) {
            tmp = findMax(root->left);
            root->element = tmp->element;
            if (tmp->left) {
                tmp->element = tmp->left->element;
                tmp->left = tmp->left->left;
                free(tmp->left);
            } else free(tmp);
        } else if (root->right || root->left) {       // 删除一种节点的情况
            if (root->right) tmp = root->right;
            else tmp = root->left;
            root->element = tmp->element;
            root->right = tmp->right;
            root->left = tmp->left;
        }
    } else {
        free(root);
    }
    if (root->element > element)
        delete(root->left, element);
    else
        delete(root->right, element);
}

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("%d ", find(root, 17));
    printf("%d", find(root, 9));