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

#include <iostream> using namespace std; template<class T> struct BinaryTreeNode {                 BinaryTreeNode< T>(const T& data)                                 :_data( data)                                 ,_left( NULL)                                 ,_right( NULL)                 {}                  T _data;                  BinaryTreeNode<T >* _left;                  BinaryTreeNode<T >* _right; }; template<class T> class BinaryTree { public:                 BinaryTree< T>()                                 :_root( NULL)                 {}                 BinaryTree< T>(const T* a, size_t size)                 {                                  size_t index = 0;                                 _root = CreateTree( a, index, size );                 }                  BinaryTreeNode<T >* FindGFather(int n1, int n2)                 {                                  return _FindGFather(_root, n1 , n2);                 }                  void PreOrder()                 {                                 _PreOrder(_root);                                 cout<<endl;                 } protected:                  BinaryTreeNode<T >* CreateTree(const T* a, size_t& index, size_t size)                 {                                  BinaryTreeNode<T >* root = NULL;                                  if ((index < size) && ( a[index ] != '#'))                                 {                                                 root= new BinaryTreeNode <T>(a[index]);                                                 root->_left=CreateTree( a, ++index , size);                                                 root->_right=CreateTree( a, ++index , size);                                 }                                  return root;                 }                  //看数字n在不在root这棵树里边                  bool IsOfTree(BinaryTreeNode <T>* root, int n)                 {                                  if(root ==NULL)                                                  return false ;                                  else if (root->_data== n)                                                  return true ;                                  else                                                  return (IsOfTree(root ->_left,n) || IsOfTree( root->_right, n ));                 }                  BinaryTreeNode<T >* _FindGFather(BinaryTreeNode< T>* root , int n1, int n2)                 {                                  if(IsOfTree(root , n1) && IsOfTree( root, n2 ))  //n1和n2都在这棵树里边，继续往下                                 {                                                  if(IsOfTree(root ->_left, n1) && (IsOfTree( root->_left, n2 )))                                                                  return _FindGFather(root ->_left, n1, n2);                                                  else if (IsOfTree(root->_right, n1) && (root ->_right, n2))                                                                  return _FindGFather(root ->_right, n1, n2);                                                  else                                                                  return root ;  //n1和n2在不同的子树里边，返回上一级；或者n1是n2的父亲（n2是n1的父亲），就返回父亲的值                                 }                                  else                                                  return NULL ;                 }                  void _PreOrder(BinaryTreeNode <T>* root)                 {                                  if(root ==NULL)                                                  return;                                 cout<< root->_data<<" " ;                                 _PreOrder( root->_left);                                 _PreOrder( root->_right);                 } protected:                  BinaryTreeNode<T >* _root; }; void test() {                  int arr[]={20, 18, 21, '#' , '#', 5, 7, '#', 3, '#' ,'#', 12, '#', '#' , 6};                  BinaryTree<int > t(arr,sizeof(arr)/ sizeof(arr[0]));                 t.PreOrder();                  BinaryTreeNode<int >* ret = t.FindGFather(21, 12);                 cout<<ret->_data<<endl; } int main() {                 test();                 system( "pause");                  return 0; }