#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;
}
本文出自 “追寻内心的声音” 博客，请务必保留此出处http://ljy789.blog.51cto.com/10697684/1835166
原文：http://ljy789.blog.51cto.com/10697684/1835166