Mark Allen Weiss的《數(shù)據(jù)結構與算法分析》第4章中講到二叉查找樹這種數(shù)據(jù)結構,關于刪除的代碼是這樣的:// 刪除以t為根的BST中值為x的節(jié)點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); } // 左右都有節(jié)點的情況 else if (t->left != NULL && t->right != NULL) { t->data = findMin(t->right)->data; // 右子樹最小的節(jié)點 remove(t->data, t->right); } else { BinaryNode* oldNode = t; t = (t->left != NULL) ? t->left : t->right); delete oldNode; }}二叉樹的基本性質(zhì)是節(jié)點大于其左子樹的所有節(jié)點,小于其右子樹的所有節(jié)點,在這個刪除算法中,當刪除的節(jié)點有2個兒子的情況的時候,為什么是從右子樹找出最小的節(jié)點而不是從左子樹找出最大的節(jié)點呢?
數(shù)據(jù)結構:關于二叉查找樹(BinarySearchTree)的刪除算法的疑問?
拉丁的傳說
2018-10-12 18:32:37