二叉树的基本操作（C++实现）

编译器是DevC++。可能有地方写得不够规范，大佬轻喷。

//链式存储的二叉树 
//先序建立方式
//遍历方式：先序，中序，后序，层次 
//计算：树的深度，叶子节点，节点数，度为1的节点数，度为2的节点数
//二叉树的复制，交换左右子树
//二叉树的查找，修改，删除，插入 


#include
#include
#include

using namespace std;

int n;

typedef struct Node{
    
    int data;
    Node *lchild,*rchild;
    
}LkNode,*BiTree;


void CreateBiTree(BiTree &T){
    
    int inputdata;
    cin>>inputdata;
    if(inputdata == -1){
        
        T = NULL;
        //return;
        
    }
    
    else{
        
        T = new LkNode();
        if(!T)
            cout<<"开辟空间失败！"<data = inputdata; //创建根节点
            CreateBiTree(T ->lchild);
            CreateBiTree(T ->rchild);
            
        }
        
    }
    
}


void PreOrederTraverse(BiTree T){ //递归实现先序遍历 
    
    if(T != NULL){
        
        cout<data<<" ";
        PreOrederTraverse(T ->lchild);
        PreOrederTraverse(T ->rchild);
        
    }
    else{
        
        //cout<<"二叉树为空！"<lchild);
        cout<data<<" ";
        MidOrederTraverse(T ->rchild);
         
    }
    else{
        
        //cout<<"二叉树为空！"<lchild);
        LastOrederTraverse(T ->rchild);
        cout<data<<" ";
         
    }
    else{
        
        //cout<<"二叉树为空！"< que;
    if(T != NULL){
        
        while(T){

            cout << T->data << " ";

            if(T->lchild)
                que.push(T->lchild);
            if(T->rchild)
                que.push(T->rchild);
            if(que.empty())
                break;

            T = que.front(); //将队列首元素赋予T， 
            que.pop();

        }
        
    }
    else{
        
        //cout<<"二叉树为空！"<lchild);
        depr = DepthBiTree(T ->rchild);
        dep = 1 + (depl > depr ? depl : depr);
        return dep;
            
    }
    
}


int NodeCount(BiTree T){ //计算节点数 
    
    int nodecount = 0;
    if(!T)
        return 0;
    else{
        
        //return NodeCount(T ->lchild) +NodeCount(T ->rchild) + 1;
        nodecount++;
        
        nodecount += NodeCount(T ->lchild);
        nodecount += NodeCount(T ->rchild);
        
    }
    return nodecount;
        
}


int LeafCount(BiTree T){ //计算叶子节点数 
    
    int leafcount = 0;
    if(!T)
        return 0;
    else{
        
        if( (!T ->lchild) && (!T ->rchild) ) //左右子树均为空，则为叶子节点 
            //leafcount++; //两种写法都可以 
            leafcount = 1;
        
        leafcount += LeafCount(T ->lchild);
        leafcount += LeafCount(T ->rchild);
            
    }
    return leafcount;
    
}
    

int SinglePointCount(BiTree T){ //计算度为1的节点数
    
    int sgcount = 0;
    if(!T)
        return 0;
    else{
        
        if( T ->lchild && T ->rchild ){ //左右节点都不为空，则分别计算左右子树度为1的节点个数 
            
            sgcount += SinglePointCount(T ->lchild);
            sgcount += SinglePointCount(T ->rchild);
            
        }
        if( T ->lchild && (!T ->rchild) ){ //左节点不为空，计算左子树度为1的节点个数 
            
            sgcount++;
            sgcount += SinglePointCount(T ->lchild);
            
        }
        if( (!T ->lchild) && T ->rchild ){ //右节点不为空，计算右子树度为1的节点个数 
            
            sgcount++;
            sgcount += SinglePointCount(T ->rchild);
            
        }
        
    }
    return sgcount;
        
}


int DoublePointCount(BiTree T){ //计算度为2的节点数 
    
    int dbcount = 0;
    if(!T)
        return 0;
    else{
        
        if( T ->lchild && T ->rchild ) //左右子树均不为空，则度为2
            dbcount++;
        
        dbcount += DoublePointCount(T ->lchild);
        dbcount += DoublePointCount(T ->rchild);
        
    }
    return dbcount;
    
}
        

void SwapBiTree(BiTree &T){ //交换左右子树所有节点 
    
    BiTree tem = new LkNode();
    if(T){
        
        tem = T ->rchild;
        T ->rchild = T ->lchild;
        T ->lchild = tem;
        
        SwapBiTree(T ->lchild);
        SwapBiTree(T ->rchild);
        
    }
    else return;
    
}


void CopyBiTree(BiTree T,BiTree &T2){ //复制二叉树 
    
    T2 = new LkNode();
    if(T){
        
        T2 ->data = T ->data;
        CopyBiTree(T ->lchild,T2 ->lchild);
        CopyBiTree(T ->rchild,T2 ->rchild);
        
    }
    else{
        
        T2 = NULL;
        return;
        
    }
    
}


bool SearchNode(BiTree T,int search){ //查找节点 
    
    if(T){
        
        if(T ->data == search){
            
            cout<<"节点"<lchild && T ->rchild){
                
                cout<<"且节点"<lchild ->data;
                cout<<"，右孩子为"<rchild ->data<<"。"<lchild && (!T ->rchild)){
                
                cout<<"且节点"<lchild ->data;
                cout<<"，右孩子为空。"<lchild) && T ->rchild){
                
                cout<<"且节点"<rchild ->data<<"。"<lchild,search);
            if(flag)
            {}
            else
                SearchNode(T ->rchild,search);
            
        }
        
    }
    else
        return false;
    
}


