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

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】二叉树中任意两节点的最近公共祖先节点，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

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

分三种情况：

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

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

插入代码

  1. Node* SearchNearAncestor(Node* root,Node* node1,Node*node2)
  2. 	{
  3. 		if (root==NULL||
  4. 			node1==NULL||
  5. 			node2==NULL)
  6. 		{
  7. 			return NULL;
  8. 		}
  9. 		if(node1==node2||node1->_parent!=NULL)
  10. 		{
  11. 			return node1;
  12. 		}
  13. 		Node* cur=root;
  14. 		while (cur)
  15. 		{
  16. 			if(cur->_key>node1->_key&&
  17. 				cur->_key>node2->_key)
  18. 			{
  19.               cur=cur->_left;
  20. 			}
  21. 			else if(cur->_key<node1->_key&&
  22. 				cur->_key<node2->_key)
  23. 			{
  24. 				cur=cur->_right;
  25. 			}
  26. 			else 
  27. 			{
  28. 				if(node1->_parent==node2)
  29. 					return node2->_parent;
  30. 				else if(node2->_parent==node1)
  31. 					return node1->_parent;
  32. 				else
  33. 				return cur;
  34. 			}
  35. 		}
  36.  
  37. 		return NULL;
  38. 	}
2、该二叉树为普通二叉树，但其有父节点，这时候，将node1的父节点和node2的parent->parent.......一直比较下去，直到二者相同，如果一直不同，则将node1再往上走，继续上步循环

查找代码为

  1. Node* NearAncetor(Node* root,Node* node2)
  2. 	{
  3. 		if(node1==root||node2==root)
  4. 		{
  5. 			return root;
  6. 		}
  7. 		Node* tmp;
  8. 		while (node1!=NULL)
  9. 		{
  10. 			node1=node1->_parent;
  11. 			tmp=node2;
  12. 			while (tmp!=NULL)
  13. 			{
  14. 				if(node1==tmp->_parent)
  15. 					return node1;
  16.  
  17. 				tmp=tmp->_parent;
  18. 			}
  19. 		}
  20. 		return NULL ;
  21. 	}

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

代码如下

  1. Node* NearAncetor(Node* root,Node* node2)
  2. 	{
  3. 		if (root==NULL||
  4. 			node1==NULL||
  5. 			node2==NULL)
  6. 		{
  7. 			return NULL;
  8. 		}
  9. 		if(node1==root||node2==root)
  10. 		{
  11. 			return root;
  12. 		}
  13. 		Node* left=NearAncetor(root->_left,node1,node2);
  14. 		Node* right=NearAncetor(root->_right,node2);
  15. 		if(left&&right)
  16. 			return root;
  17. 		if(left==NULL)
  18. 			return right;
  19. 		else
  20. 			return left;
  21. 	}

