Description

給出一個數據序列，建立二叉排序樹，并實現刪除功能

對二叉排序樹進行中序遍歷，可以得到有序的數據序列

Input

第一行輸入t，表示有t個數據序列

第二行輸入n，表示首個序列包含n個數據

第三行輸入n個數據，都是自然數且互不相同，數據之間用空格隔開

第四行輸入m，表示要刪除m個數據

從第五行起，輸入m行，每行一個要刪除的數據，都是自然數

以此類推輸入下一個示例

Output

第一行輸出有序的數據序列，對二叉排序樹進行中序遍歷可以得到

從第二行起，輸出刪除第m個數據后的有序序列，輸出m行

以此類推輸出下一個示例的結果

Sample

#0

Input

Copy

1
6
22 33 55 66 11 44
3
66
22
77

Output

Copy

11 22 33 44 55 66 
11 22 33 44 55 
11 33 44 55 
11 33 44 55 

?

難點：

?

?1.普通的刪除：刪除的是葉子

2.刪除的是中間的節點但是只有左右子樹其中一個

3.刪除的節點是中間的節點且左右子樹都有值

?

思路：

?

?1.刪除的是葉子

直接把那個葉子刪了，不要了，就是這么大氣！！！

?

2.刪除的是中間的節點，但是只有左右子樹其中一個

直接將要刪掉的他的子樹接上去就好了

3.要刪的節點左右子樹都有值

? 我給此時的樹再加一點，有點突然，別介意
? 分為兩種情況

?1.這個要刪的節點22的左子樹11只有左子樹15沒有右子樹，

2.要刪的節點22的左子樹11不只有一個左子樹還有右子樹

tips：
1.為什么要找左子樹最大值？
? ? 因為二叉排序樹左子樹小于根，根小于右子樹，所以找左子樹最大一直向右找就行了
2.為什么20的左子樹是不是null沒有關系？
? ? 因為我們只需要拿20替換22的位置，花圈部分再比20小，也是11的右子樹的位置里，肯定比11大，所以11的右子樹直接指向花圈部分沒有問題

?

刪除節點的的部分：

? ? ? ? ?分為三個部分

1.刪除的節點左子樹為空，那就直接把這個節點的右子樹接上去
2.刪除的節點右子樹為空，那就直接把這個節點的左子樹接上去
3.刪除的節點左右子樹不為空：
? ? root為要被刪除的節點
? ? 一：root的左子樹只有一個左子樹，那就把這個節點替換要刪的節點的值，然后root的左指針指向被替換節點的左子樹，對應這張圖

? ? 二：左子樹不只有一個節點，那就找這個子樹的最大值，跟要刪的節點替換，且這個節點的父節點的右指針指向最大值的左子樹，對應這張圖

?

代碼部分：

?

1.構建二叉排序樹，可以參考我另一篇文章DS二叉排序樹之查找

? ? ?結構體：

? ?建立根：

? 剩下的元素逐個插入：

?

2.刪除元素的函數

? ? 找到要刪除的元素的節點的位置

? ? ?刪除函數remove

?

完整代碼：

#include <iostream>
#include <queue>
using namespace std;
struct treenod
{int val;treenod* left, * right;//左右子樹指針treenod(){left = NULL;right = NULL;}treenod(int x){val = x;left = NULL;right = NULL;}
};
queue<int>ss;//隊列用來存要建樹的值
void insert(treenod*& root, int num)///元素逐個插入
{if (root == NULL)//遇到空就插入{root = new treenod(num);}if (num < root->val)//插入的值比這個節點小就往左子樹繼續走{insert(root->left, num);}if (num > root->val)//插入的值比這個節點小就往右子樹繼續走{insert(root->right, num);}
}
treenod* buildtree()//建樹
{if (ss.empty())return NULL;treenod* root;root = new treenod(ss.front());//先建立根ss.pop();while (!ss.empty()){insert(root, ss.front());//剩下的元素都一個一個插入ss.pop();}return root;
}
void zhonxu(treenod* root)
{if (root == NULL)return;zhonxu(root->left);cout << root->val << " ";zhonxu(root->right);
}
void remove(treenod*& root)//root是要刪除的節點
{if (root->right == NULL)//要刪的節點只有一個左子樹{root = root->left;return;}if (root->left == NULL)//要刪的節點只有一個右子樹{root = root->right;return;}//要刪的節點存在左右子樹treenod* p = root->left;treenod* pre = root;//可以記為要刪除的節點的父節點while (p->right != NULL){pre = p;            //pre可以理解為最大值的父節點p = p->right;       //向右子樹走找最大值}if (pre == root)//說明要刪的節點左子樹只有一個左分支，沒有右分支{root->val = p->val;//要刪除的節點的值＝p的值root->left = p->left;//且這個被刪節點的左子樹要指向，p的左子樹delete p;return;}root->val = p->val;//說明要刪的節點的左子樹有右子樹，有右分支，root＝root的左子樹里的最大值pre->right = p->left;//最大值的父節點的右子樹指向最大值的左子樹delete p;return;
}
void removeItem(treenod*& root, int num)//根節點和要刪除的值
{if (root == NULL)//如果遇到空節點說明不存在這個值的節點，不用刪除return;if (root->val == num)//說明存在這個值的節點，刪除{remove(root);//調用刪除函數return;}if (root->val > num)//如果要刪除的值小于這個節點的值，向左子樹走{removeItem(root->left, num);}if (root->val < num)//如果要刪除的值大于這個節點的值，向右子樹走{removeItem(root->right, num);}
}int main()
{int t;cin >> t;while (t--){int n;cin >> n;for (int i = 1; i <= n; i++){int num;cin >> num;ss.push(num);}treenod* root;root = buildtree();zhonxu(root);cout << endl;int m;cin >> m;for (int i = 1; i <= m; i++){int num;cin >> num;removeItem(root, num);zhonxu(root);cout << endl;}}return 0;
}

偷懶下，主函數不想打注釋了，也不長，有讀題的都知道在干嘛

---

這周估計就更這個吧，因為要備考四級了，而且我也不是大佬，后面的題還不太會，等我慢慢學吧！！！
不要催更，不要催更，不要催更！！！
祝我四級不要再421分好吧有緣人。

我祝你六級輕松拿下600分！！！

?