Re: [理工] [資結]-交大97-資訊聯招

[feather585 (殤丞)]

還有幾個問題想問一下

3. (2)

我的答案是這樣

bool check(node *root)
{
        if(root == NULL)
                return true;

        if(root->left == NULL)
                return true;
        if(root->value > root->left->value)
                return false;

        if(root->right == NULL)
                return true;
        if(root->value > root->right->value)
                return false;

        return check(root->left) && check(root->right);
}

不知道這樣正不正確

4. (7)

爬文之後

還是搞不懂題目中的 weight-balance condition 到底是什麼意思



感謝幫忙

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.121.101
→ ybite:3(2):很顯然不對。return不是這樣用的。
→ ybite:4(7): 我對這題充滿問號。
→ ybite:更正一下一樓的講法：Root 6 左空 右9的情況下會出錯。
→ ybite:...等等，搞懂了，錯不在這邊。
→ ybite:3(2)我的答案https://gist.github.com/c5a9d90f3d4710a6b8d5
→ ybite:希望是對的，歡迎挑錯。
→ BenLinus:樓上的code leftHeight 值傳回來一直都0耶...
→ ybite:果然有錯 XDDDDDD 最後Return時應該要加一 囧 請重整頁面
→ feather585:所以我的方法錯在忘記要確定BT是complete
→ feather585:但要確定BT是complete不只要左右子樹高度相同或差1吧?
→ BenLinus:樓上說對了XD
例:
     ○
    ／＼
   ○  ○
  ／  ／
 ○  ○
※ 編輯: feather585      來自: 140.113.121.101      (02/11 16:04)
→ ybite:好反例！ Q_______Q 有什麼解決方法嗎？
→ ybite:一個直覺想到的方法是把所有對Height的檢查都拿掉
→ ybite:然後依序把樹中擁有同樣Depth節點的數字記錄下來
→ ybite:如果1,2,...,n-1 Depth中有有數量不到1,2,...2^(n-2)者就錯
→ feather585:我覺得沒有指向sibling的pointer
→ feather585:要寫出確定complete的程式好像蠻困難的
→ sneak: 但要確定BT是comp https://daxiv.com