C++打印完全二叉树

叁歲伎倆 2022-09-11 10:16 22阅读 0赞

思路：完全二叉树可以采用数组顺序存储，而且除最后一层外其余各层都是满的。则可以采用逆序打印的方式，先确定最底层的节点位置及数目，进而确定其上各层的节点位置。

### **打印效果** ###

**![20210915183718135.png][]**

### 代码实现 ###

#include<iostream>
    #include<stdlib.h>
    #include<string>
    #include<vector>
    #include<cmath>
    #include<time.h>
    #include<exception>
    
    
    using namespace std;
    
    //存储数值节点及树枝的初始位置以及判断是否为空节点
    typedef struct{
        int iniloc;
        bool place_hold = false;
    }treeNode;          
    
    //存储要打印的每一行字符、起始位置，以及其中存储节点和树枝的栈
    class prtTreeLine{
        public:
            string str;
            int iniLoc;
            vector<treeNode>tr;
            vector<treeNode>limb;
    };
    
    
    //处理最底层
    void process_Bottom(vector<prtTreeLine> &Bitree,int arr[],int len){
        int tree_height = floor(log2(len)+1);
        int first_node = (int)(pow(2,tree_height-1));
        int maxBasenode = (int)(pow(2,tree_height-1));                  //最底层最大元素个数(满的情况下)
        int base_node_sum = len-first_node+1>0?len-first_node+1:1;      //最底层元素个数(实际节点数)
        prtTreeLine pt;
        string str;
        int ini_loc=0;
        pt.iniLoc = ini_loc;
        for(int j=0;j<=maxBasenode;j++) //遍历最底层的节点
        {
            treeNode tn;
            tn.iniloc = ini_loc;
            string val_str;
            if(j<base_node_sum)       
                {
                    val_str = to_string(arr[j+first_node]) + "    ";
                    
                }
            else{
                val_str = string(6,' ');     //最底层不是满的,后续节点用6个空格作占位符
                tn.place_hold = true;
            }
            str +=  val_str ;
            ini_loc += val_str.size();
            pt.tr.push_back(tn);
        }
        pt.str = str;
        Bitree.push_back(pt);
    }
    
    //处理树枝层
    void processLimb(vector<prtTreeLine> &Bitree){
        prtTreeLine pt;
        prtTreeLine last_pt = Bitree.back();
        string str(last_pt.str.size(),' ');     //初始化一个字符串
        int iniloc = 0;
        pt.iniLoc =last_pt.iniLoc+1;
        iniloc = pt.iniLoc;
        for(int g=0;g<last_pt.tr.size();g++)
        {
            treeNode limb;
            if(last_pt.tr[g].place_hold==false)
            {
                if(g%2==0)  //对应左节点
                {
                iniloc =last_pt.tr[g].iniloc+1;     //左孩子头上的枝干位置应为其位置+1
                str.replace(iniloc,1,"/");
                
                }
                else{
                    iniloc =last_pt.tr[g].iniloc-1;
                    str.replace(iniloc,1,"\\");
                }
            }
            else{
                iniloc =last_pt.tr[g].iniloc+2;
                limb.place_hold = true;
            }
            
            limb.iniloc = iniloc;
            pt.limb.push_back(limb);
        }
        pt.str = str;
        Bitree.push_back(pt);
    }
    
    
    //处理其它节点层
    void process_others(vector<prtTreeLine> &Bitree,int arr[],int nodeLayer){
        prtTreeLine pt;
        prtTreeLine last_pt = Bitree.back();
        string str(last_pt.str.size(),' ');     //初始化一个字符串
        int iniloc = 0;
        pt.iniLoc =last_pt.iniLoc+1;
        iniloc = pt.iniLoc;
        int node =0;
        int iniNode = (int)(pow(2,nodeLayer-1));
        int node_sum = (int)(pow(2,nodeLayer))-(int)(pow(2,nodeLayer-1));     //完全二叉树除了最低层应该都是满的
    
        for(int q=0;q<last_pt.limb.size()&&node<node_sum;q+=2,node++)
        {
            treeNode tn;
            int mid;
            if(q+1<last_pt.limb.size())
            {
                mid =last_pt.limb[q].iniloc+ (last_pt.limb[q+1].iniloc-last_pt.limb[q].iniloc)/2;       //节点所在位置应为其左右枝干中间
                string val_str = to_string(arr[node+iniNode]);
                str.replace(mid,val_str.size(),val_str);
                if(last_pt.limb[q].place_hold==false)       //如果该节点有孩子节点
                    {
                        int frspace = mid-last_pt.limb[q].iniloc-1;
                        frspace = frspace>0?frspace:0;
                        int baspace = last_pt.limb[q+1].iniloc-mid-val_str.size();
                        baspace = baspace>0?baspace:0;
                        string front_str(frspace,'_');      //用下划线充填节点与左孩子树枝之间的空格
                        string back_str(baspace,'_');
                        if(frspace)
                            str.replace(last_pt.limb[q].iniloc+1,frspace,front_str);
                        if(last_pt.limb[q+1].place_hold ==false) //如果该节点有右孩子
                        {
                            if(baspace)
                            str.replace(mid+val_str.size(),baspace,back_str);
                        }
                    }
                iniloc =mid;
                tn.iniloc = iniloc;
                pt.tr.push_back(tn);
                
            }
        }
        pt.str = str;
        Bitree.push_back(pt);
        
    }
    
    
    //打印一颗完全二叉树
    void treePrint(int arr[],int len)
    {
        void process_Bottom(vector<prtTreeLine> &Bitree,int arr[],int len);
        void processLimb(vector<prtTreeLine> &Bitree);
        void process_others(vector<prtTreeLine> &Bitree,int arr[],int nodeLayer);
    
    
    
        vector<prtTreeLine>Bitree;
        int tree_height = floor(log2(len)+1);
        int layer = tree_height*2-2;
    
        process_Bottom(Bitree,arr,len);
    
        for(int nodeLayer=tree_height-1;layer>0;--layer)      //从最底层开始逆序打印
        {
            prtTreeLine last_pt = Bitree.back();
            if(last_pt.limb.size()!=0)
            {
                //上一行为树枝行，本行应打印节点行
                //其它层
                process_others(Bitree,arr,nodeLayer);
                nodeLayer--;        //nodeLayer为当前节点层号
            }
            else{
                //上一行为节点行，本行应打印树干行
                processLimb(Bitree);
            }
    
        }
    
        cout<<"***********打印一颗完全二叉树**************"<<endl;
        while(!Bitree.empty())
        {
            cout<<Bitree.back().str<<endl;
            Bitree.pop_back();
        }
        
    }
    
    
    //生成一个随机数组
    void getRandarray(int arr[],int len)
    {
        srand(time(NULL));
        cout<<"原始序列:";
        for(int i=1;i<=len; i++)     //完全二叉树从序号1开始排序
        {
            arr[i] = rand()%100+1;
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    
    }
       
    
    int main()
    {
        int len = 27;
        int *arr = new int[len+1];      //完全二叉树从序号1开始排序
        getRandarray(arr,len);
        try{
            treePrint(arr,len);
        }catch(exception &e){
        
            cerr<<e.what()<<endl;
        }
        return 0;
    }

[20210915183718135.png]: /images/20220828/cebe37cb453d4c8298b3374103d2eb71.png