C语言实现二叉树：数据结构实验报告

一、实验目的

掌握二叉树的基本概念和基本操作；
熟悉二叉树的遍历方式（前序遍历、中序遍历、后序遍历）；
了解二叉树的应用。

二、实验内容

二叉树的创建和销毁；
二叉树的遍历方式（前序遍历、中序遍历、后序遍历）；
二叉树的查找和插入操作；
二叉树的删除操作。

三、实验步骤

1. 二叉树的创建和销毁

二叉树的创建可以通过递归的方式来实现，具体代码如下：

typedef struct node{
    int data;
    struct node *left,*right;
}node;

node *create_tree(){
    int data;
    node *p;
    scanf('%d',&data);
    if(data==-1)
        p=NULL;
    else{
        p=(node*)malloc(sizeof(node));
        p->data=data;
        p->left=create_tree();
        p->right=create_tree();
    }
    return p;
}

二叉树的销毁也可以使用递归的方式来实现，具体代码如下：

void destroy_tree(node *p){
    if(p!=NULL){
        destroy_tree(p->left);
        destroy_tree(p->right);
        free(p);
    }
}

2. 二叉树的遍历方式

二叉树的遍历方式有三种：前序遍历、中序遍历、后序遍历，具体代码如下：

void pre_order(node *p){
    if(p!=NULL){
        printf('%d ',p->data);
        pre_order(p->left);
        pre_order(p->right);
    }
}

void in_order(node *p){
    if(p!=NULL){
        in_order(p->left);
        printf('%d ',p->data);
        in_order(p->right);
    }
}

void post_order(node *p){
    if(p!=NULL){
        post_order(p->left);
        post_order(p->right);
        printf('%d ',p->data);
    }
}

3. 二叉树的查找和插入操作

二叉树的查找和插入操作也可以使用递归的方式来实现，具体代码如下：

node *search(node *p,int data){
    if(p==NULL)
        return NULL;
    if(p->data==data)
        return p;
    else if(p->data>data)
        return search(p->left,data);
    else
        return search(p->right,data);
}

node *insert(node *p,int data){
    if(p==NULL){
        p=(node*)malloc(sizeof(node));
        p->data=data;
        p->left=NULL;
        p->right=NULL;
    }
    else if(p->data>data)
        p->left=insert(p->left,data);
    else
        p->right=insert(p->right,data);
    return p;
}

4. 二叉树的删除操作

二叉树的删除操作需要考虑多种情况，具体代码如下：

node *delete(node *p,int data){
    node *temp,*child;
    if(p==NULL)
        return NULL;
    if(p->data==data){
        if(p->left==NULL){
            temp=p->right;
            free(p);
            return temp;
        }
        else if(p->right==NULL){
            temp=p->left;
            free(p);
            return temp;
        }
        else{
            temp=p->right;
            child=p->right;
            while(child->left!=NULL)
                child=child->left;
            child->left=p->left;
            free(p);
            return temp;
        }
    }
    else if(p->data>data)
        p->left=delete(p->left,data);
    else
        p->right=delete(p->right,data);
    return p;
}

四、实验结果

通过本次实验，我掌握了二叉树的基本概念和基本操作，熟悉了二叉树的遍历方式，并且了解了二叉树的应用。在实际应用中，二叉树可以用来表示一些复杂的数据结构，例如文件系统，数据库等等。