求二叉树中两个节点的最低公共祖先节点

直接贴代码，关于求二叉树中两个节点的最低公共祖先节点二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm#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;
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-07/104855.htm