求二叉树中两个节点的最近公共祖先结点数据结构

二叉树是搜索二叉树 1、原理：二叉搜索树是排序过的，位于左子树的结点都比父结点小，位于右子树的结点都比父结点大，我们只需从根节点开始和两个输入的结点进行比较，如果当前节点的值比两个结点的值都大，那么最低的公共祖先结点一定在该结点的左子树中，下一步开遍历当前结点的左子树。如果当前节点的值比两个结点的值都小，那么最低的公共祖先结点一定在该结点的右子树中，下一步开遍历当前结点的右子树。这样从上到下找到第一个在两个输入结点的值之间的结点。
【求二叉树中两个节点的最近公共祖先结点】2、实现代码

BinaryNode* CreateBinaryTree(int* array, int length) { BinaryNode* root = new BinaryNode(array[0]); BinaryNode* pTemp = NULL; for (int idx = 1; idx < length; idx++) { BinaryNode* pCur = root; //寻找插入位置 while (pCur) { if (array[idx]_value) { pTemp = pCur; pCur = pCur->_left; } else if (array[idx]>pCur->_value) { pTemp = pCur; pCur = pCur->_right; } else return NULL; } //插入元素 pCur = new BinaryNode(array[idx]); if (array[idx] < pTemp->_value) pTemp->_left = pCur; else pTemp->_right = pCur; } return root; }//搜素二叉树寻找最近公共祖先节点 BinaryNode* AncestorTreeNode(BinaryNode* pRoot, BinaryNode* node1, BinaryNode* node2) { if (pRoot == NULL) return NULL; if (node1 == NULL) return node2; if (node2 == NULL) return node1; while (pRoot) { if (pRoot->_value > node1->_value && pRoot->_value > node2->_value) pRoot = pRoot->_left; if (pRoot->_value < node1->_value && pRoot->_value < node2->_value) pRoot = pRoot->_right; else return pRoot; } return NULL; }

测试用例：

void FunTest1() { BinaryNode* pRoot = NULL; int array[] = { 5, 2, 6 }; int length = sizeof(array) / sizeof(array[0]); pRoot = CreateBinaryTree(array, length); BinaryNode* node1 = pRoot->_left->_left; BinaryNode* node2 = pRoot->_left->_right; BinaryNode* pNode = AncestorTreeNode(pRoot, node1, node2); if (pNode) cout << pNode->_value << endl; }

二叉树节点中包含指向父节点的指针 1、原理：如果树中每个结点都有父结点（根结点除外），这个问题可以转换成求两个链表的第一个公共结点，假设树结点中指向父结点的指针是parent，树的每一个叶结点开始都由一个指针parent串起来的链表，每个链表的尾结点就是树的根结点。那么输入的这两个结点位于链表上，它们的最低公共祖先结点刚好是这两个链表的第一个公共结点。 2、实现代码

int Hight(BinaryNode* root, BinaryNode* node) { int len = 0; while (node) { len++; node = node->_parent; } return len; } BinaryNode* GetLastCommonAncestor(BinaryNode* root, BinaryNode* node1, BinaryNode* node2) { if (root == NULL || node1 == NULL || node2 == NULL) return NULL; int len1 = Hight(root, node1); //一个链表的高度 int len2 = Hight(root, node2); //另一个链表的高度 //寻找两个链表的第一个交点 while (len1 != len2) { if (len1 < len2) len2--; else len1--; } while (node1 && node2 && node1 != node2) { node1 = node1->_parent; node2 = node2->_parent; } if (node1 == node2) return node1; else return NULL; }

测试用例

void FunTest() { BinaryNode* root = new BinaryNode(1); BinaryNode* cur = root; queue q; BinaryNode* top = NULL; q.push(root); for (int i = 2; i <= 7; i++) { if (!q.empty()) { top = q.front(); if (cur == top->_left) { cur = new BinaryNode(i); top->_right = cur; cur->_parent = top; q.pop(); } else { cur = new BinaryNode(i); top->_left = cur; cur->_parent = top; } q.push(cur); } } BinaryNode* node1 = root->_left->_left; BinaryNode* node2 = root->_left->_right; BinaryNode* ancestor = GetLastCommonAncestor(root, node1, node2); if (ancestor) cout << ancestor->_value << endl; else cout << "没有公共祖先" << endl; }

二叉树是普通二叉树，没有指向父结点的指针 1、原理：在二叉树根结点的左子树和右子树中分别找输入的两个结点，如果两个结点都在左子树，遍历当前结点的左子树，如果两个结点都在右子树，遍历当前结点的右子树，直到一个在当前结点的左子树，一个在当前结点的右子树，返回当前结点就是最低的公共祖先结点。 2、实现代码

bool IsNodeInTree(BinaryNode* pRoot, BinaryNode* pNode) { if (pRoot == NULL || pNode == NULL) return false; if (pNode == pRoot) return true; if (IsNodeInTree(pRoot->_left, pNode) || IsNodeInTree(pRoot->_right, pNode)) return true; return false; } BinaryNode* GetCommonAncestor(BinaryNode* pRoot, BinaryNode* node1, BinaryNode* node2) { if (pRoot == NULL) return NULL; if (node1 == pRoot && IsNodeInTree(pRoot, node2) || node2 == pRoot && IsNodeInTree(pRoot, node1)) return pRoot; bool node1left = IsNodeInTree(pRoot->_left, node1); bool node1right = IsNodeInTree(pRoot->_right, node1); bool node2left = IsNodeInTree(pRoot->_left, node2); bool node2right = IsNodeInTree(pRoot->_right, node2); if (node1left && node2right || node1right && node2left) return pRoot; if (node1left && node2left) return GetCommonAncestor(pRoot->_left, node1, node2); if (node1right && node2right) return GetCommonAncestor(pRoot->_right, node1, node2); return NULL; }

测试用例

void FunTest3() { BinaryNode* root = new BinaryNode(1); BinaryNode* cur = root; queue q; BinaryNode* top = NULL; q.push(root); for (int i = 2; i <= 7; i++) { if (!q.empty()) { top = q.front(); if (cur == top->_left) { cur = new BinaryNode(i); top->_right = cur; cur->_parent = top; q.pop(); } else { cur = new BinaryNode(i); top->_left = cur; cur->_parent = top; } q.push(cur); } } BinaryNode* node1 = root->_left->_left; BinaryNode* node2 = root->_left->_right; BinaryNode* ancestor = GetCommonAncestor(root, node1, node2); if (ancestor) cout << ancestor->_value << endl; else cout << "没有公共祖先" << endl; }

头文件和结点的结构体

#include #include using namespace std; struct BinaryNode { BinaryNode* _left; BinaryNode* _right; BinaryNode* _parent; int _value; BinaryNode(const int& value) :_value(value) , _left(NULL) , _right(NULL) , _parent(NULL) {} };