树的镜像

c++代码

#include<iostream>

using namespace std;

typedef struct BTN* BT;
struct BTN{
    int d;
    BT lc;
    BT rc;
};

BT initBT(int d){
    BT bt = new BTN;
    bt->d = d;
    bt->lc = NULL;
    bt->rc = NULL;
    return bt;
}

void insertBT(int d, BT bt, char c){
    BT t = initBT(d);
    switch(c){
        case 'l':
        bt->lc = t;
        break;
        case 'r':
        bt->rc = t;
    }
}

void deleteBT(BT bt){
    if(bt){ 
        BT t = bt;
        deleteBT(bt->lc);
        deleteBT(bt->rc);
        delete t;
    }
}

void changeBTc(BT bt){
    if(bt){
        BT t = bt->lc;
        bt->lc = bt->rc;
        bt->rc = t;
        changeBTc(bt->lc);
        changeBTc(bt->rc);  
    }
}

void printBT(BT bt){
    if(bt){ 
        printBT(bt->lc);
        cout<<bt->d<<" ";
        printBT(bt->rc);
    }
}

void levelTransBT(BT bt, int &n){
    int MAXQ = 50;
    BT queue[MAXQ];
    
    for(int i = 0; i < MAXQ; i++)
        queue[i] = NULL;

    int f = 0;
    int r = 0;
    
    queue[r++] = bt;
    
    int flag = 1;
    int temp = 1;
    n = temp;
    
    while(queue[f]){
        flag--;
        if(!flag){
            flag = temp;
            temp = 0;
        }

        BT t = queue[f++];
        cout<<t->d<<" ";
        if(t->lc){
            queue[r++] = t->lc;
            temp++;
        }
        if(t->rc){
            queue[r++] = t->rc;
            temp++;
        }

        if(temp > n)
            n = temp;
    }
}

BT init(){
    BT bt = initBT(15);
    insertBT(7, bt, 'l');
    insertBT(18, bt, 'r');

    BT l = bt->lc;
    insertBT(5, l, 'l');
    insertBT(8, l, 'r');
    BT r = bt->rc;
    insertBT(26, r, 'l');
    insertBT(1, r, 'r');
    
    BT t = l;
    l = l->lc;
    insertBT(10, l, 'l');
    insertBT(26, l, 'r');
    l = l->lc;  
    insertBT(9, l, 'l');
    insertBT(14, l, 'r');
    insertBT(6, t->lc->rc, 'l');
    
    l = t->rc;
    insertBT(2, l, 'l');
    insertBT(19, l, 'r');
    insertBT(28, l->lc, 'r');
    insertBT(3, l->rc, 'l');
    
    t = r;
    r = r->lc;
    insertBT(8, r, 'r');
    insertBT(18, r->rc, 'l');
    r = t->rc;
    insertBT(6, r, 'r');
    r = r->rc;
    insertBT(14, r, 'l');
    insertBT(27, r, 'r');
    
    return bt;
}

int main(){
    BT bt = init();
    printBT(bt);
    
    changeBTc(bt);
    cout<<"\nchird changed:\n";
    printBT(bt);
    
    changeBTc(bt);
    int n = 0;
    cout<<"\nlevel trans:\n"; 
    levelTransBT(bt, n);
    cout<<"\nthe width:\n"<<n;
    return 0;
}

有任何问题请回复提出。然后欢迎关注微信公众号格物致愚：