#include<iostream>usingnamespacestd;template<classT>structBinaryTreeNode{BinaryTreeNode<T>(constT&data):_data(data),_left(NULL),_right(NULL){}T_data;BinaryTreeNode<T>*_left;BinaryTreeNode<T>*_right;};template<classT>classBinaryTree{public:BinaryTree<T>():_root(NULL){}BinaryTree<T>(constT*a,size_tsize){size_tindex=0;_root=CreateTree(a,index,size);}BinaryTreeNode<T>*FindGFather(intn1,intn2){return_FindGFather(_root,n1,n2);}voidPreOrder(){_PreOrder(_root);cout<<endl;}protected:BinaryTreeNode<T>*CreateTree(constT*a,size_t&index,size_tsize){BinaryTreeNode<T>*root=NULL;if((index<size)&&(a[index]!='#')){root=newBinaryTreeNode<T>(a[index]);root->_left=CreateTree(a,++index,size);root->_right=CreateTree(a,++index,size);}returnroot;}//看数字n在不在root这棵树里边boolIsOfTree(BinaryTreeNode<T>*root,intn){if(root==NULL)returnfalse;elseif(root->_data==n)returntrue;elsereturn(IsOfTree(root->_left,n)||IsOfTree(root->_right,n));}BinaryTreeNode<T>*_FindGFather(BinaryTreeNode<T>*root,intn1,intn2){if(IsOfTree(root,n1)&&IsOfTree(root,n2))//n1和n2都在这棵树里边，继续往下{if(IsOfTree(root->_left,n1)&&(IsOfTree(root->_left,n2)))return_FindGFather(root->_left,n1,n2);elseif(IsOfTree(root->_right,n1)&&(root->_right,n2))return_FindGFather(root->_right,n1,n2);elsereturnroot;//n1和n2在不同的子树里边，返回上一级；或者n1是n2的父亲（n2是n1的父亲），就返回父亲的值}elsereturnNULL;}void_PreOrder(BinaryTreeNode<T>*root){if(root==NULL)return;cout<<root->_data<<"";_PreOrder(root->_left);_PreOrder(root->_right);}protected:BinaryTreeNode<T>*_root;};voidtest(){intarr[]={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;}intmain(){test();system("pause");return0;}