二叉搜索树全部代码 
  1. #include<iostream>
  2. using namespace std;
  3. template<class K>
  4. struct SearchTreeNode 
  5. {
  6. 	typedef SearchTreeNode<K> Node;
  7. 	Node* _left;
  8. 	Node* _right;
  9. 	Node* _parent;
  10. 	K _key;
  11. 	SearchTreeNode(const K& key)
  12. 		:_left(NULL),_right(NULL),_parent(NULL),_key(key)
  13. 	{}
  14. };
  15. template<class K>
  16. class SearchTree
  17. {
  18. 	typedef SearchTreeNode<K> Node;
  19. public:
  20. 	SearchTree()
  21. 	:_root(NULL)
  22. 	{}
  23. 	~SearchTree()
  24. 	{
  25. 		delete _root;
  26. 	}
  27. 	SearchTree(const SearchTree<K>& t)  
  28. 	{  
  29. 		_root=t._root;  
  30. 	}  
  31. 	Node* GetRoot()
  32. 	{
  33. 		return _root;
  34. 	}
  35. 	bool Find(const K& key)
  36. 	{
  37. 		if(_root==NULL)
  38. 			return false;
  39. 		Node* cur=_root;
  40. 		while (cur)
  41. 		{
  42. 			if(cur->_key>key)
  43. 				cur=cur->_left;
  44. 			else if(cur->_key<key)
  45. 				cur=cur->_right;
  46. 			else 
  47. 				return true;
  48. 		}
  49. 	}
  50. 	bool Insert(const K&key)
  51. 	{
  52. 		_Insert(_root,key);
  53. 		return true;
  54. 	}
  55. 	void Inorder()
  56. 	{
  57. 		_Inorder(_root);
  58. 		cout<<endl;
  59. 	}
  60. 	Node* SearchNearAncestor(Node* root,Node*node2)
  61. 	{
  62. 		if (root==NULL||
  63. 			node1==NULL||
  64. 			node2==NULL)
  65. 		{
  66. 			return NULL;
  67. 		}
  68. 		if(node1==node2||node1->_parent!=NULL)
  69. 		{
  70. 			return node1;
  71. 		}
  72. 		Node* cur=root;
  73. 		while (cur)
  74. 		{
  75. 			if(cur->_key>node1->_key&&
  76. 				cur->_key>node2->_key)
  77. 			{
  78.               cur=cur->_left;
  79. 			}
  80. 			else if(cur->_key<node1->_key&&
  81. 				cur->_key<node2->_key)
  82. 			{
  83. 				cur=cur->_right;
  84. 			}
  85. 			else 
  86. 			{
  87. 				if(node1->_parent==node2)
  88. 					return node2->_parent;
  89. 				else if(node2->_parent==node1)
  90. 					return node1->_parent;
  91. 				else
  92. 				return cur;
  93. 			}
  94. 		}
  95.  
  96. 		return NULL;
  97. 	}
  98. protected:
  99. 	
  100. 	bool _Insert(Node*& root,const K& key)
  101. 	{
  102. 		if(root==NULL)
  103. 		{
  104. 		  root=new Node(key);
  105. 		  return true;
  106. 		}
  107. 		if(root->_key>key)
  108. 		{
  109. 			return _Insert(root->_left,key);
  110. 		}
  111. 		else if(root->_key<key)
  112. 		{
  113. 			return _Insert(root->_right,key);
  114. 		}
  115. 		else
  116. 			return false;
  117. 	}
  118. 	void _Inorder(Node* root)
  119. 	{
  120. 		Node* cur=root;
  121. 		if(cur==NULL)
  122. 			return;
  123. 		_Inorder(cur->_left);
  124. 		cout<<cur->_key<<" ";
  125. 		_Inorder(cur->_right);
  126. 	}
  127. protected:
  128. 	Node* _root;
  129. };
  130. //void testSearch()
  131. //{
  132. //	int arr[]={3,4,1,5,2,6,8,7,9};
  133. //	SearchTree<int> t;
  134. //	
  135. //	
  136. //	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
  137. //	{
  138. //		t.Insert(arr[i]);
  139. //	}
  140. //	t.Inorder();
  141. //  
  142. //}
  143. void test()
  144. {
  145. 	int arr[]={5,3,9};
  146. 	SearchTree<int> t1;
  147. 	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
  148. 	{
  149. 		t1.Insert(arr[i]);
  150. 	}
  151. 	t1.Inorder();
  152. 	SearchTreeNode<int>* root=t1.GetRoot();
  153. 	SearchTreeNode<int>* node1=root->_left->_right;
  154. 	SearchTreeNode<int>* node2=root->_right->_left;
  155. 	SearchTreeNode<int>* ancetor=t1.SearchNearAncestor(root,node2);
  156. 	cout<<node1->_key<<"和"<<node2->_key<<"的最近祖先是"<<ancetor->_key<<endl;
  157. 	SearchTreeNode<int>* node3=root->_right->_right->_right;
  158. 	SearchTreeNode<int>* node4=root->_right->_left;
  159. 	SearchTreeNode<int>* ancetor2=t1.SearchNearAncestor(root,node3,node4);
  160. 	cout<<node3->_key<<"和"<<node4->_key<<"的最近祖先是"<<ancetor2->_key<<endl;
  161. 	cout<<endl;
  162. }

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

