Mark Allen Weiss的《数据结构与算法分析》第4章中讲到二叉查找树这种数据结构,关于删除的代码是这样的:
// 删除以t为根的BST中值为x的节点void remove(int x, BinaryNode*& t){ if ( t == NULL) { return ; } if (x < t->data) { remove(x, t->left); } else if (x > t->data) { remove(x, t->right); } // 左右都有节点的情况 else if (t->left != NULL && t->right != NULL) { t->data = findMin(t->right)->data; // 右子树最小的节点 remove(t->data, t->right); } else { BinaryNode* oldNode = t; t = (t->left != NULL) ? t->left : t->right); delete oldNode; }}
二叉树的基本性质是节点大于其左子树的所有节点,小于其右子树的所有节点,
在这个删除算法中,当删除的节点有2个儿子的情况的时候,为什么是从右子树找出最小的节点而不是从左子树找出最大的节点呢?
解决方案
都可以,二叉搜索树删除拥有左右子树节点的时候,既可以用左子树的最右节点来替代,也可以用右子树的最左节点来替代。书中的例子应该是刚好用到了其中的一种情况。