二叉树的基本操作（C语言）

梦里梦外; 2022-02-19 15:57 208阅读 0赞

**前提：**

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node
    { 
        char data;
        struct node *lson;
        struct node *rson;
    }NODE;

**一、建造二叉树**

1、已知二叉树的一个按先序遍历输入的字符序列，如abc,de,g,f, (其中,表示空结点)。

int i;		//在main函数中i要置零
    char a[100];
    
    NODE *creat()
    { 
        NODE *t;
        if(a[i]==',')
        { 
            i++;
            return NULL;
        }
        t=(NODE *)malloc(sizeof(NODE));
        t->data=a[i];
        i++;
        t->lson=creat();
        t->rson=creat();
        return t;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70]

2、已知二叉树的先序遍历序列和中序遍历序列

NODE *creat(char s1[],char s2[],int len)
    { 
        int i;
        NODE *t;
        if(len<=0)
        { 
            return NULL;
        }
        t=(NODE *)malloc(sizeof(NODE));
        t->data=s1[0];
        for(i=0;i<len;i++)
        { 
            if(s2[i]==s1[0])
            { 
                break;
            }
        }
        t->lson=creat(s1+1,s2,i);
        t->rson=creat(s1+i+1,s2+1+i,len-1-i);
        return t;
    }

3、已知一棵二叉树的中序遍历和后序遍历

NODE *creat(char s1[],char s2[],int len)
    { 
        NODE *t;
        int i;
        if(len<=0)
        { 
            return NULL;
        }
        t=(NODE *)malloc(sizeof(NODE));
        t->data=s2[len-1];
        for(i=0;i<len;i++)
        { 
            if(s1[i]==s2[len-1])
                break;
        }
        t->lson=creat(s1,s2,i);
        t->rson=creat(s1+i+1,s2+i,len-i-1);
        return t;
    }

**二、遍历二叉树**

1、前序遍历

void xian(NODE *t)
    { 
        if(t)
        { 
            printf("%c",t->data);
            xian(t->lson);
            xian(t->rson);
        }
    }

2、中序遍历

void mid(NODE *t)
    { 
        if(t)
        { 
            mid(t->lson);
            printf("%c",t->data);
            mid(t->rson);
        }
    }

3、后序遍历

void hou(NODE *t)
    { 
        if(t)
        { 
            hou(t->lson);
            hou(t->rson);
            printf("%c",t->data);
        }
    }

4、层序遍历

void show(struct node  *t)
    { 
        //队列思想；out相当于队列的头，in相当于队列的尾后面那一个；
        struct node *temp[55];//定义了55个结构体指针；用来指结点；
        temp[0]=t;
        int in=1,out=0;//因为一开始temp队列中只有一个t；所以in=1 out=0；
        while(out<in) //确保队列非空；
        { 
            if(temp[out])
            { 
                printf("%c",temp[out]->data);
                temp[in++]=temp[out]->lson; //把要输出的那个结点的左右儿子放进队列；
                temp[in++]=temp[out]->rson;
            }
            out++;//既然temp【out】已经输出了，让out++来删除输出的结点；
        }
    }

**三、求叶子数**

int yezi(NODE *t)
    { 
        int k;
        if(t==NULL)
        { 
            return 0;
        }
        else if(t->lson==NULL&&t->rson==NULL)
        { 
            return 1;
        }
        else
        { 
            k=yezi(t->lson)+yezi(t->rson);
            return k;
        }
    }

int count=0;
    void yezi(NODE *t)
    { 
        if(t)
        { 
            if(t->lson==NULL&&t->rson==NULL)
            { 
    			count++;
    		}
            yezi(t->lson);
            yezi(t->rson);
        }
    }

**四、求深度**

int deep(NODE *t)
    { 
        int d=0;
        if(t)
        { 
            d=max(deep(t->lson)+1,deep(t->rson)+1);
        }
        return d;
    }

int deep(NODE *t)
    { 
        if(t==NULL)
        	return 0;
        else
        { 
        	int l=deep(t->lson)+1;
        	int r=deep(t->rson)+1;
            int d=l>r?l:r;
            return d;
        }  
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70]: /images/20220219/9210f5337e304ec69b959d883b91a24f.png