2. 考研
  3. 已知在二叉树中，T为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

已知在二叉树中，T为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

admin2012-06-26  48
问题 已知在二叉树中，T为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。
选项
答案int．found=FALSE； Bitree*Find_Near_Ancient(Bitree T，Bitree p，Bitree q){ //求二叉树T中结点P和q的最近共同祖先 Bitree pathp[100]，pathq[100]； //设立两个辅助数组暂存从根到p，q的路径 Findpath(T，p，pathp，0)； found=FALSE； Findpath(T，q，pathq，0)； //求从根到p，q的路径放在pathp和pathq中 for(i=0；pathp[i]==pathq[i]&&pathp[i]；i++) ；//查找两条路径上最后一个相同结点 return pathp[--i]； } void Findpath(Bitree T，Bitree p，Bitree path[]，int i){ //求从T到p路径的递归算法 if(T==p) { found=TRUE； //找到 return； } path[i]=T； //当前结点存入路径 if(T->lchild) Findpath(T->lchild，p，path，i+1)； //在左子树中继续寻找 if(T->rchild＆&!found) Findpath(T->rchild，p，path，i+1)； //在右子树中继续寻找 if(!found) path[i]=NULL； //回溯 }
解析 本题也可叙述为求，*p和*q两个结点的最小子树。
    遍历访问到*p时，将*p结点的祖先保存到数组pathp中，再遍历访问到*q时，将*q结点的祖先保存到数组pathq中，将数组pathp与数组pathq的结点依次(从0开始)比较，找到最近的共同祖先。
转载请注明原文地址:https://kaotiyun.com/show/8yxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)