试编写算法,求二叉树T中结点a和b的最近共同祖先。

试编写算法,求二叉树T中结点a和b的最近共同祖先。
二叉链表类型定义:
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild,*rchild;
} BiTNode, *BiTree;
可用栈类型Stack的相关定义:
typedef struct {
BiTNode *ptr; // 二叉树结点的指针类型
int tag; // 0..1
} SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
int StackLength(SqStack S);
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e);
Status GetTop(Stack S, SElemType &e);
*
********/
BiTree CommAncestor(BiTree T, TElemType a, TElemType b)
/* 求二叉树T中结点a和b的最近共同祖先 */
{

}

5个回答

非递归方式:

 BTreeNode_t *GetLastCommonParent(BTreeNode_t *pRoot,  BTreeNode_t *pNode1, BTreeNode_t *pNode2){
    if( pRoot == NULL || pNode1 == NULL || pNode2 == NULL) 
        return NULL;


    vector < BTreeNode_t *>  vec1;//用来保存从根节点到指定节点的遍历路径,前序遍历
    vector <BTreeNode_t *>   vec2;
    stack <BTreeNode_t *>   st;
    bool  findflag1 = false;
    bool findflag2 = false;
    BTreeNode_t *commonParent = NULL;


    while( pRoot != NULL || !st.empty() ){
        while( pRoot != NULL ){



            if( findflag1 == false){//没有找出所有的节点:从根节点到指定节点,在遍历时继续入栈
                vec1.push_back( pRoot);
                if( pRoot == pNode1)//找到,则设置标志位
                    findflag1 = true;
            }


            if( findflag2 == false ){
                vec1.push_back( pRoot);
                if( pRoot == pNode2 )
                    findflag2 = true;
            }


            if( findflag1 == true && findflag2 == true)//如果都已找到,则退出
                break;

            st.push( pRoot);
            pRoot = pRoot->m_pLeft;
        }


        while( !st.empty()){
            pRoot = st.top();
            st.pop();
            pRoot = pRoot->right;

            if( findflag1 == false )//没有找到全部路径节点时,就需要将错误路径节点退出
                vec1.pop_back();


            if( findflag2 == false )
                vec2.pop_back();
        }
        if( findflag1 == true && findflag2 == true)//如果都已找到,则退出
            break;


    } 
    if( findflag1 == true && findflag2 == true){//在两个遍历路径上查找最后一个相同的节点,就是最低公共祖先节点(最近公共父节点) 
        vector< BTreeNode_t *> ::iterator iter1 = vec1.begin(); 
        vector< BTreeNode_t *> ::iterator iter2 = vec2.begin(); 
        while( iter1 != vec1.end() && iter2 != vec2.end() ){ 
            if( *iter1 == *iter2) 
                commonParent = *iter1; 
            else 
                break; 
            ++iter1; 
            ++iter2;
         } 
    } 


    vec1.clear(); 
    vec2.clear(); 
    st.clear(); 


    return commonParent;
}
wangyaninglm
shiter 这个版本呢?
5 年多之前 回复
zhen_94
zhen_94 回复知常曰明: 想要把a及其祖先进栈1,b及其祖先进栈2,总是失败
5 年多之前 回复
gamefinity
知常曰明 回复zhen_94: 其实很简单啦。你找到去A的路,找到去B的路,两条路一比较,从哪里开始分叉的,结果就是它
5 年多之前 回复
zhen_94
zhen_94 就是看不太懂啊
5 年多之前 回复
 BTreeNode_t *GetLastCommonParent( BTreeNode_t *pRoot, BTreeNode_t *pNode1, BTreeNode_t *pNode2){
    if( pRoot == NULL ) //说明是空树,不用查找了,也就找不到对应节点,则返回NULL
        return  NULL;

    if( pRoot == pNode1 || pRoot == pNode2 )//说明在当前子树的根节点上找到两个节点之一
        return pRoot;

    BTreeNode_t   *pLeft = GetLastCommonParent( pRoot->m_pLeft, pNode1, pNode2);  //左子树中的查找两个节点并返回查找结果
    BTreeNode_t   *pRight = GetLastCommonParent( pRoot->m_pRight, pNode1, pNode2);//右子树中查找两个节点并返回查找结果

    if( pLeft == NULL )//如果在左子树中没有找到,则断定两个节点都在右子树中,可以返回右子树中查询结果;否则,需要结合左右子树查询结果共同断定
        return pRight;
    if ( pRight == NULL )//如果在右子树中没有找到,则断定两个节点都在左子树中,可以返回左子树中查询结果;否则,需要结合左右子树查询结果共同断定
        return pLeft;

    return pRoot;//如果在左右子树中都找两个节点之一,则pRoot就是最低公共祖先节点,返回即可。
}

wangyaninglm
shiter 回复zhen_94: 你的测试用例正确么?
5 年多之前 回复
zhen_94
zhen_94 这个试了之后,有时候会返回空
5 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