二叉樹中兩個節點的最近公共祖先節點

#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;
}