7-1 树的遍历 (25 分)

秒速五厘米 2023-10-04 15:28 41阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyODE2MQ_size_16_color_FFFFFF_t_70]  
欲哭无泪，我可能选择了最难走的一条路，我突发奇想，使用二维坐标的形式在电脑中描绘一棵树，使用结构体数组，结构体是\{结点，x，y\}，摸索了很长时间，写是写出来了，但是忒麻烦了，光是处理后序、前序整理成我想要的树就写了150行代码，要了老命了，最后所有样例也只通过了一半，哭死，就先这样吧。

#include <stdio.h>
    #include <math.h>
    
    #define peerless -1000
    
    int pot=0;
    
    
    typedef struct Tree
    {
        
        int x;
        int y;
        int node;
    };
    
    struct Tree tree[36];
    
    void deal_tree(struct Tree *tree,int *pos_array,int *mid_array,int N);
    void find_root(int root_pot,int num,struct Tree *tree,int N,int *pos_array,int root_loc,int *mid_array,int i,int j,int left,int right,int level);
    void print_seq_tree(struct Tree *tree,int N);
    
    int main()
    {
        
        int N;
        int pos_array[36]={
        0};//后续遍历
        int mid_array[36]={
        0};//中序遍历
        int i = 0 ;
    
        scanf("%d",&N);
        while(i<N)
        {
        
            scanf("%d",&pos_array[i]);
            i++;
        }
        i=0;
        while(i<N)
        {
        
            scanf("%d",&mid_array[i]);
            i++;
        }
    
        deal_tree(tree,pos_array,mid_array,N);
    
        print_seq_tree(tree,N);
        return 0;
    }
    
    
    void print_seq_tree(struct Tree *tree,int N)
    {
        
        int i=0,j=0;
        int x=0,y=0,node=0;
        while(i<N)
        {
        
            j=i+1;
            while(j<N)
            {
        
                if(tree[i].y<tree[j].y)
                {
        
                    x=tree[i].x;
                    y=tree[i].y;
                    node=tree[i].node;
    
                    tree[i].x=tree[j].x;
                    tree[i].y=tree[j].y;
                    tree[i].node=tree[j].node;
    
                    tree[j].x=x;
                    tree[j].y=y;
                    tree[j].node=node;
    
                }
                j++;
            }
            i++;
        }
    
        i=0;
        j=0;
        while(i<N)
        {
        
            j=i+1;
            while(j<N)
            {
        
                if(tree[i].y==tree[j].y && tree[i].x>tree[j].x)
                {
        
                    x=tree[i].x;
                    y=tree[i].y;
                    node=tree[i].node;
    
                    tree[i].x=tree[j].x;
                    tree[i].y=tree[j].y;
                    tree[i].node=tree[j].node;
    
                    tree[j].x=x;
                    tree[j].y=y;
                    tree[j].node=node;
    
                }
                j++;
            }
            i++;
        }
    
        i=0;
        while(i<N)
        {
        
            if(i==N-1)
            {
        
                printf("%d\n",tree[i].node);
                break;
            }
            printf("%d ",tree[i].node);
            i++;
        }
    }
    
    void deal_tree(struct Tree *tree,int *pos_array,int *mid_array,int N)
    {
        
        int i=0,j=0;
        j=N-1;
        find_root(0,N,tree,N,pos_array,N-1,mid_array,i,j,0,0,0);
        //mid_array[i]即根
    }
    
    //使用(x,y)二维平面坐标的方式存储结点相对位置，root是(0,0)其左子树根(-1,-1)，其右子树根(1,-1)
    //(当前根的tree地址，当前检测的字串的个数，保存树的结构体数组，后序遍历序列，后序遍历序列中的根地址，中序遍历序列，中序遍历序列中待检测字串的起点，~终点，要检测的是左子树，要检测的是右子树，当前深度)
    void find_root(int root_pot,int num,struct Tree *tree,int N,int *pos_array,int root_loc,int *mid_array,int i,int j,int left,int right,int level)
    {
        
        int u=0;
        if(left==1)
        {
        
            u=i;
            //找根
            while(i<=j)
            {
        
                if(pos_array[root_loc]==mid_array[i])
                {
        
                    break;
                }
                i++;
            }
            //存储该根结点
            tree[pot].node=mid_array[i];
            tree[pot].x=tree[root_pot].x-1;
            tree[pot].y=level;
            root_pot=pot;
            pot++;
            level--;
            if(num==1)//若只有num=1说明这是最后一个结点了，该结束了
            {
        
                u++;
            }
            else if(i==u)//检测到中序序列中的根地址刚好是检测字串的起点，说明该根结点只有右子树，则检测右子树
            {
        
                root_loc=j-1;
                num=j-u;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,u+1,j,0,1,level);
            }
            else if(i==j)//检测到中序序列中的根地址刚好是检测字串的终点，说明该根结点只有左子树，则检测左子树
            {
        
                root_loc=j-1;
                num=j-u;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,u,j-1,1,0,level);
            }
            else//否则该根左右都有则进行两次检测
            {
        
                //先左
                root_loc=i-1;
                num=i-u;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,u,i-1,1,0,level);
                //后右
                root_loc=j-1;
                num=j-i;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,i+1,j,0,1,level);
            }
    
        }
        else if(right==1)
        {
        
            u=i;
            while(i<=j)
            {
        
                if(pos_array[root_loc]==mid_array[i])
                {
        
                    break;
                }
                i++;
            }
            tree[pot].node=mid_array[i];
            tree[pot].x=tree[root_pot].x+1;
            tree[pot].y=level;
            root_pot=pot;
            pot++;
            level--;
            if(num==1)
            {
        
                u++;
            }
            else if(i==u)
            {
        
                root_loc=j-1;
                num=j-u;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,u+1,j,0,1,level);
            }
            else if(i==j)
            {
        
                //因为后序与中序存在错位问题，所以有的-1有的-2
                root_loc=j-2;
                num=j-u;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,u,j-1,1,0,level);
            }
            else
            {
        
                root_loc=i-2;
                num=i-u;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,u,i-1,1,0,level);
                root_loc=j-2;
                num=j-i;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,i+1,j,0,1,level);
            }
    
        }
        else if(left==0 && right==0)//这里处理整个树的根
        {
        
            u=i;
            while(i<=j)
            {
        
                if(pos_array[root_loc]==mid_array[i])
                {
        
                    break;
                }
                i++;
            }
            tree[pot].node=mid_array[i];
            tree[pot].x=0;
            tree[pot].y=level;
            root_pot=pot;
            pot++;
            level--;
            if(num==1)
            {
        
                u++;
            }
            else if(i==u)
            {
        
                root_loc=j-1;
                num=j-u;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,u+1,j,0,1,level);
            }
            else if(i==j)
            {
        
                root_loc=j-1;
                num=j-u;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,u,j-1,1,0,level);
            }
            else
            {
        
                root_loc=i-1;
                num=i-u;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,u,i-1,1,0,level);
                root_loc=j-1;
                num=j-i;
                find_root(root_pot,num,tree,N,pos_array,root_loc,mid_array,i+1,j,0,1,level);
            }
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyODE2MQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210605203249912.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyODE2MQ==,size_16,color_FFFFFF,t_70