【数据结构】二叉树中任意两节点的最近公共祖先节点

问题要求：任意给出二叉树中的两个节点，求他们的最近祖先

分三种情况：

1、该二叉树是搜索二叉树

如果两个节点的值都大于根节点，则遍历右子树查找一个处于两节点之间的值为最近祖先，如果两个节点的值都小于根节点，则遍历左子树查找一个两节点之间的值为最近祖先

Node* SearchNearAncestor(Node* root,Node* node1,Node*node2)
	{
		if (root==NULL||
			node1==NULL||
			node2==NULL)
		{
			return NULL;
		}
		if(node1==node2||node1->_parent!=NULL)
		{
			return node1;
		}
		Node* cur=root;
		while (cur)
		{
			if(cur->_key>node1->_key&&
				cur->_key>node2->_key)
			{
              cur=cur->_left;
			}
			else if(cur->_key<node1->_key&&
				cur->_key<node2->_key)
			{
				cur=cur->_right;
			}
			else 
			{
				if(node1->_parent==node2)
					return node2->_parent;
				else if(node2->_parent==node1)
					return node1->_parent;
				else
				return cur;
			}
		}

		return NULL;
	}

2、该二叉树为普通二叉树，但其有父节点，这时候，将node1的父节点和node2的parent->parent.......一直比较下去，直到二者相同，如果一直不同，则将node1再往上走，继续上步循环

查找代码为

Node* NearAncetor(Node* root,Node* node2)
	{
		if(node1==root||node2==root)
		{
			return root;
		}
		Node* tmp;
		while (node1!=NULL)
		{
			node1=node1->_parent;
			tmp=node2;
			while (tmp!=NULL)
			{
				if(node1==tmp->_parent)
					return node1;

				tmp=tmp->_parent;
			}
		}
		return NULL ;
	}

3、该二叉树为普通二叉树，他也没有父节点，这时候要分别递归左右子树，如果一个节点出现在左子树，另一个出现在右子树，则返回根节点，如果两个都出现在左，则最近祖先在子树，如果两个都出现在右，则最近祖先在右子树上

代码如下

Node* NearAncetor(Node* root,Node* node2)
	{
		if (root==NULL||
			node1==NULL||
			node2==NULL)
		{
			return NULL;
		}
		if(node1==root||node2==root)
		{
			return root;
		}
		Node* left=NearAncetor(root->_left,node1,node2);
		Node* right=NearAncetor(root->_right,node2);
		if(left&&right)
			return root;
		if(left==NULL)
			return right;
		else
			return left;
	}

二叉搜索树全部代码

#include<iostream>
using namespace std;
template<class K>
struct SearchTreeNode 
{
	typedef SearchTreeNode<K> Node;
	Node* _left;
	Node* _right;
	Node* _parent;
	K _key;
	SearchTreeNode(const K& key)
		:_left(NULL),_right(NULL),_parent(NULL),_key(key)
	{}
};
template<class K>
class SearchTree
{
	typedef SearchTreeNode<K> Node;
public:
	SearchTree()
	:_root(NULL)
	{}
	~SearchTree()
	{
		delete _root;
	}
	SearchTree(const SearchTree<K>& t)  
	{  
		_root=t._root;  
	}  
	Node* GetRoot()
	{
		return _root;
	}
	bool Find(const K& key)
	{
		if(_root==NULL)
			return false;
		Node* cur=_root;
		while (cur)
		{
			if(cur->_key>key)
				cur=cur->_left;
			else if(cur->_key<key)
				cur=cur->_right;
			else 
				return true;
		}
	}
	bool Insert(const K&key)
	{
		_Insert(_root,key);
		return true;
	}
	void Inorder()
	{
		_Inorder(_root);
		cout<<endl;
	}
	Node* SearchNearAncestor(Node* root,Node*node2)
	{
		if (root==NULL||
			node1==NULL||
			node2==NULL)
		{
			return NULL;
		}
		if(node1==node2||node1->_parent!=NULL)
		{
			return node1;
		}
		Node* cur=root;
		while (cur)
		{
			if(cur->_key>node1->_key&&
				cur->_key>node2->_key)
			{
              cur=cur->_left;
			}
			else if(cur->_key<node1->_key&&
				cur->_key<node2->_key)
			{
				cur=cur->_right;
			}
			else 
			{
				if(node1->_parent==node2)
					return node2->_parent;
				else if(node2->_parent==node1)
					return node1->_parent;
				else
				return cur;
			}
		}

		return NULL;
	}
protected:
	
	bool _Insert(Node*& root,const K& key)
	{
		if(root==NULL)
		{
		  root=new Node(key);
		  return true;
		}
		if(root->_key>key)
		{
			return _Insert(root->_left,key);
		}
		else if(root->_key<key)
		{
			return _Insert(root->_right,key);
		}
		else
			return false;
	}
	void _Inorder(Node* root)
	{
		Node* cur=root;
		if(cur==NULL)
			return;
		_Inorder(cur->_left);
		cout<<cur->_key<<" ";
		_Inorder(cur->_right);
	}
protected:
	Node* _root;
};
//void testSearch()
//{
//	int arr[]={3,4,1,5,2,6,8,7,9};
//	SearchTree<int> t;
//	
//	
//	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
//	{
//		t.Insert(arr[i]);
//	}
//	t.Inorder();
//  
//}
void test()
{
	int arr[]={5,3,9};
	SearchTree<int> t1;
	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
	{
		t1.Insert(arr[i]);
	}
	t1.Inorder();
	SearchTreeNode<int>* root=t1.GetRoot();
	SearchTreeNode<int>* node1=root->_left->_right;
	SearchTreeNode<int>* node2=root->_right->_left;
	SearchTreeNode<int>* ancetor=t1.SearchNearAncestor(root,node2);
	cout<<node1->_key<<"和"<<node2->_key<<"的最近祖先是"<<ancetor->_key<<endl;
	SearchTreeNode<int>* node3=root->_right->_right->_right;
	SearchTreeNode<int>* node4=root->_right->_left;
	SearchTreeNode<int>* ancetor2=t1.SearchNearAncestor(root,node3,node4);
	cout<<node3->_key<<"和"<<node4->_key<<"的最近祖先是"<<ancetor2->_key<<endl;
	cout<<endl;
}

