网站 优化 件,制作网页游戏的软件,成都工业设计公司排名,辽宁建设工程信息网保函保险服务设一棵二叉树的结点结构为(LLINK,INFO,RLINK)#xff0c;ROOT为指向该二叉树根结点的指针#xff0c;p和q分别为指向该二叉树中任意两个节点的指针#xff0c;试编写算法ANCESTOR(ROOT,p,q,r)#xff0c;找到p和q的最近公共祖先结点r #include iostream
#include ROOT为指向该二叉树根结点的指针p和q分别为指向该二叉树中任意两个节点的指针试编写算法ANCESTOR(ROOT,p,q,r)找到p和q的最近公共祖先结点r #include iostream
#include stack
#includequeue
typedef struct treenode{char INFO;struct treenode *LLINK;struct treenode *RLINK;
}treenode,*ptreenode;ptreenode buytreenode(char x)
{ptreenode n(ptreenode) malloc(sizeof (treenode));n-INFOx;n-LLINK nullptr,n-RLINK nullptr;return n;
}ptreenode build_tree()
{ptreenode root buytreenode(A);root-LLINK buytreenode(B);root-RLINK buytreenode(C);root-LLINK-LLINK buytreenode(D);root-LLINK-RLINK buytreenode(E);root-RLINK-LLINK buytreenode(F);root-RLINK-RLINK buytreenode(G);root-LLINK-LLINK-LLINK buytreenode(H);root-LLINK-LLINK-RLINK buytreenode(I);return root;
}void print_tree(ptreenode root) {std::queueptreenode tmp;tmp.push(root);int s tmp.size();while (!tmp.empty()) {ptreenode t tmp.front();tmp.pop();s--;printf(%3c, t-INFO);if (t-LLINK) tmp.push(t-LLINK);if (t-RLINK) tmp.push(t-RLINK);if (s 0) puts(), s tmp.size();}
}ptreenode ancestor(ptreenode root,ptreenode p,ptreenode q)
{if(rootq||rootp||root nullptr) return root;ptreenode left ancestor(root-LLINK,p,q);ptreenode right ancestor(root-RLINK,p,q);if(left! nullptrright! nullptr) return root;if(left nullptr) return right;return left;//如果left和right都是空的那么返回其中任意一个就行也就是返回空
}
int main() {ptreenode rootbuild_tree();print_tree(root);puts();printf(%3c\n,ancestor(root,root-LLINK-LLINK,root-LLINK-RLINK)-INFO);puts();printf(%3c\n,ancestor(root,root-LLINK-LLINK-LLINK,root-LLINK-LLINK-RLINK)-INFO);return 0;
}
