LCA.tar.zip_二叉树的最近公共祖先问题

#include <iostream> #include <fstream> using namespace std; #define MAX_TREE_SIZE 100 typedef int ElemType; //双亲结点 typedef struct PTNode //定义树中的一个结点 { ElemType data; int parent; }PTNode; //树结构 typedef struct { PTNode nodes[MAX_TREE_SIZE]; int n; //树中结点的总数 }PTree; int getHeight(PTree& p , int n){//获得第n个节点在树中的深度 int h = 0; int k = p.nodes[n - 1].parent; while(k != -1){ h++; k = p.nodes[k].parent; } return h; } PTree creat(ifstream & in){ //使用双亲表示法创建并存储树 PTree p; p.nodes[0].data = 1; p.nodes[0].parent = -1; //初始化根结点 int n = 0 ; //节点数 int i = 0 ; //指向当前节点的双亲的指针 int k = 1; //nodes指针 int num = 2; //节点序号 int m = 0; //第i个节点的儿子节点数 in>>n; p.n = n; while(n--){ in>>m; if(m == 0) i++; while(m--){ int c; in>>c; p.nodes[k].data = num++; p.nodes[k].parent = i; k++; if(m == 0) i++; } } return p; } void LCA(ifstream& in , PTree& p){ //求最近公共节点的算法LCA int k ; in>>k; int n1,n2; ofstream out; out.open("/Users/ydy/Desktop/output.txt"); while(k --){ in>>n1; in>>n2; //输入寻找祖先的两个节点 out<<n1<<" "<<n2<<" "; while(getHeight(p,n1) != getHeight(p,n2)){ //向上寻找双亲，使两节点处于同一深度 if(getHeight(p,n1) > getHeight(p,n2)){ n1 = p.nodes[n1 - 1].parent + 1; }else{ n2 = p.nodes[n2 - 1].parent + 1; } } while(n1 != n2){ //寻找公共祖先 n1 = p.nodes[n1 - 1].parent + 1; n2 = p.nodes[n2 - 1].parent + 1; } out<<n1<<"\n"; //公共祖先的编号用n1表示，输出到文本中 } } int main(){ ifstream in; in.open("/Users/ydy/Desktop/input.txt"); PTree p = creat(in); /* 测试树建立是否正确*/ cout<<"i "<<"data "<<"parent"<<endl; for(int i = 0 ; i < p.n ; i++){ cout<<i<<" "<<p.nodes[i].data<<" "<<p.nodes[i].parent<<endl; } /* 测试深度是否正确*/ for(int i = 1 ; i <= p.n ;i++){ cout<<"node (" << i << ") 深度为" << getHeight(p,i)<<endl; } LCA(in,p); in.close(); return 0; }