二叉树：距离最近的共同祖先

最新推荐文章于 2025-03-28 09:33:37 发布

客院载论

最新推荐文章于 2025-03-28 09:33:37 发布

阅读量821

点赞数

分类专栏：数据结构 OJ C++ 文章标签：数据结构 c++ 二叉树

本文链接：https://blog.csdn.net/Blackoutdragon/article/details/110825431

版权

数据结构同时被 3 个专栏收录

124 篇文章

订阅专栏

C++

84 篇文章

订阅专栏

67 篇文章

订阅专栏

文章目录

问题描述 :

目的：使用C++模板设计二叉树的抽象数据类型（ADT）。并在此基础上，使用二叉树ADT的基本操作，设计并实现简单应用的算法设计。
内容：（1）请参照链表的ADT模板，设计二叉树的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件，以及网盘中的链表ADT原型文件，自行设计二叉树的ADT。）
注意：二叉树ADT的基本操作的算法设计很多要用到递归的程序设计方法。
（2）ADT的简单应用：使用该ADT设计并实现若干应用二叉树的算法设计。
应用：要求设计一个算法，查找距离二叉树中2个结点最近的共同祖先。二叉树的存储结构的建立参见二叉树应用1。
注意：x、y都是属于该二叉树的结点。

参考函数原型：

//查找距离二叉树中2个结点最近的共同祖先 （用户函数）

template<class ElemType>

BinaryTreeNode<ElemType> * FindNearAncient( BinaryTree<ElemType> &T, ElemType &x, ElemType &y );

辅助函数：

//查找从根结点到元素值为x的结点的路径 （成员函数，参见基本操作18）

template<class ElemType> //Q为存放路径的顺序队列

void BinaryTree<ElemType>::FindPath( ElemType &x, SqQueue<BinaryTreeNode<ElemType> *> &Q );

输入说明 :

第一行：表示无孩子或指针为空的特殊分隔符

第二行：二叉树的先序序列（结点元素之间以空格分隔）

第三行：元素值x

第四行：元素值y

输出说明 :

第一行：元素值（共同祖先）

如x、y中有根结点，则输出NULL

输入范例 :

#
A B # C D # # E # # F # G # H # #
B
D

输出范例 :

思路分析

在这里插入图片描述

将问题转换为找两个字符串的公共子串的最后一个元素

实现伪码

BinaryTreeNode * FindNearAncient( BinaryTree T
                                           , ElemType x, ElemType y ){

    //树为空，就退出
    if(T.BinaryTreeisEmpty()) return NULL;

    //建造两个队列用来保存二者的路径
    SqQueue<BinaryTreeNode*> xQueue,yQueue;

    //生成二者的路径的
    T.FindPath(x,xQueue);
    T.FindPath(y,yQueue);

    //遍历两个队列，找对最后一个公共前缀
    BinaryTreeNode *xNode,*yNode;
    xQueue.deQueue(xNode);
    yQueue.deQueue(yNode);

    //遍历两个队列
    while(xNode->getData() != yNode->getData()){

        //首先队列不是等长的，长的先出
        if(xQueue.getQueueNums() > yQueue.getQueueNums()){
             xQueue.deQueue(xNode);
        }
        else if(xQueue.getQueueNums() < yQueue.getQueueNums()){
            yQueue.deQueue(yNode);

        }else{
            xQueue.deQueue(xNode);
            yQueue.deQueue(yNode);

        }
    }

    //里面还有一个节点可以出队
    if(xQueue.getQueueNums() >= 1)
    {
        xQueue.deQueue(xNode);
        return xNode;

    }else{
        return NULL;

    }
}