[Data Structure] Recent public ancestors of any two nodes in the binary tree

Question request: Give two nodes in the binary tree arbitrarily, and find their nearest ancestor

There are three types Situation:

1. The binary tree is a search binary tree

If the values ​​of both nodes are greater than the root node, traverse the right subtree to find the nearest value between the two nodes Ancestor, if the value of both nodes is less than the root node, then traverse the left subtree to find a value between the two nodes is the nearest ancestor

insert code

< pre code_snippet_id="1994384" snippet_file_name="blog_20161119_1_4084628" name="code" class="cpp">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_key&& cur->_key_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. The binary tree is an ordinary binary tree, but it has a parent node. At this time, compare the parent node of node1 and the parent->parent of node2 until the two are the same. If it is always different, move node1 up again and continue the previous step loop

The search code is

Node* NearAncetor (Node* root,Node* node1,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. The binary tree It is an ordinary binary tree, and it does not have a parent node. At this time, it is necessary to recurse the left and right subtrees separately. If one node appears in the left subtree and the other appears in the right subtree, the root node is returned. If both appear on the left, then The nearest ancestor is in the subtree. If both appear on the right, the nearest ancestor is on the right subtree.

The code is as follows

Node* NearAncetor(Node* root,Node* node1,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,node1,node2); if(left&&right) return root; if(left==NULL) return right; else return left; }

All codes of binary search tree

#includeusing namespace std;templatestruct SearchTreeNode {typedef SearchTreeNode Node; Node* _left; Node* _right; Node* _parent; K _key; SearchTreeNode(const K& key) :_left(NULL) ,_right(NULL) ,_parent(NULL) ,_key(key) {}};templateclass SearchTree{ typedef SearchTreeNode Node;public: SearchTree() :_root(NULL ) {} ~SearchTree() {delete _root;} SearchTree(const SearchTree& 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 _right; else return true;}} bool Insert(const K&key) {_Insert(_root,key); return true;} void Inorder() {_Inorder(_root); cout<_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_key&& cur->_key_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_right ,key);} else return false;} void _Inorder(Node* root) {Node* cur=root; if(cur==NULL) return; _Inorder(cur->_left); cout<_key<< ""; _Inorder(cur->_right); }protected: Node* _root;};//void testSea rch()//{// int arr[]={3,4,1,5,2,6,8,7,9};// SearchTree t;// // // for(int i=0;i t1; for(int i=0;i* root=t1.GetRoot(); SearchTreeNode* node1=root->_left->_right; SearchTreeNode* node2=root->_right->_left; SearchTreeNode* ancetor=t1.SearchNearAncestor(root,node1,node2); cout<_key The nearest ancestor of <<" and "<_key<<" is "<_key<* node3=root->_right->_right->_right; SearchTreeNode* node4=root->_right->_left; SearchTreeNode* ancetor2=t1.SearchNearAncestor(root,node3,node4); cout<_key<<" and "<_key<< The nearest ancestor of "is"<_key<
  
Find the nearest ancestors of 4 and 6 here The nearest ancestor of 9,6
Result

Common binary tree has all the codes of the parent node

#include using namespace std;struct TreeNode{ TreeNode* _left; TreeNode* _right; TreeNode* _parent; int _key; TreeNode(const int& key) :_left(NULL) ,_right(NULL) ,_parent(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<_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 _parent=root; root->_right=node; return true;} if(root->_key> key) _Insert(root->_left,key); else if(root->_key _right,key); else return true;} void _Inorder(Node* root ) {Node* cur=root; if(cur==NULL) return; _Inorder(cur->_left); cout<_key<<" "; _Inorder(cur->_right);} Node* _root; };void test2(){ int arr[]={5,3,4,1,7,8,2,6,0,9}; BinrayTree t1; for(int i=0;i_left->_left ; TreeNode* node2=root->_right->_right; cout<_key<<" and the nearest ancestor of "<_key<<" is"; TreeNode* ancetor=t1.NearAncetor(root,node1,node2); if(ancetor) cout<_key <
  
 Here to test the nearest ancestor of 1, 8

Common binary tree without parent node all codes

#include using namespace std;struct NoParentTreeNode{ NoParentTreeNode* _left; NoParentTreeNode* _right ; int _key; NoParentTreeNode(const int& key) :_left(NULL) ,_right(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,key); return true;} void Inorder2() {_Inorder(_root); cout<_left,node1,node2); Node* right=NearAncetor(root->_right ,node1,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_key) {return _Insert(root ->_left,key);} else return false;} void _Inorder(Node* root) {Node* cur=root; if(cur==NULL) return; _Inorder(cur->_left); cout< _key<<" "; _Inorder(cur->_right);} Node* _root;};void test3(){ int arr[]={5,3,4,1,7,8,2,6,0, 9}; NoParentBinrayTree t1; for(int i=0;i_left->_left; NoParentTreeNode* node2=root->_right->_right->_right; NoParentTreeNode* ancetor=t1.NearAncetor(root,node1,node2 ); cout<_key<<" and the nearest ancestor of "<_key<<" is "<_key<
  
 Test here Nearest ancestor of 1, 9
 
Test code

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