c++用二叉树表示代数表达式_二叉树-删除指定结点的子树（C++）

淩亂°似流年 2023-01-04 13:14 160阅读 0赞

![bbe77c3bd9151e7db0abc31e923a199d.png][]

哈罗哈罗！叨叨Chen又来分享学习所得了。今天给大家分享的算法是如何在构建好的二叉树中删除用户指定的结点及以它为根的子树。注意要释放相应空间喔~

话不多说，beginning！

## Punchline------------------------------------------------------------------- ##

Task：根据输入的广义表形式，创建二叉树，再删除二叉树指定data值为x的结点，并删除以x为根结点的子树，递归实现，注意释放内存。

Input：输入两行，第一行为表示二叉树的广义表形式，第二行为待删除子树根结点的元素x。

Output：输出一行，为删除后的树的广义表达式。

Realize：

1.  创建二叉树（CreateBiTree）：这里根据输入二叉树的广义表形式，结合栈的思想实现二叉树的创建（非递归算法），创建的思路如下：

*  遇到data，则建立新的结点，将结点的值指向data，结点的左右指针为NULL；
 *  遇到 '(' ：将前一步建立的结点入栈，设置标记flag=1表示下一步可能会有左孩子；
 *  遇到 ','：设置flag=2表示下一步将会有右孩子；
 *  遇到 ')'：出栈，表示返回上一层，i.e.回到当前结点的父结点。

2.递归删除子树（DeleteTree）：递归实现，删除思路如下：

*  如果树为NULL（也表示当递归到叶结点的时候），则返回上一层；
 *  如果遇到data的值==x，则设置标记fl=1，会返回给上一层表示是x是在父结点的左孩子还是右孩子，进而删除以x为根结点的子树。

3.广义表输出删除后的二叉树（print）：递归实现。

## \------------------------------------------------------------------------------ ##

## Let's get it! ##

//加载头文件；这里设置的MaxInitSIze是为限制输入的广义表的长度。

#include<iostream>;
    #include<string>;
    #include<cstring>;
    using namespace std;
    #define MaxInitSize 30

//定义树结点，这里NodeTree便于结点指针的声明；

typedef struct Node
    {
         
        char data;
        Node *lc,*rc;
    }*NodeTree;

//主要功能

//创建二叉树
    Node *CreateBiTree(char *a,int len)
    {
         
        Node *temp,*root=NULL;
        Node *stack[MaxInitSize];
        int i,flag,top=-1;
        if(a[0]==' '){
         return root;}
        for(i=0;i<len;i++)
        {
         
            switch(a[i])
            {
         
                case '(':top++;stack[top]=temp;flag=1;break;
                case ',':flag=2;break;
                case ')':top--;break;
                default:
                    temp=(Node*)malloc(sizeof(Node));
                    temp->data=a[i];temp->lc=NULL;temp->rc=NULL;
                    if(root==NULL){
         root=temp;}
                    else
                    {
         
                        if(flag==1){
         stack[top]->lc=temp;}
                        else{
         stack[top]->rc=temp;}
                    }
                    break;
            }
        }
        return root;
    }
    //递归删除子树
    int DeleteTree(NodeTree &t,char e,int fl)
    {
         
        if(t==NULL){
         return 0;}
        else
        {
         
            if(t->data==e){
         fl=1;}
            int lf=DeleteTree(t->lc,e,fl);
            int rf=DeleteTree(t->rc,e,fl);
            if(fl==1)
            {
         
                if(t->data==e){
         t=NULL;return 1;}
                free(t);
            }
            else
            {
         
                if(lf==1){
         t->lc=NULL;}
                if(rf==1){
         t->rc=NULL;}
            }
            
        }
        return 0;
    }
    //输出二叉树广义表形式
    void print(Node*t)
    {
         
        if(t==NULL){
         return ;}
        cout<<t->data;
        if(t->lc){
         cout<<"(";print(t->lc);}
        if(!t->lc && t->rc){
         cout<<"(";}
        if(t->rc){
         cout<<",";print(t->rc);cout<<")";}
        if(t->lc &&!t->rc){
         cout<<")";}
        return ;
    }

//main函数

int main()
    {
         
        char elem[MaxInitSize];
        char subt;
        cin.getline(elem,MaxInitSize);
        cin>>subt;
        int len=strlen(elem);
        Node *root=CreateBiTree(elem,len);
        int fl=0;
        DeleteTree(root,subt,fl);
        print(root);
        return 0;
    }

这里的main函数设置为以上的形式，是为了满足用户输入的各类广义表形式。读者还可以在return 0前设置一个清除clear函数，将创建的二叉树清除掉，释放内存，在叨叨Chen的其他算法的文章会涉及。

关于这个算法，叨叨Chen今天先写在这里，欢迎读者提出批评和建议，叨叨Chen会采纳好的建议追加在此算法后面。

2020.10.08------------------------------------------------------------------It still comes---

--------------------

[bbe77c3bd9151e7db0abc31e923a199d.png]: /images/20221119/78a63318fb2d4d60a8c5138df56912f8.png