树中两个节点的最近公共祖先 多种情况分析

1.求树中两个节点的最近公共祖先
这个问题按 对题意解析思路 的不同， 可以有许多的变种问题 和 解决思路
首先我们来看比较简单的一种： 如果这颗树是 二叉搜索树( 假设这个二叉搜索树中没有两个值相同的结点, 并且我们 考虑的这两个结点不是空结点 )
根据二叉搜索树的性质( 左子树的值都比根节点小， 右子树的值都比根节点大 )
我们的思路为： 从根节点开始， 如果两个节点的值 都比当前节点(此时为根节点)小， 则 它们的 最低公共祖先在 当前节点的左子树中， 否则在 当前节点的右子树中
接下来 我们只需要， 将 需要判断的节点 更新为 当前节点的 左孩子结点 或 右孩子结点即可。
直到 遇到一个节点的值 介于我们的两个结点之间， 即它为这两个节点的 最近公共祖先。

当然别忘了 处理 特殊情况：  这两个结点， 其中一个节点 为 另一个结点的 祖先

：

#include <iostream>
#include <windows.h>
using namespace std;
#include "BinarySearchTree.h"					//我包含了这个头文件 来测试我们所写的函数是否能达到预期的 效果.
												//这个头文件中 只保留了 测试这个函数 需要用到的接口， 如想查看 二叉搜索树 更完整定义， 可以看我的另一篇博客 ---> 二叉搜索树
												//因为我们要用到 二叉树结点 来定义 变量， 所以在头文件中， 修改将 结点定义 放在了 类外面。 在 我的 原博客中(即二叉搜索树)， 二叉搜索树的结点定义 是属于 类的私有成员.


template <typename T>
BSTNode<T>* GetLastCommonNode( BSTNode<T>* root, BSTNode<T>* node1, BSTNode<T>* node2 )//注意， BSTNode*是错的， 返回类型是 BSTNode*<T>
{
	if ( NULL != root && NULL != node1 && NULL != node2 )
	{
		T data = root->_data;
		T data1 = node1->_data;
		T data2 = node2->_data;

		if ( data < data1 && data < data2 )
			GetLastCommonNode( root->_right, node1, node2 );
		else if ( data > data1 && data > data2 )
			GetLastCommonNode( root->_left, node1, node2 );
		else
		{
			//第一种情况: node1 与 node2 有一个结点与当前节点相等， 即 node1 与 node2 中有一个结点为另一个结点祖先( 注意， 并不是我们的树中出现了重复的数字， 这点要注意 )
			if ( data1 == data )
				return node1;
			else if ( data2 == data )
				return node2;
			else//此时 为第二种情况， 即 当前结点的值 在 两个结点之间.
				return root;
		}
	}
	else//注意， 这里必须用 else 来 匹配上面的 if.  不要抱 :  如果  执行 if 则上面 就返回了 ，如果没返回， 则这里返回 NULL 就好了.  说明上面逻辑 没执行.  不能抱这种想法。 因为上面是含有递归的， 所以 有可能是 子Fun( ) 返回了， 所以 ，如果不用 else 匹配， 有可能 返回值 被 NULL 代替 返回 ，程序挂掉. 
	{
		//如果程序运行到这， 即所给数据有问题， 如 root node1 node2 可能有一个结点为空.
		return NULL;
	}
}


