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個兒子的情況的時候,為什么是從右子樹找出最小的節點而不是從左子樹找出最大的節點呢?
添加回答
舉報
0/150
提交
取消