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

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

admin2013-07-12  70
问题 已知在二叉树中，T为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。
选项
答案 int．found＝FALSEI Bitree*Find＿Near＿Ancient(Bitree T，Bitree P，Bitree q){ ／／求二叉树T中结点P和q的最近共同祖先 Bitree pathp[100]，pathq[i00]； ／／设立两个辅助数组暂存从根到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－>ichild) Findpath(T－>ichild，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://www.kaotiyun.com/show/Juxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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