大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这篇文章给大家介绍怎么求python二叉树中两个节点的最低公共父节点,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
在抚州等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都做网站、网站制作、成都外贸网站建设 网站设计制作定制网站建设,公司网站建设,企业网站建设,成都品牌网站建设,成都全网营销推广,外贸营销网站建设,抚州网站建设费用合理。
必须通过遍历查找一个节点的祖先集合,然后比较两个节点的祖先集合就可以找到最低的那个。这里采用后序遍历,并传入一个栈记录该节点的祖先节点。在每次访问一个节点时,先把这个节点压入栈,然后判断该节点是不是要查找的那个节点,如果是返回。接着查找它的左子树和右子树,当要查找的节点在它的左右子树中则返回。然后判断该节点与栈顶节点是否相同,是则弹出栈顶元素。这是因为相同就代表了在访问它的左右子树时没有添加新的节点,也就是说要查找的那个节点不在它的左右子树中,则该节点也就是不是要查找的节点的祖先。
#include#include using namespace std; struct BinaryTreeNode { int _data; BinaryTreeNode* _left; BinaryTreeNode* _right; BinaryTreeNode(int x) :_data(x) , _left(NULL) , _right(NULL) {} }; class BinaryTree { private: BinaryTreeNode* _root; private: void _Clear(BinaryTreeNode* root) { if (root == NULL) return; _Clear(root->_left); _Clear(root->_right); delete root; } BinaryTreeNode* _CreateBinary(int* arr, int& index, const int size) { BinaryTreeNode* ret = NULL; if (index < size&&arr[index] != '#') { ret = new BinaryTreeNode(arr[index]); ret->_left = _CreateBinary(arr, ++index, size); ret->_right = _CreateBinary(arr, ++index, size); } return ret; } BinaryTreeNode* _Find(BinaryTreeNode* root, int x) { if (root == NULL) return NULL; if (root->_data == x) return root; BinaryTreeNode* leftRet = _Find(root->_left, x); if (leftRet) return leftRet; BinaryTreeNode* rightRet = _Find(root->_right, x); return rightRet; } BinaryTreeNode* _GetPath(BinaryTreeNode* root, const BinaryTreeNode* child1, const BinaryTreeNode* child2) { if (root == NULL) return NULL; bool temp = isInclude(root, child1, child2); if (temp == false) return NULL; else { BinaryTreeNode* leftFind = _GetPath(root->_left, child1, child2); BinaryTreeNode* rightFind = _GetPath(root->_right, child1, child2); if (leftFind == NULL&&rightFind == NULL) return root; else if (leftFind == NULL&&rightFind) return rightFind; else return leftFind; } } bool isInclude(BinaryTreeNode* root, const BinaryTreeNode* child1, const BinaryTreeNode* child2) { if (root == NULL) return false; bool c1 = false, c2 = false; if (root == child1) c1 = true; if (root == child2) c2 = true; if (c1&&c2) return true; else { if (isInclude(root->_left, child1, child2)) return true; else if (isInclude(root->_right, child1, child2)) return true; else return false; } } bool _GetPathStack(BinaryTreeNode* root, BinaryTreeNode* child, stack & s) { if (root == NULL) return false; s.push(root); if (root == child) { return true; } if (_GetPathStack(root->_left, child, s)) return true; if (_GetPathStack(root->_right, child, s)) { return true; } s.pop(); return false; } public: BinaryTree() :_root(NULL) {} BinaryTree(int* arr, int size) :_root(NULL) { int index = 0; _root = _CreateBinary(arr, index, size); } ~BinaryTree() { if (_root == NULL) return; _Clear(_root); } void PostOrder_NonR() { if (_root == NULL) return; stack s; BinaryTreeNode* cur = _root; BinaryTreeNode* prev = NULL; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } BinaryTreeNode* top = s.top(); if (top->_right == NULL || prev&&prev == top->_right) { cout << top->_data << " "; prev = top; s.pop(); } else { cur = top->_right; } } cout << endl; } BinaryTreeNode* Find(int x) { return _Find(_root, x); } BinaryTreeNode* LastCommonFather(BinaryTreeNode* child1, BinaryTreeNode* child2) { if (_root == NULL || child1 == NULL || child2 == NULL) return NULL; stack s1, s2; _GetPathStack(_root, child1, s1); _GetPathStack(_root, child2, s2); int size1 = s1.size(); int size2 = s2.size(); if (size1>size2) { int dif = size1 - size2; while (dif--) { s1.pop(); } } else { int dif = size2 - size1; while (dif--) { s2.pop(); } } BinaryTreeNode* top1 = NULL; BinaryTreeNode* top2 = NULL; if (!s1.empty() && !s2.empty()) { top1 = s1.top(); top2 = s2.top(); } while (!s1.empty() && top1 != top2) { s1.pop(); top1 = s1.top(); s2.pop(); top2 = s2.top(); } return top1 == top2 ? top1 : NULL; } /*BinaryTreeNode* LastCommonFather(BinaryTreeNode* child1, BinaryTreeNode* child2) { if (_root == NULL || child1 == NULL || child2 == NULL) return NULL; return _GetPath(_root, child1, child2); }*/ }; int main() { int arr[] = { 1, 2, 4, 8, '#', '#', '#', 5, '#', 9, '#', '#', 3, 6, '#', '#', 7 }; BinaryTree bt(arr, sizeof(arr) / sizeof(arr[0])); bt.PostOrder_NonR(); /*cout << bt.Find(9)->_data << endl; if (bt.Find(0)) cout << bt.Find(0)->_data << endl;*/ if (bt.LastCommonFather(bt.Find(9), bt.Find(7))) cout << bt.LastCommonFather(bt.Find(9), bt.Find(7))->_data << endl; system("pause"); }
关于怎么求python二叉树中两个节点的最低公共父节点就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。