结果

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

  1. #include <iostream>
  2. using namespace std;
  3. struct TreeNode
  4. {
  5. 	TreeNode* _left;
  6. 	TreeNode* _right;
  7. 	TreeNode* _parent;
  8. 	int _key;
  9. 	TreeNode(const int& key)
  10. 		:_left(NULL),_key(key)
  11. 	{}
  12. };
  13. class BinrayTree
  14. {
  15. 	typedef TreeNode Node;
  16. public:
  17.     BinrayTree()
  18. 		:_root(NULL)
  19. 	{}
  20. 	~BinrayTree()
  21. 	{
  22. 		delete _root;
  23. 	}
  24. 	Node* GetRoot()
  25. 	{
  26. 		return _root;
  27. 	}
  28. 	bool Insert2(const int& key)
  29. 	{
  30. 		_Insert(_root,key);
  31. 		return true;
  32. 	}
  33. 	void Inorder2()
  34. 	{
  35. 		_Inorder(_root);
  36. 		cout<<endl;
  37. 	}
  38. 	Node* NearAncetor(Node* root,Node* node2)
  39. 	{
  40. 		if(node1==root||node2==root)
  41. 		{
  42. 			return root;
  43. 		}
  44. 		Node* tmp;
  45. 		while (node1!=NULL)
  46. 		{
  47. 			node1=node1->_parent;
  48. 			tmp=node2;
  49. 			while (tmp!=NULL)
  50. 			{
  51. 				if(node1==tmp->_parent)
  52. 					return node1;
  53.  
  54. 				tmp=tmp->_parent;
  55. 			}
  56. 		}
  57. 		return NULL ;
  58. 	}
  59. protected:
  60. 	bool _Insert(Node*& root,const int& key)
  61. 	{
  62. 		Node* node=new Node(key);
  63. 		node->_key=key;
  64. 		node->_left=node->_right=node->_parent=NULL;
  65. 		if(root==NULL)
  66. 		{
  67. 			root=node;
  68. 			return true;
  69. 		}
  70. 		if(root->_left == NULL && root->_key > key)
  71. 		{
  72. 			node->_parent=root;
  73. 			root->_left=node;
  74. 			return true;
  75. 		}
  76. 		if(root->_right == NULL && root->_key < key)
  77. 		{
  78. 			node->_parent=root;
  79. 			root->_right=node;
  80. 			return true;
  81. 		}
  82. 		if(root->_key > key)
  83. 			_Insert(root->_left,key);
  84. 		else if(root->_key < key)
  85. 			_Insert(root->_right,key);
  86. 		else
  87. 			return true;
  88. 	}
  89. 	void  _Inorder(Node* root)
  90. 	{
  91. 		Node* cur=root;
  92. 		if(cur==NULL)
  93. 			return;
  94. 		_Inorder(cur->_left);
  95. 		cout<<cur->_key<<" ";
  96. 		_Inorder(cur->_right);
  97. 	}
  98. 	Node* _root;
  99. };
  100. void test2()
  101. {
  102. 	int arr[]={5,9};
  103. 	BinrayTree t1;
  104. 	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
  105. 	{
  106. 		t1.Insert2(arr[i]);
  107. 	}
  108. 	t1.Inorder2();
  109. 	TreeNode* root=t1.GetRoot();
  110. 	TreeNode* node1=root->_left->_left;
  111. 	TreeNode* node2=root->_right->_right;
  112. 	cout<<node1->_key<<"和"<<node2->_key<<"的最近祖先是";
  113. 	TreeNode* ancetor=t1.NearAncetor(root,node2);
  114. 	if(ancetor)
  115. 	cout<<ancetor->_key<<endl;
  116. 	cout<<endl;
  117. }


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

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

  1. #include <iostream>
  2. using namespace std;
  3. struct NoParentTreeNode
  4. {
  5. 	NoParentTreeNode* _left;
  6. 	NoParentTreeNode* _right;
  7. 	int _key;
  8. 	NoParentTreeNode(const int& key)
  9. 		:_left(NULL),_key(key)
  10. 	{}
  11. };
  12. class NoParentBinrayTree
  13. {
  14. 	typedef NoParentTreeNode Node;
  15. public:
  16. 	NoParentBinrayTree()
  17. 		:_root(NULL)
  18. 	{}
  19. 	~NoParentBinrayTree()
  20. 	{
  21. 		delete _root;
  22. 	}
  23. 	Node* GetRoot()
  24. 	{
  25. 		return _root;
  26. 	}
  27. 	bool Insert2(const int& key)
  28. 	{
  29. 		_Insert(_root,node2);
  30. 		if(left&&right)
  31. 			return root;
  32. 		if(left==NULL)
  33. 			return right;
  34. 		else
  35. 			return left;
  36. 	}
  37. protected:
  38. 	bool _Insert(Node*& root,const int& key)
  39. 	{
  40. 		if(root==NULL)
  41. 		{
  42. 			root=new Node(key);
  43. 			return true;
  44. 		}
  45. 		if(key>root->_key)
  46. 		{
  47. 			return  _Insert(root->_right,key);
  48. 		}
  49. 		else if(key<root->_key)
  50. 		{
  51. 			return  _Insert(root->_left,key);
  52. 		}
  53. 		else 
  54. 			return false;
  55. 	}
  56. 	void  _Inorder(Node* root)
  57. 	{
  58. 		Node* cur=root;
  59. 		if(cur==NULL)
  60. 			return;
  61. 		_Inorder(cur->_left);
  62. 		cout<<cur->_key<<" ";
  63. 		_Inorder(cur->_right);
  64. 	}
  65. 	Node* _root;
  66. };
  67. void test3()
  68. {
  69. 	int arr[]={5,9};
  70. 	NoParentBinrayTree t1;
  71. 	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
  72. 	{
  73. 		t1.Insert2(arr[i]);
  74. 	}
  75. 	t1.Inorder2();
  76. 	NoParentTreeNode* root=t1.GetRoot();
  77. 	NoParentTreeNode* node1=root->_left->_left;
  78. 	NoParentTreeNode* node2=root->_right->_right->_right;
  79. 	NoParentTreeNode* ancetor=t1.NearAncetor(root,node2);
  80. 	cout<<node1->_key<<"和"<<node2->_key<<"的最近祖先是"<<ancetor->_key<<endl;
  81. 	cout<<endl;
  82. }

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


测试代码

  1. #include "SearchTree.h"
  2. #include "HaveParentUnsearchTree.h"
  3. #include "NoParentSearchTree.h"
  4. #include <cstdlib>
  5. int main()
  6. {
  7. 	test();
  8. 	test2();
  9. 	test3();
  10. 	system("pause");
  11. 	return 0;
  12. }

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

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test