这里查找4，6的最近祖先和9，6的最近祖先

结果

普通二叉树有父节点的全部代码

#include <iostream>
using namespace std;
struct TreeNode
{
	TreeNode* _left;
	TreeNode* _right;
	TreeNode* _parent;
	int _key;
	TreeNode(const int& key)
		:_left(NULL),_key(key)
	{}
};
class BinrayTree
{
	typedef TreeNode Node;
public:
    BinrayTree()
		:_root(NULL)
	{}
	~BinrayTree()
	{
		delete _root;
	}
	Node* GetRoot()
	{
		return _root;
	}
	bool Insert2(const int& key)
	{
		_Insert(_root,key);
		return true;
	}
	void Inorder2()
	{
		_Inorder(_root);
		cout<<endl;
	}
	Node* NearAncetor(Node* root,Node* node2)
	{
		if(node1==root||node2==root)
		{
			return root;
		}
		Node* tmp;
		while (node1!=NULL)
		{
			node1=node1->_parent;
			tmp=node2;
			while (tmp!=NULL)
			{
				if(node1==tmp->_parent)
					return node1;

				tmp=tmp->_parent;
			}
		}
		return NULL ;
	}
protected:
	bool _Insert(Node*& root,const int& key)
	{
		Node* node=new Node(key);
		node->_key=key;
		node->_left=node->_right=node->_parent=NULL;
		if(root==NULL)
		{
			root=node;
			return true;
		}
		if(root->_left == NULL && root->_key > key)
		{
			node->_parent=root;
			root->_left=node;
			return true;
		}
		if(root->_right == NULL && root->_key < key)
		{
			node->_parent=root;
			root->_right=node;
			return true;
		}
		if(root->_key > key)
			_Insert(root->_left,key);
		else if(root->_key < key)
			_Insert(root->_right,key);
		else
			return true;
	}
	void  _Inorder(Node* root)
	{
		Node* cur=root;
		if(cur==NULL)
			return;
		_Inorder(cur->_left);
		cout<<cur->_key<<" ";
		_Inorder(cur->_right);
	}
	Node* _root;
};
void test2()
{
	int arr[]={5,9};
	BinrayTree t1;
	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
	{
		t1.Insert2(arr[i]);
	}
	t1.Inorder2();
	TreeNode* root=t1.GetRoot();
	TreeNode* node1=root->_left->_left;
	TreeNode* node2=root->_right->_right;
	cout<<node1->_key<<"和"<<node2->_key<<"的最近祖先是";
	TreeNode* ancetor=t1.NearAncetor(root,node2);
	if(ancetor)
	cout<<ancetor->_key<<endl;
	cout<<endl;
}

这里测试1，8的最近祖先

普通二叉树且无父节点全部代码

#include <iostream>
using namespace std;
struct NoParentTreeNode
{
	NoParentTreeNode* _left;
	NoParentTreeNode* _right;
	int _key;
	NoParentTreeNode(const int& key)
		:_left(NULL),_key(key)
	{}
};
class NoParentBinrayTree
{
	typedef NoParentTreeNode Node;
public:
	NoParentBinrayTree()
		:_root(NULL)
	{}
	~NoParentBinrayTree()
	{
		delete _root;
	}
	Node* GetRoot()
	{
		return _root;
	}
	bool Insert2(const int& key)
	{
		_Insert(_root,node2);
		if(left&&right)
			return root;
		if(left==NULL)
			return right;
		else
			return left;
	}
protected:
	bool _Insert(Node*& root,const int& key)
	{
		if(root==NULL)
		{
			root=new Node(key);
			return true;
		}
		if(key>root->_key)
		{
			return  _Insert(root->_right,key);
		}
		else if(key<root->_key)
		{
			return  _Insert(root->_left,key);
		}
		else 
			return false;
	}
	void  _Inorder(Node* root)
	{
		Node* cur=root;
		if(cur==NULL)
			return;
		_Inorder(cur->_left);
		cout<<cur->_key<<" ";
		_Inorder(cur->_right);
	}
	Node* _root;
};
void test3()
{
	int arr[]={5,9};
	NoParentBinrayTree t1;
	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
	{
		t1.Insert2(arr[i]);
	}
	t1.Inorder2();
	NoParentTreeNode* root=t1.GetRoot();
	NoParentTreeNode* node1=root->_left->_left;
	NoParentTreeNode* node2=root->_right->_right->_right;
	NoParentTreeNode* ancetor=t1.NearAncetor(root,node2);
	cout<<node1->_key<<"和"<<node2->_key<<"的最近祖先是"<<ancetor->_key<<endl;
	cout<<endl;
}

这里测试1，9的最近祖先

测试代码

#include "SearchTree.h"
#include "HaveParentUnsearchTree.h"
#include "NoParentSearchTree.h"
#include <cstdlib>
int main()
{
	test();
	test2();
	test3();
	system("pause");
	return 0;
}

原文链接：https://www.f2er.com/datastructure/382393.html

【数据结构】二叉树中任意两节点的最近公共祖先节点

猜你在找的数据结构相关文章