void GetParent(BiTree T,int search){ //查找父节点 
    
    if(T ->lchild){
        
        if(T ->lchild ->data == search){
            
            cout<<"节点"<data<<"的左孩子。"<lchild,search);
            
    }
    if(T ->rchild){
        
        if(T ->rchild ->data == search){
            
            cout<<"节点"<data<<"的右孩子。"<rchild,search);
            
    }
    if( (!T ->lchild) && (!T ->rchild) )
        return;
        
}


bool UpdateNode(BiTree &T,int update){ //修改节点 
    
    if(T){
        
        if(T ->data == update){
            
            int update2;
            cout<<"节点"<>update2;
            
            T ->data = update2;
            return true; 
            
        }
        else{
            
            bool flag = UpdateNode(T ->lchild,update);
            if(flag)
            {}
            else
                UpdateNode(T ->rchild,update);
            
        }
        
    }
    else
        return false;
    
}


bool DeleteNode(BiTree &T,int dlt){ //删除节点
    
    if(T){
        
        if(T ->data == dlt){
            
            if(T ->lchild && T ->rchild){ //用左孩子替代原节点，右孩子变成左孩子的左孩子 
                
                BiTree tem = T ->rchild;
                T = T ->lchild; //可以写个if，左右节点谁大谁替代原节点 
                T ->lchild = tem;
                T ->rchild = NULL;
                
            }
            else if(T ->lchild && (!T ->rchild)){ //用左孩子替代原节点 
                
                T = T ->lchild;
                
            }
            else if((!T ->lchild) && T ->rchild){ //用右孩子替代原节点 
                
                T = T ->rchild;
                
            }
            else
                T = NULL;
            
            //T = NULL; //连同左右孩子一起删除 
            return true; 
            
        }
        else{
            
            bool flag = DeleteNode(T ->lchild,dlt);
            if(flag)
            {}
            else
                DeleteNode(T ->rchild,dlt);
            
        }
        
    }
    else
        return false;
    
}


bool InsertNode(BiTree &T,int istparent){ //删除节点
    
    if(T){
        
        if(T ->data == istparent){
            
            int istdata;
            if(T ->lchild && T ->rchild){ //选择插入为原节点的左孩子或右孩子 
                
                cout<<"父节点左右孩子均存在，输入0代表插入为左孩子，输入1代表插入为右孩子。";
                cout<>lr;
                
                if(lr == 0){
                    
                    cout<<"请输入要插入的数据：";
                    cin>>istdata;
                    BiTree tem = new LkNode(); //开辟新空间
                     
                    tem ->data = istdata;
                    tem ->lchild = T ->lchild; //插入后原节点的左孩子，变成现节点的左孩子
                    tem ->rchild = NULL;
                    T ->lchild = tem;
                    
                }
                else if(lr == 1){
                
                    cout<<"请输入要插入的数据：";
                    cin>>istdata;
                    BiTree tem = new LkNode();
                     
                    tem ->data = istdata;
                    tem ->rchild = T ->rchild; //插入后原节点的右孩子，变成现节点的右孩子
                    tem ->lchild = NULL;
                    T ->rchild = tem;
                    
                }
                else
                    cout<<"插入为空。"<lchild && (!T ->rchild)){ //插入为原节点的右孩子 
                
                cout<<"父节点左孩子存在，右孩子为空，默认插入为右孩子，请输入要插入的数据：";
                cin>>istdata;
                BiTree tem = new LkNode();
            
                tem ->data = istdata;
                T ->rchild = tem; 
                
            }
            else if((!T ->lchild) && T ->rchild){ //插入为原节点的左孩子 
                
                cout<<"父节点左孩子为空，右孩子存在，默认插入为左孩子，请输入要插入的数据：";
                cin>>istdata;
                BiTree tem = new LkNode();
            
                tem ->data = istdata;
                T ->lchild = tem;
                
            }
            else{
                
                cout<<"父节点左右孩子均不存在，默认插入为左孩子，请输入要插入的数据：";
                cin>>istdata;
                
                BiTree istl = new LkNode();
                istl ->data = istdata;
                //istl ->lchild = NULL;
                //istl ->rchild = NULL;
                T ->lchild = istl;
                
            }
            
            return true; 
            
        }
        else{
            
            bool flag = InsertNode(T ->lchild,istparent);
            if(flag)
            {}
            else
                InsertNode(T ->rchild,istparent);
            
        }
        
    }
    else
        return false;
    
}


int main(){
    
    while(1){
        
        BiTree tree = NULL; //创建从根节点开始的二叉树
         
        cout<<"请输入二叉树tree的节点：";
        CreateBiTree(tree);
        cout<<"二叉树tree创建成功！"<>srh;
        if(SearchNode(tree,srh)){
        
            if(tree ->data == srh)
                cout<<"节点"<>upt;
        if(UpdateNode(tree,upt)){
        
            cout<<"修改成功！修改后tree层次遍历的顺序为：";
            LevelTraverse(tree); 
            cout<>dlt;
        if(DeleteNode(tree,dlt)){
        
            cout<<"删除成功！删除后tree层次遍历的顺序为：";
            LevelTraverse(tree); 
            cout<>istparent;
        if(InsertNode(tree,istparent)){
        
            cout<<"插入成功！插入后tree层次遍历的顺序为：";
            LevelTraverse(tree); 
            cout<