用C语言以链表的形式编写满二叉树及其相关增加、删除、修改、查找操作

由于满二叉树特点是每个节点都有两个子节点，因此我们可以按照层次遍历的方式将节点存储在链表中，每个节点的两个子节点的索引可以通过计算索引和深度来得到。

下面给出完整的代码实现：

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

// 定义树节点结构体
typedef struct TreeNode {
    int value;  // 数据域
    struct TreeNode *left;  // 左子节点
    struct TreeNode *right;  // 右子节点
} TreeNode;

// 初始化树节点
TreeNode *newTreeNode(int value, TreeNode *left, TreeNode *right) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    if (node == NULL) {
        printf("Error: Unable to allocate memory for new tree node.\n");
        exit(1);
    }
    node->value = value;
    node->left = left;
    node->right = right;
    return node;
}

// 获取二叉树的深度
int getDepth(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = getDepth(root->left);
    int rightDepth = getDepth(root->right);
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

// 获取满二叉树的节点个数
int getNodeCount(int depth) {
    int count = 1;
    while (--depth > 0) {
        count = count * 2 + 1;
    }
    return count;
}

// 获取满二叉树指定节点的索引
int getNodeIndex(int depth, int position) {
    return getNodeCount(depth - 1) + position;
}

// 获取满二叉树指定索引的节点值
int getNodeValue(int index) {
    return index;
}

// 获取满二叉树指定节点的左子节点
TreeNode *getLeftChild(int depth, int position) {
    int leftIndex = getNodeIndex(depth + 1, position * 2);
    if (leftIndex > getNodeCount(depth)) {
        return NULL;
    }
    int value = getNodeValue(leftIndex);
    return newTreeNode(value, NULL, NULL);
}

// 获取满二叉树指定节点的右子节点
TreeNode *getRightChild(int depth, int position) {
    int rightIndex = getNodeIndex(depth + 1, position * 2 + 1);
    if (rightIndex > getNodeCount(depth)) {
        return NULL;
    }
    int value = getNodeValue(rightIndex);
    return newTreeNode(value, NULL, NULL);
}

// 递归方式创建满二叉树
TreeNode *createFullBinaryTree(int depth, int position) {
    if (depth <= 0) {
        return NULL;
    }
    int value = getNodeValue(getNodeIndex(depth, position));
    TreeNode *left = getLeftChild(depth, position);
    TreeNode *right = getRightChild(depth, position);
    return newTreeNode(value, createFullBinaryTree(depth - 1, position * 2), createFullBinaryTree(depth - 1, position * 2 + 1));
}

// 按层次遍历方式打印二叉树
void printBinaryTree(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    TreeNode *queue[1024];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode *node = queue[front++];
        printf("%d ", node->value);
        if (node->left != NULL) {
            queue[rear++] = node->left;
        }
        if (node->right != NULL) {
            queue[rear++] = node->right;
        }
    }
    printf("\n");
}

// 根据指定的值查找节点
TreeNode *findNode(TreeNode *root, int value) {
    if (root == NULL) {
        return NULL;
    }
    if (root->value == value) {
        return root;
    }
    TreeNode *left = findNode(root->left, value);
    if (left != NULL) {
        return left;
    }
    TreeNode *right = findNode(root->right, value);
    if (right != NULL) {
        return right;
    }
    return NULL;
}

// 增加指定的子节点
void addChild(TreeNode *parent, int leftValue, int rightValue) {
    if (parent == NULL) {
        printf("Error: Parent node does not exist.\n");
        return;
    }
    if (parent->left != NULL || parent->right != NULL) {
        printf("Error: Parent node already has child nodes.\n");
        return;
    }
    if (leftValue >= 0) {
        TreeNode *left = newTreeNode(leftValue, NULL, NULL);
        parent->left = left;
    }
    if (rightValue >= 0) {
        TreeNode *right = newTreeNode(rightValue, NULL, NULL);
        parent->right = right;
    }
}

// 删除指定节点
void deleteNode(TreeNode *root, int value) {
    if (root == NULL) {
        printf("Error: Node does not exist.\n");
        return;
    }
    if (root->value == value) {
        root->value = -1;
        root->left = NULL;
        root->right = NULL;
        return;
    }
    if (root->left != NULL && root->left->value == value) {
        deleteNode(root->left, value);
    }
    if (root->right != NULL && root->right->value == value) {
        deleteNode(root->right, value);
    }
}

int main() {
    int depth = 4;  // 二叉树深度
    TreeNode *root = createFullBinaryTree(depth, 1);
    printf("Binary Tree created successfully!\n");
    printBinaryTree(root);

    int nodeValue = 6;  // 查找指定节点的值
    TreeNode *node = findNode(root, nodeValue);
    printf("Found node with value %d: %p\n", nodeValue, node);

    int parentValue = 3;  // 指定父节点的值
    TreeNode *parent = findNode(root, parentValue);
    addChild(parent, -1, -1);  // 增加子节点

    int deleteValue = 1;  // 删除节点的值
    deleteNode(root, deleteValue);

    printBinaryTree(root);

    return 0;
}