树的两个结点的最近公共祖先结点

比眉伴天荒 2023-07-20 05:47 151阅读 0赞

//代码在“BJFU_数据结构习题_268基于二叉链表的二叉树叶子结点到根结点的路径的求解”上修改的
    #include<iostream>
    using namespace std;
    char path[100];
    char path1[100];
    char path2[100];
    typedef struct BiTNode
    {
        
        char data;
        struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    void CreateBiTree(BiTree &T,char S[],int &i)
    {
        
        if(S[i]=='0')
            T=NULL;
        else
        {
        
            T=new BiTNode;
            T->data=S[i];
            CreateBiTree(T->lchild,S,++i);
            CreateBiTree(T->rchild,S,++i);
        }
    }
    void DFS(BiTree T,int n,char c1,char c2)
    {
        
        if(T)
        {
        
            path[n]=T->data;
            if(path[n]==c1)
            {
        
                for(int i=1;i<=n;i++)
                {
        
                    path1[i]=path[i];    
                    cout<<path1[i];//从根节点输出
                }
                cout<<endl;
            }
            else if(path[n]==c2)
            {
        
                for(int i=1;i<=n;i++)
                {
        
                    path2[i]=path[i];    
                    cout<<path2[i];//从根节点输出
                }    
                cout<<endl;
            }
            else
            {
        
                DFS(T->lchild,n+1,c1,c2);
                DFS(T->rchild,n+1,c1,c2);
            }
        }
    }
    void Father(char path1[],char path2[])
    {
        
        char father;
        for(int i=1;;i++)
        {
            
            if(path1[i]==path2[i])    
                father=path1[i];
            else
            {
        
                cout<<"最近公共祖先为"<<father<<endl;
                return;
            }
        }
    }
    int main()
    {
         
        char S[100];//abcd00e00f00ig00h00
        while(cin>>S&&S[0]!='0')
        {
        
            int i=-1;
            BiTree T;
            CreateBiTree(T,S,++i);
            int n=0;
            char c1,c2;
            cin>>c1>>c2;//两个结点
            DFS(T,n+1,c1,c2);//深度遍历搜索
            Father(path1,path2);//输出最近公共祖先
        }  
        return 0;
    }
    //这个题目考察的是深度遍历，以及具有公共前缀或者后缀的数组