#pragma once
#include <iostream>
#include <cassert>
#include <stack>
#include <vector>
using namespace std;
template <
typename T>
struct TreeNode
{
T _data;
TreeNode<T>* _left;
TreeNode<T>* _right;
TreeNode(
const T& data = T())
:_data(data)
,_left(NULL)
,_right(NULL)
{}
};
template <
typename T>
class BinaryTree
{
public:
typedef TreeNode<T> Node;
BinaryTree()
:_root(NULL)
{}
BinaryTree(T* a,size_t n,
const T& invalid)
:_root(NULL)
{
assert(a);
size_t index =
0;
_root = _CreatTree(a,n,index,invalid);
}
~BinaryTree()
{
if (_root)
{
_Destroy(_root);
_root = NULL;
}
}
bool Find(
const T& data)
{
return _Find(_root,data);
}
Node* sameAncester(Node* n1,Node* n2)
{
return _sameAncester3(_root,n1,n2);
}
protected:
Node* _CreatTree(T* a,size_t n,size_t& index,
const T& invalid)
{
Node* root = NULL;
if (a[index] != invalid && index < n)
{
root =
new Node(a[index]);
root->_left = _CreatTree(a,n,++index,invalid);
root->_right = _CreatTree(a,n,++index,invalid);
}
return root;
}
void _Destroy(Node* root)
{
if (root)
{
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
root = NULL;
}
}
bool _Find(Node* root,
const T& data)
{
if (NULL == root)
{
return false;
}
else if (root->_data == data)
{
return true;
}
else
{
bool isIn =
false;
if (root->_left && !isIn)
isIn = _Find(root->_left,data);
if (root->_right && !isIn)
isIn = _Find(root->_right,data);
return isIn;
}
}
Node* _sameAncester1(Node*& root,Node* n1,Node* n2)
{
assert(n1 && n2);
if (root && Find(n1->_data) && Find(n2->_data))
{
if (root->_data == n1->_data || root->_data == n2->_data)
{
return root;
}
else
{
Node* cur = root;
bool tmp1 = _Find(cur->_left,n1->_data);
bool tmp2 = _Find(cur->_left,n2->_data);
if (tmp1 && tmp2)
{
return _sameAncester1(cur->_left,n1,n2);
}
else if(!tmp1 && !tmp2)
{
return _sameAncester1(cur->_right,n1,n2);
}
else
{
return root;
}
}
}
return NULL;
}
bool _GetPath2(Node* root,Node* cur,
stack<Node*>& s)
{
if (NULL == root || NULL == cur)
return false;
s.push(root);
if (cur->_data == root->_data)
{
return true;
}
if (_GetPath2(root->_left,cur,s))
{
return true;
}
if (_GetPath2(root->_right,cur,s))
{
return true;
}
s.pop();
return false;
}
Node* _sameAncester2(Node*& root,Node* n1,Node* n2)
{
if (NULL == root)
{
return NULL;
}
stack<Node*> s1;
stack<Node*> s2;
_GetPath2(root,n1,s1);
_GetPath2(root,n2,s2);
while (s1.size() > s2.size())
{
s1.pop();
}
while(s1.size() < s2.size())
{
s2.pop();
}
while(s1.top() != s2.top())
{
s1.pop();
s2.pop();
}
return s1.top();
}
bool _GetPath3(Node* root,Node* cur,
vector<Node*>& v)
{
if (NULL == root || NULL == cur)
return false;
v.push_back(root);
if (cur->_data == root->_data)
{
return true;
}
else
{
bool ret =
false;
if (root->_left && !ret)
{
ret = _GetPath3(root->_left,cur,v);
}
if (root->_right && !ret)
{
ret = _GetPath3(root->_right,cur,v);
}
if (ret ==
false && v.size() !=
0)
{
v.pop_back();
}
return ret;
}
}
Node* _sameAncester3(Node*& root,Node* n1,Node* n2)
{
if (NULL == root)
{
return NULL;
}
vector<Node*> v1;
vector<Node*> v2;
_GetPath3(root,n1,v1);
_GetPath3(root,n2,v2);
vector<Node*>::iterator it1 = v1.begin();
vector<Node*>::iterator it2 = v2.begin();
while(it1 != v1.end() && it2 != v2.end())
{
if (*it1 != *it2)
{
return *(--it1);
}
++it1;
++it2;
}
if (it1 == v1.end() || it2 == v2.end())
return *(--it1);
return NULL;
}
private:
Node* _root;
};
void Test()
{
int a1[] = {
1,
2,
'#',
3,
'#',
'#',
4,
5,
'#',
6,
'#',
7,
'#',
'#',
8};
int a2 [
10] = {
1,
2,
3,
'#',
'#',
4,
'#' ,
'#',
5,
6};
size_t n1 =
sizeof(a1)/
sizeof(a1[
0]);
size_t n2 =
sizeof(a2)/
sizeof(a2[
0]);
BinaryTree<
int> bt1(a1,n1,
'#');
BinaryTree<
int> bt2(a2,n2,
'#');
cout<<
"2:"<<bt1.Find(
2)<<endl;
cout<<
"9:"<<bt1.Find(
9)<<endl;
cout<<
"7:"<<bt2.Find(
7)<<endl;
cout<<
"6:"<<bt2.Find(
6)<<endl;
cout<<bt1.sameAncester(
new TreeNode<
int>(
3),
new TreeNode<
int>(
8))->_data<<endl;
cout<<bt1.sameAncester(
new TreeNode<
int>(
3),
new TreeNode<
int>(
2))->_data<<endl;
cout<<bt1.sameAncester(
new TreeNode<
int>(
8),
new TreeNode<
int>(
7))->_data<<endl;
cout<<bt1.sameAncester(
new TreeNode<
int>(
1),
new TreeNode<
int>(
3))->_data<<endl;
}