直接贴代码
#include "stdafx.h"
#include <iostream>
#include <list>
using namespace std;
//定义二叉树的节点
struct BinaryTreeNode
{
char m_nvalue;
BinaryTreeNode * m_pleft;
BinaryTreeNode * m_pright;
};
//创建值为value的节点
BinaryTreeNode * CreateBinaryTreeNode(char value)
{
BinaryTreeNode * p=new BinaryTreeNode();
p->m_nvalue=value;
p->m_pleft=NULL;
p->m_pright=NULL;
return p;
}
//设置左孩子
void SetLeftchild(BinaryTreeNode * pRoot,BinaryTreeNode * lchild)
{
if(pRoot==NULL)
return;
pRoot->m_pleft=lchild;
}
//设置右孩子
void SetRightchild(BinaryTreeNode * pRoot,BinaryTreeNode * rchild)
{
if(pRoot==NULL)
return;
pRoot->m_pright=rchild;
}
//保存从根到某节点的路径(最重要函数)
bool getPath(BinaryTreeNode * pRoot,BinaryTreeNode * pNode,list<BinaryTreeNode *> & List)
{
if(pRoot==NULL || pNode ==NULL)
return false;
if(pRoot==pNode)
{
List.push_back(pRoot);
return true;
}
List.push_back(pRoot);
bool result=getPath(pRoot->m_pleft,pNode,List);
if(!result)
result=getPath(pRoot->m_pright,pNode,List);
if(!result)
List.pop_back();
return result;
}
BinaryTreeNode * getCommonParent(BinaryTreeNode * pRoot,BinaryTreeNode * pNode1,BinaryTreeNode * pNode2)
{
list<BinaryTreeNode *> List1;
list<BinaryTreeNode *> List2;
bool result1=getPath(pRoot,pNode1,List1);
bool result2=getPath(pRoot,pNode2,List2);
if(result1==false || result2==false)
return NULL;
BinaryTreeNode * commonParent=NULL;
list<BinaryTreeNode *>::iterator ite1=List1.begin();
list<BinaryTreeNode *>::iterator ite2=List2.begin();
for(;ite1!=List1.end() && ite2!=List2.end();ite1++,ite2++)
{
if(*ite1==*ite2)
commonParent=*ite1;
else
break;
}
return commonParent;
}
void printList(list<BinaryTreeNode *> &List)
{
for(list<BinaryTreeNode *>::iterator ite=List.begin();ite!=List.end();ite++)
{
cout<<(*ite)->m_nvalue<<" ";
}
cout<<endl;
}
//创建一棵如下所示的二叉树
// A
// / \
// B C
// / \
// D E
// / \ / \
// F G H I
//
int _tmain(int argc, _TCHAR* argv[])
{
BinaryTreeNode * pA=CreateBinaryTreeNode('A');
BinaryTreeNode * pB=CreateBinaryTreeNode('B');
BinaryTreeNode * pC=CreateBinaryTreeNode('C');
BinaryTreeNode * pD=CreateBinaryTreeNode('D');
BinaryTreeNode * pE=CreateBinaryTreeNode('E');
BinaryTreeNode * pF=CreateBinaryTreeNode('F');
BinaryTreeNode * pG=CreateBinaryTreeNode('G');
BinaryTreeNode * pH=CreateBinaryTreeNode('H');
BinaryTreeNode * pI=CreateBinaryTreeNode('I');
SetLeftchild(pA,pB);
SetRightchild(pA,pC);
SetLeftchild(pB,pD);
SetRightchild(pB,pE);
SetLeftchild(pD,pF);
SetRightchild(pD,pG);
SetLeftchild(pE,pH);
SetRightchild(pE,pI);
BinaryTreeNode * p=getCommonParent(pA,pD,pF);
if(p!=NULL)
cout<<"Common Parent is "<<p->m_nvalue<<endl;
system("PAUSE");
return 0;
}
| 
转播
