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

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

admin2014-12-08  132
问题 已知在二叉树中，T为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。
选项
答案int found：FALSE； Bitree*Find_Near_Ancient(Bitree T，Bitree P，Bitree q){ ／／求二叉树T中结点P和q的最近共同祖先 Bitree pathp[i00]，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； ／／回溯 }
解析
转载请注明原文地址:https://kaotiyun.com/show/RZxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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