void TestFun( )
{
	int a[] = { 7, 4, 1, 8, 5, 9 ,2, 3, 10 };
	BinarySearchTree<int> t;

	for ( size_t i = 0; i < sizeof(a)/sizeof(a[0]); ++i )
		t.Insert( a[i] );

	t.PrintTree( );
	cout << endl;

	BSTNode<int>* root = t.GetRoot( );

	//因为我们的 BinarySearchTree.h 头文件中 未实现 Find( ) 函数 ，我们就在这， 造几个我们想测试的 找最近祖先数据 的结点 
	//其实 node1 和 node2 只是用了 它们中的数据 进行测试.
	//还要注意的是， 本来我们的 结点指针来源于 Find( ) 函数的 返回值， 因为我们没实现 Find( ) 函数 ，所以自己造结点， 但是要注意的 一点是  我们的数据 必须是 二叉搜索树中 已有的数据 ， 因为我们是模拟 Find( )函数的返回值 ，所以不能造出， 二叉搜索树中没有数据的结点指针
	BSTNode<int>* tTest1 = new BSTNode<int>( 1 );
	BSTNode<int>* tTest2 = new BSTNode<int>( 2 );
	BSTNode<int>* tTest3 = new BSTNode<int>( 3 );
	BSTNode<int>* tTest5 = new BSTNode<int>( 5 );
	BSTNode<int>* tTest9 = new BSTNode<int>( 9 );
	BSTNode<int>* tTest10 = new BSTNode<int>( 10 );

	//非法情况
	if ( NULL == GetLastCommonNode<int>( NULL, NULL, NULL ) )
		cout << "No" << endl;

	//正常情况
	cout << "4? : " << GetLastCommonNode<int>( root, tTest5, tTest3 )->_data << endl;
	cout << "9? : " << GetLastCommonNode<int>( root, tTest9, tTest10 )->_data << endl;
	cout << "7? : " << GetLastCommonNode<int>( root, tTest2, tTest10 )->_data << endl;
	cout << "4? : " << GetLastCommonNode<int>( root, tTest1, tTest5 )->_data << endl;
}


int main( )
{
	TestFun( );

	system( "pause" );
	return 0;
}

BinarySearchTree.h:

#include <iostream>
using namespace std;


template <typename T>
struct BSTNode
{
	T _data;
	BSTNode* _left;
	BSTNode* _right;

	BSTNode( const T& x, BSTNode* left = NULL, BSTNode* right = NULL )
		: _data( x )
		, _left( left )
		, _right( right )
		{}
};


template<typename T>
class BinarySearchTree
{
public:
	BinarySearchTree( )
		: _root( NULL )
	{}

	~BinarySearchTree( )
	{
		MakeEmpty( );
	}

	void PrintTree( ) const						//采用中序遍历打印树
	{
		_PrintTree( _root );
	}

	void MakeEmpty( )
	{
		_MakeEmpty( _root );
	}

	void Insert( const T& x )
	{
		_Insert( x, _root );
	}

	BSTNode<T>* GetRoot( )							//注意 ， 这里也需要是 BSTNode<T>*.    在 public上面   typedef 时， 是 --->   typedef BSTNode<T> Node   ？？？
	{
		return _root;
	}

private:
	BSTNode<T>* _root;

	void _Insert( const T& x, BSTNode<T>*& root )//想， 它是怎么链起来的， 因为下一个root是 它父亲的左或右孩子的引用， 如果传引用， new后，它的父亲的左右孩子就被链起来了。  否则的话， 临时变量，   孩子被new值赋予后不会影响到调用它的函数的值(父亲的左or右孩子的值)
	{
		if ( NULL == root )
		{
			root = new BSTNode<T>( x, NULL, NULL );
		}
		else if ( x < root->_data )
		{
			_Insert( x, root->_left );
		}
		else if ( x > root->_data )
		{
			_Insert( x, root->_right );
		}
		else
		{
			;									//相等，目前什么都不做，当然，也可以更新值什么的.
		}
	}

	void _MakeEmpty( BSTNode<T>*& root ) const
	{
		if ( NULL == root )
		{
			;
		}
		else
		{
			_MakeEmpty( root->_left );		//后序删除
			_MakeEmpty( root->_right );

			delete root;
		}

		root = NULL;							//别忘了置NULL
	}

	void _PrintTree( BSTNode<T>* root ) const			//中序
	{
		if ( NULL == root )
		{
			return;
		}

		_PrintTree( root->_left );
		cout << root->_data << " ";
		_PrintTree( root->_right );
	}
};

我们插入的这棵二叉搜索树简略图如下：  右边是我们 要测试的两个结点 及 它们最近的公共祖先