/********************************************************************
    created:    2011/05/26        12:13
    filename:     BSTree2DuLink.h
    file base:    BSTree2DuLink
    file ext:    h
    author:        WT@CHINA
    
    purpose:    把二元查找樹轉變成排序的雙向鏈表

    題目：
    輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。
    要求不能創建任何新的結點，只調整指針的指向。
        10
        / \
      6    14
     / \   / \
    4   8 12 16
    轉換成雙向鏈表
    4=6=8=10=12=14=16。

    首先我們定義的二元查找樹 節點的數據結構如下：
    struct BSTreeNode
    {
    int m_nValue; // value of node
    BSTreeNode *m_pLeft; // left child of node
    BSTreeNode *m_pRight; // right child of node
    };
*********************************************************************/
#include <iostream>
using namespace std;

struct BSTreeNode
{
    int m_nValue; // value of node
    BSTreeNode *m_pLeft; // left child of node
    BSTreeNode *m_pRight; // right child of node
};

void BSTree2DuLink(BSTreeNode* pNode, BSTreeNode* pLeft, BSTreeNode* pRight)
{
    if (pNode->m_pLeft != NULL) {
        BSTree2DuLink(pNode->m_pLeft, pLeft, pNode);
    } else {
        if (pLeft != NULL) {
            pNode->m_pLeft = pLeft;
            pLeft->m_pRight = pNode;
        }
    }

    if (pNode->m_pRight != NULL) {
        BSTree2DuLink(pNode->m_pRight, pNode, pRight);
    } else {
        if (pRight != NULL) {
            pNode->m_pRight = pRight;
            pRight->m_pLeft = pNode;
        }
    }
}

void Test_BSTree2DuLink()
{
    // init tree
    BSTreeNode node4; node4.m_nValue = 4; node4.m_pLeft = NULL; node4.m_pRight = NULL;
    BSTreeNode node8; node8.m_nValue = 8; node8.m_pLeft = NULL; node8.m_pRight = NULL;
    BSTreeNode node6; node6.m_nValue = 6; node6.m_pLeft = &node4; node6.m_pRight = &node8;

    BSTreeNode node12; node12.m_nValue = 12; node12.m_pLeft = NULL; node12.m_pRight = NULL;
    BSTreeNode node16; node16.m_nValue = 16; node16.m_pLeft = NULL; node16.m_pRight = NULL;
    BSTreeNode node14; node14.m_nValue = 14; node14.m_pLeft = &node12; node14.m_pRight = &node16;

    BSTreeNode root; root.m_nValue = 10; root.m_pLeft = &node6; root.m_pRight = &node14;
    
    // convert BSTree to DuLink
    BSTree2DuLink(&root, NULL, NULL);

    // console out the double link list
    BSTreeNode* p = &root;
    while(p->m_pLeft != NULL) p = p->m_pLeft;
    while(p != NULL)
    {
        cout<<p->m_nValue<<"  ";
        p = p->m_pRight;
    }
    
}