[問題] BST的swap
遇到的問題： (題意請描述清楚)
因為要做刪除BST節點的動作 所以希望可以把待刪除的節點
移動到external node 這樣就不用考量left child跟right child的問題(都是NULL)
題目有要求要使用qsort library，而不能用其他的方法做swap
並且有要求建立一個array of ptrs指到Tree nodes
應該是要用array來做swap吧
不過剛才測試的結果 我發現
swap ptrs array elements 並不會swap 原本的tree nodes
該如何去處理這個問題呢?
(本來想要用compare() 偷吃步直接改node中的key值 但是好像失敗了 囧)
希望得到的正確結果：
qsort a BST
程式跑出來的錯誤結果：
array 排好了
BST 原封不動
開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
codeblock in WinXP SP3
有問題的code： (請善用置底文標色功能)
qsort(array,size,sizeof(array[0]),cmp);
int cmp(const void *a,const void *b)
{
return strcmp((*(Tree**)a)->key,(*(Tree**)b)->key);
}
補充說明：
如果有需要我補充其他的code 可以請提出來 感恩
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.117.236.215
※ 編輯: l314520 來自: 122.117.236.215 (12/10 00:18)
推
12/10 00:31, , 1F
12/10 00:31, 1F
因為題目要求一定要用qsort...
→
12/10 00:32, , 2F
12/10 00:32, 2F
在交換node並且將待刪除的node刪掉後，整個排序會變動
所以我必須重新再排一次 否則這就不滿足BST的特性了
2
ˊˋ
1 3
ˋ
4
2是待刪節點 與4交換 (打錯了 囧 原本root=5不會平衡)
4
ˊˋ
1 3
再來要重排
3
ˊˋ
1 4
完成
→
12/10 00:35, , 3F
12/10 00:35, 3F
→
12/10 00:36, , 4F
12/10 00:36, 4F
對吼 忘記說
我是用inorder traversal去跑整個BST 所以是由小到大排序
※ 編輯: l314520 來自: 122.117.236.215 (12/10 01:02)
※ 編輯: l314520 來自: 122.117.236.215 (12/10 01:07)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：
1
4
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
