使用C语言实现结点值为字母的完全二叉树的插入、3种遍历和删除操做和实验报告

实验目的：

1.掌握完全二叉树的插入、遍历和删除操作。

2.深入理解C语言中指针的概念和运用。

实验原理：

完全二叉树：一棵深度为k的，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称之为完全二叉树。

完全二叉树的性质：

1.除了最后一层，其他层节点数都是满的。

2.最后一层节点都是靠左排列的。

插入操作：

在完全二叉树中，新节点插入到最后一层的最右边。

1.如果树为空，则插入的节点为根节点。

2.如果树不为空：

a.找到最后一层的最右边节点。

b.插入新的节点。

c.如果插入后，该层节点数已满，则新开一层。

遍历操作：

1.前序遍历：先访问根节点，再依次遍历左子树和右子树。

2.中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。

3.后序遍历：先遍历左子树，再遍历右子树，最后访问根节点。

删除操作：

1.如果要删除的节点没有子节点，直接删除。

2.如果要删除的节点只有一个子节点，则将该子节点代替要删除的节点。

3.如果要删除的节点有两个子节点，则在其右子树中找到最小的节点，并将其代替要删除的节点。

实验步骤：

1.定义完全二叉树的节点结构体：

typedef struct TreeNode{
    char data;
    struct TreeNode *lchild; //左孩子
    struct TreeNode *rchild; //右孩子
}TreeNode, *Tree;

2.定义完全二叉树的插入函数：

void InsertNode(Tree *root, char data){
    TreeNode *new_node = (TreeNode*)malloc(sizeof(TreeNode));
    new_node->data = data;
    new_node->lchild = NULL;
    new_node->rchild = NULL;
    if((*root) == NULL){
        (*root) = new_node;
        return;
    }
    TreeNode *p = (*root);
    int count = 0;
    while(p->lchild != NULL){
        count++;
        if(count & 1){ //如果count为奇数，则向左子树查找
            p = p->lchild;
        }
        else{ //如果count为偶数，则向右子树查找
            p = p->rchild;
        }
    }
    if(count & 1){ //如果count为奇数，则新节点插入到左子树
        p->lchild = new_node;
    }
    else{ //如果count为偶数，则新节点插入到右子树
        p->rchild = new_node;
    }
}

3.定义完全二叉树的前序遍历函数：

void PreOrderTraversal(Tree root){
    if(root != NULL){
        printf("%c ", root->data);
        PreOrderTraversal(root->lchild);
        PreOrderTraversal(root->rchild);
    }
}

4.定义完全二叉树的中序遍历函数：

void InOrderTraversal(Tree root){
    if(root != NULL){
        InOrderTraversal(root->lchild);
        printf("%c ", root->data);
        InOrderTraversal(root->rchild);
    }
}

5.定义完全二叉树的后序遍历函数：

void PostOrderTraversal(Tree root){
    if(root != NULL){
        PostOrderTraversal(root->lchild);
        PostOrderTraversal(root->rchild);
        printf("%c ", root->data);
    }
}

6.定义完全二叉树的查找节点函数：

TreeNode* FindNode(Tree root, char data){
    if(root == NULL){
        return NULL;
    }
    if(root->data == data){
        return root;
    }
    TreeNode *p = FindNode(root->lchild, data);
    if(p != NULL){
        return p;
    }
    else{
        return FindNode(root->rchild, data);
    }
}

7.定义完全二叉树的删除节点函数：

void DeleteNode(Tree *root, char data){
    TreeNode *p = FindNode((*root), data);
    if(p == NULL){
        return;
    }
    if(p->lchild == NULL && p->rchild == NULL){ //要删除的节点没有子节点
        free(p);
        p = NULL;
        return;
    }
    if(p->lchild == NULL || p->rchild == NULL){ //要删除的节点只有一个子节点
        TreeNode *child = p->lchild ? p->lchild : p->rchild;
        p->data = child->data;
        p->lchild = child->lchild;
        p->rchild = child->rchild;
        free(child);
        child = NULL;
        return;
    }
    else{ //要删除的节点有两个子节点
        TreeNode *q = p->rchild;
        while(q->lchild != NULL){ //在右子树中找到最小的节点
            q = q->lchild;
        }
        p->data = q->data; //将最小的节点代替要删除的节点
        DeleteNode(&(p->rchild), q->data); //删除最小的节点
        return;
    }
}

实验报告：

本次实验实现了结点值为字母的完全二叉树的插入、3种遍历和删除操作，并且深入理解了C语言中指针的概念和运用。

在插入操作中，采用了层次遍历的方法，找到最后一层的最右边节点，然后插入新的节点。如果插入后，该层节点数已满，则新开一层。

在遍历操作中，分别实现了前序遍历、中序遍历和后序遍历三种方法。其中，前序遍历先访问根节点，再依次遍历左子树和右子树；中序遍历先遍历左子树，再访问根节点，最后遍历右子树；后序遍历先遍历左子树，再遍历右子树，最后访问根节点。

在删除操作中，分为三种情况：要删除的节点没有子节点、要删除的节点只有一个子节点和要删除的节点有两个子节点。对于第一种情况，直接删除节点；对于第二种情况，将子节点代替要删除的节点；对于第三种情况，在其右子树中找到最小的节点，并将其代替要删除的节点。

综上所述，本次实验使我更深入理解了完全二叉树的相关知识，同时也掌握了C语言中指针的概念和运用，提高了我的编程能力。