Question:
Find the minimum larger node in binary search tree for a giving node.
Answer:
struct BSTreeNode {
BSTreeNode* pLeft;
BSTreeNode* pRight;
BSTreeNode* pParent;
int value;
};
BSTreeNode* findMinLarge(BSTreeNode* node) {
if (!node)
return 0;
if (Node* result = node->pRight) {
while (result && result->pLeft) {
result = result->pLeft;
}
return result;
}
if (node->pParent == 0) {
return 0;
}
if (node->pParent->pLeft == node)
return node->pParent;
BSTreeNode* parent = node->pParent;
BSTreeNode* pparent = parent->pParent;
while (1) {
if (pparent && pparent->pLeft == parent) {
return pparent;
}
if (!pparent)
break;
parent = pparent;
pparent = parent->pParent;
}
return 0;
}
Find the minimum larger node in binary search tree for a giving node.
Answer:
struct BSTreeNode {
BSTreeNode* pLeft;
BSTreeNode* pRight;
BSTreeNode* pParent;
int value;
};
BSTreeNode* findMinLarge(BSTreeNode* node) {
if (!node)
return 0;
if (Node* result = node->pRight) {
while (result && result->pLeft) {
result = result->pLeft;
}
return result;
}
if (node->pParent == 0) {
return 0;
}
if (node->pParent->pLeft == node)
return node->pParent;
BSTreeNode* parent = node->pParent;
BSTreeNode* pparent = parent->pParent;
while (1) {
if (pparent && pparent->pLeft == parent) {
return pparent;
}
if (!pparent)
break;
parent = pparent;
pparent = parent->pParent;
}
return 0;
}
No comments:
Post a Comment