// Tree1.cpp
#include <iostream.h>
#include <iomanip.h>

// 二分木のノード
struct SNode
{
    int    value;     // 値
    SNode* pNext[2];  // 子ノード
};

// 二分木
struct STree
{
    int    value;  // 値
    SNode* pRoot;  // ルート
};

// 初期化処理
void InitTree(STree* pTree);
void InitNode(SNode* pNode);

// キーのビット数
const unsigned KEY_BITS = sizeof (unsigned) * 8;
// 最上位ビット
const unsigned TOP_BIT  = 1 << (KEY_BITS - 1);

// ノードを追加
void AddNode(STree* pTree, unsigned key, int value);
// ノードを追加（再帰サブルーチン）
SNode* Rec_AddNode(SNode** ppParent, unsigned key, int nBit);

// 木を削除
void FreeNode(STree* pTree);
// 木を削除（再帰サブルーチン）
void Rec_FreeNode(SNode* pParent);

// 木全体を表示
void DispTree(STree* pTree);
// 木全体を表示（再帰サブルーチン）
void Rec_DispTree(SNode* pParent, int nDepth);

// データ入力
bool Input(STree* pTree);

int main()
{
    STree tree;

    InitTree(&tree);
    while(Input(&tree));
    DispTree(&tree);

    return 0;
}

// 木の初期化
void InitTree(STree* pTree)
{
    pTree->value = 0;
    pTree->pRoot = NULL;
}

// ノードの初期化
void InitNode(SNode* pNode)
{
    pNode->value = 0;
    pNode->pNext[0] = NULL;
    pNode->pNext[1] = NULL;
}

// ノードを追加
void AddNode(STree* pRoot, unsigned key, int value)
{
    // ０の場合
    if(key == 0)
    {
        pRoot->value = value;
        return;
    }

    int nBit;  // ビット番号

    // 最上位ビットに「１」を持ってきます
    for(nBit = KEY_BITS - 1; (key & TOP_BIT) == 0; nBit--)
        key <<= 1;

    // 
    SNode* pAdd = Rec_AddNode(&pRoot->pRoot, key, nBit);
    if(pAdd != NULL)
        pAdd->value = value;
}

// ノードを追加（再帰サブルーチン）
// 戻り値は追加された要素のアドレスです
SNode* Rec_AddNode(SNode** ppParent, unsigned key, int nBit)
{
    // 要素の確保
    if(*ppParent == NULL)
    {
        *ppParent = new SNode;
        if(*ppParent == NULL)
            return NULL;
        InitNode(*ppParent);
    }

    // 追加した要素のアドレスを返します
    if(nBit == 0)
        return *ppParent;

    key <<= 1;
    SNode** ppNext = &(*ppParent)->pNext[(key & TOP_BIT) != 0];

    // 次のノードへ
    return Rec_AddNode(ppNext, key, nBit - 1);
}

// 木を削除
void FreeNode(STree* pTree)
{
    if(pTree->pRoot != NULL)
        Rec_FreeNode(pTree->pRoot);
}

// 木を削除（再帰サブルーチン）
void Rec_FreeNode(SNode* pParent)
{
    int i;
    for(i = 0; i < 2; i++)
    {
        SNode* pNext = pParent->pNext[i];
        if(pNext != NULL)
            Rec_FreeNode(pNext);  // 子以降を削除します
    }
    delete pParent;  // 最後に自分を削除します
}

// 木全体を表示
void DispTree(STree* pTree)
{
    cout << pTree->value << endl;
    Rec_DispTree(pTree->pRoot, 0);
}

// 木全体を表示（再帰サブルーチン）
void Rec_DispTree(SNode* pParent, int nDepth)
{
    if(pParent == NULL)
        return;

    int i;

    // setw で表示幅を指定できます
    // iomanip.h をインクルードしてから使います
    cout << setw(nDepth * 2) << "" << pParent->value << endl;
    for(i = 0; i < 2; i++)
        Rec_DispTree(pParent->pNext[i], nDepth + 1);
}

// データ入力
bool Input(STree* pTree)
{
    unsigned key;
    int      value;

    cout << "数値を２つ入力して下さい > " << flush;
    cin >> key >> value;

    if(value == -1)
        return false;

    AddNode(pTree, key, value);
    return true;
}

数値を２つ入力して下さい > 1 1
数値を２つ入力して下さい > 2 2
数値を２つ入力して下さい > 3 3
数値を２つ入力して下さい > 5 4
数値を２つ入力して下さい > 6 5
数値を２つ入力して下さい > 7 6
数値を２つ入力して下さい > 12 7
数値を２つ入力して下さい > 0 -1
0:0
  2
    4
1
      7
    5
  3
    6