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吧, 如此一來, 就完成了...