Tree traversal

對於一顆在tree上的node而言, 不管他有多少個children, 我們總會希望用一些方法來取得或是找到他底下所有的node, 這時traversal的方法就出現了, 但是在一個binary tree裡我們常看到pre-order, in-order及post-order, 這些方法我們都學過, 一但到了一個node有多個children時怎麼辦呢?

這個問題源自於工作上的需求, 這個tree還是一個可以回溯找parent的, 也就是他是一個double linked tree, 雖然這link的方法無礙於我們訪問這個tree, 但有時遇到要訪問同一層level的node時,這時非常的好用...

演算法如下,

void InOrder(TreeNode* pNode) {
    if(pNode != NULL) {
        InOrder(pNode->left);
        cout << pNode->data;
        InOrder(pNode->right);
    }
}

void PreOrder(TreeNode* pNode) {
    if(pNode != NULL) {
        cout << pNode->data;
        PreOrder(pNode->left);
        PreOrder(pNode->right);
    }
}

void PostOrder(TreeNode* pNode) {
    if(pNode != NULL) {
        PostOrder(pNode->left);
        PostOrder(pNode->right);
        cout << pNode->data;
    }
}

void LevelOrder(TreeNode* pNode) {
    if(pNode != NULL) {
        TreeNode* pTmpNode = pNode;
        AddToQueue(pTmpNode);
        while(pTmpNode != NULL) {
            pTmp = DeQueue();
            cout << pTmpNode->data;
            AddToQueue(pTmpNode->left);
            AddToQueue(pTmpNode->right);
        }
    }
}

這樣一來就完成了, 當然如果一個node不只有left, right兩個children, 那就自己implement一個get next child吧, 如此一來, 就完成了...

ノルウェイの森

這本小說出來23年了, 早在14年前高一時, 就看過這本小說, 當時看不懂, 後來再看一次是在書店裡, 雖然懂了, 但其實沒有很深入的去了解作者想表達的是什麼。

直到上星期, 這部小說搬上了大螢幕, 很多人總認為這部電影拍的沒有小說寫得好...雖然我還沒看過電影, 但我想我能理解為何一堆人都說拍的不好, 或是看不懂...

 

其實要理解一本小說最好的方法, 就是去理解作者寫小說的那個年代, 到底發生了什麼大事, 小說裡的年代是被設置在1960年代晚期, 那時日本剛剛戰敗, 當時日本各大學罷課頻頻發生, 很像早一點中國發生的學運, 大學生不唸書, 一天到晚搞活動, 而主角和第一位女主角都不喜歡這樣子的活動, 所以他們孤立於人群之外。當然這部小說是主角的回憶, 所以有時在看時, 會覺得不太連續, 而這也是作者希望讀者多看幾次的關係, 才會用這樣的手法寫小說, 因為插述寫法的小說, 沒有一定功力, 是寫不出來的...

 

書裡面談到很多的生死(主角的朋友, 以及直子都是自殺身亡), 直到後來小綠用開心活潑感動了主角, 其實在面對人生時, 很多人會選擇像是直子的憂鬱來面對, 而不是像小綠一樣的樂觀活潑, 就算小綠和家人的關係再不好, 在小綠的父母重病時, 他還是一樣照顧著他們, 很多人說這一點是矛盾的, 我倒覺得小綠是唯一看懂人生的人..

 

每每談到自殺, 書裡自殺的人物還真是不少, 但這也是作者想強調的, 在那個年代裡, 人們的心理是多麼的不健全, 傳統到全新的流行, 到處充滿著矛盾, 那時沒有人知道什麼是未來, 未來有什麼, 曾有很多人和我說, 這本小說裡充滿了性愛的場景, 其實這些人還是不懂作者想表達的是什麼...

 

感情, 性, 生死..正是作者認為人生最快樂及最苦惱的事, 全是因為這些, 所以作者才會寫下"死並不是終結生的決定性要素。在那裏死只不過是構成生的許多要素之一。"這不正是作者最深刻的體會嗎?

 

"沒有什麼人喜歡孤獨的，只是不勉強交朋友而已，因為就算那樣做也只有失望而已。"

為什麼會說出這句話, 那不正是時下年輕人最常做的一件事, 交多一點朋友來填滿自己人生的空白, 後來才發現原來連自已都不認識, 認識到的只是一群能填滿你時間的朋友, 而不是填滿你的人生, 讓你的人生變得更有義!!

 

我最記得的一幕是小綠說把蛋糕丟到窗外的事, 為什麼會這麼清楚, 因為人, 常有不同的想法, 很有可能前一秒就和下一秒完全不同, 而這也是人生最重要的轉折處, 你說小綠說出這些話來之前, 他心裡想的是什麼呢?人生常會因為一個忽然來的意外而有所改變, 小綠明白, 但看書的人又有多少人懂呢?

 

電影拍得沒有小說好, 應該說村上大師寫作的手法很難讓電影能夠比他好, 所以看完電影不懂的人, 回過頭再看看小說吧, 也許這本書年代久遠, 跟不上潮流了, 但回過頭去看看那些年代的人, 其實現代的人並不見得活得比他們快樂...

 

用OO思考加減乘除的作法!?

在OO的世界裡, 什麼都能用Object來實現, 但也許會有人說, 下面的程式很好

 

int main() {
    int a = 0, b = 0;
    char op = 0;
    cout << "Please input the operation: +, -, *, /" << endl;
    cin >> op;
    cout << "Please input the first number ==> ";
    cin >> a;
    cout << "Please input the second number ==>";
    cin >> b;

    int result = 0;
    if(op == '+') {
        result = a+b;
    } else if(op == '-') {
        result = a-b;
    } else if(op == '*') {
        result = a*b;
    } else if(op == '/') {
        result = a/b;
    } else {
        // error!!
    }
    cout << "Result: " << result << endl;
}

很好, 這程式其實沒什麼大問題, 而且寫得很清楚(因為是我寫的!!XD), 但..沒有錯的程式就代表是好程式嗎?在以前可能是, 因為這code好懂又沒錯, 直到OO世界之後, 這樣的code不但不好, 而且充滿了不可知的後果!!為什麼說不可知呢??如

試想一下, 這時只果我想再加入一個operation時怎麼做, 就叫做%好了, 取出果個除數的餘數, 這時要改動的code有多少呢?

想一下好像又不難, 在if else再加一個就好了不是嗎??對, 這是其中之一的解答, 但確不是最好的解答..如果你是一個OOP的程式設計師, 你肯定馬上就發現這樣的修改太麻煩了..所以你會這麼寫..

class IOperation abstract {
public:
    virtual double GetResult() = 0;
    void SetNum1(double num1) {
    m_dNum1 = num1;
}
    void SetNum2(double num2) {
    m_dNum2 = num2;
}
protected:
    double m_dResult;
    double m_dNum1;
    double m_dNum2;
};

寫到此, 大概也就知道+有自己的兩個元素, -也有, /也有, *也有, 所以要再加一個%也不是什麼難事, 只要繼承就好, 所以, 再簡單的程式, 也有可以使用OOD的地方, 別再小看OO了, 另外這個方法, 其實也是design pattern裡的工廠模式, 只要有一個factory, 就可以create出任何的+-*/方法, 這樣一來對於client, 他只要input 三個東西, 就可以得到結果, 不用去考慮裡面的實作..也算是一種很好的應用...