Cây Nhị Phân

//https://www.facebook.com/CungHocLapTrinhUIT/
#include <iostream>
#include <queue>
#include <conio.h>

using namespace std;
struct TreeNode
{
    int key;
    int value;
    TreeNode *pLeft, *pRight;
};
typedef TreeNode* TREE;
void CreateTree(TREE &Root)
{
    Root = NULL;
}
int InsertNode(TREE &Root, int key)
{
    if (Root)
    {
        if (Root->key == key)
        {
            Root->value++;
            return 0;
        }
        if (Root->key > key) return InsertNode(Root->pLeft, key);
        return InsertNode(Root->pRight, key);
    }
    TreeNode *p = new TreeNode;
    if (p == NULL) return -1;
    p->pLeft = p->pRight = NULL;
    p->key = key;
    p->value = 1;
    Root = p;
    return 1;
}
void NLR(TREE Root)
{
    if (Root)
    {
        cout << Root->key << endl;
        NLR(Root->pLeft);
        NLR(Root->pRight);
    }
}
void LNR(TREE Root)
{
    if (Root)
    {
        LNR(Root->pLeft);
        cout << Root->key << endl;
        LNR(Root->pRight);
    }
}
void LRN(TREE Root)
{
    if (Root)
    {
        LRN(Root->pLeft);
        LRN(Root->pRight);
        cout << Root->key << endl;
    }
}
int SearchNode(TREE Root, int key)
{
    if (Root)
    {
        if (Root->key == key)
            return 1;
        if (Root->key > key) return SearchNode(Root->pLeft, key);
        return SearchNode(Root->pRight, key);
    }
    return 0;
}
void DeleteTree(TREE &Root)
{
    if (Root)
    {
        DeleteTree(Root->pLeft);
        DeleteTree(Root->pRight);
        delete Root;
    }
    Root = NULL;
}
void CopyTree(TREE Root1, TREE &Root2)
{
    if (Root1)
    {
        TreeNode * p = new TreeNode;
        if (p == NULL) exit(1);
        p->pLeft = p->pRight = NULL;
        p->key = Root1->key;
        p->value = Root1->value;
        Root2 = p;
        CopyTree(Root1->pLeft, Root2->pLeft);
        CopyTree(Root1->pRight, Root2->pRight);
    }
}
void Output(TREE R)
{
    if (R)
    {
        Output(R->pRight);
        cout << R->key << "\tXuat hien: " << R->value << endl;
        Output(R->pLeft);
    }
}
int Height(TREE Root)
{
    if (!Root)
        return 0;
    int a = Height(Root->pLeft);
    int b = Height(Root->pRight);
    if (a > b) return (a + 1);
    else return (b + 1);
}
int DemNode(TREE Root)
{
    if (Root == NULL)
        return 0;
    return (1 + DemNode(Root->pLeft) + DemNode(Root->pRight));
}
void DemLa(TREE Root, int &count)
{
    if (Root)
    {
        if (Root->pLeft == NULL && Root->pRight == NULL) count++;
        DemLa(Root->pLeft, count);
        DemLa(Root->pRight, count);
    }
}
void DemNode1CayCon(TREE Root, int &count)
{
    if (Root)
    {
        if (Root->pLeft != Root->pRight && (Root->pRight == NULL || Root->pLeft == NULL)) count++;
        DemNode1CayCon(Root->pLeft, count);
        DemNode1CayCon(Root->pRight, count);
    }
}
void DemNode2CayCon(TREE Root, int &count)
{
    if (Root)
    {
        if (Root->pRight != NULL && Root->pLeft != NULL) count++;
        DemNode2CayCon(Root->pLeft, count);
        DemNode2CayCon(Root->pRight, count);
    }
}
void DemNode_Muc(TREE Root, int muc, int &count)
{
    if (Root)
    {
        if (Height(Root) == muc) count++;
        DemNode_Muc(Root->pLeft, muc, count);
        DemNode_Muc(Root->pRight, muc, count);
    }
}
int SNT(int n)
{
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return 0;
    return 1;
}
void Dem_SNT(TREE Root, int &count)
{
    if (Root)
    {
        if (SNT(Root->key)) count++;
        Dem_SNT(Root, count);
        Dem_SNT(Root, count);
    }
}
void MackDeletion(TREE &Root)
{
    TreeNode *p = Root;
    if (Root->pLeft == NULL && Root->pRight == NULL)
    {
        Root = NULL;
        delete p;
        return;
    }
    if (Root->pLeft == NULL)
    {
        Root = p->pRight;
        delete p;
        return;
    }
    if (Root->pRight == NULL)
    {
        Root = p->pLeft;
        delete p;
        return;
    }
    TreeNode *pPtr = Root->pRight;
    while (pPtr->pLeft) pPtr = pPtr->pLeft;
    pPtr->pLeft = p->pLeft;
    Root = p->pRight;
    delete p;

}
int Deletenode(TREE &Root, int x)
{
    if (Root)
    {
        if (Root->key == x)
        {
            MackDeletion(Root);
            return 1;
        }
        if (Root->key > x) return Deletenode(Root->pLeft, x);
        return Deletenode(Root->pRight, x);
    }
    return 0;
}
void Input(TREE &Root)
{
    int x;
    do
    {
        cout << "Nhap x = 0 de thoat nhap:  x = ";
        cin >> x;
        if (x == 0) break;
        InsertNode(Root, x);
    } while (1);
}
void DuyetTheoMuc(TREE &Root)
{
    TREE p = Root;
    queue<TREE> q;
    if (Root == NULL) return;
    q.push(p);
    while (!q.empty())
    {
        p = q.front();
        q.pop();
        cout << p->key << "\t";
        if (p->pLeft) q.push(p->pLeft);
        if (p->pRight) q.push(p->pRight);
    }
}

void menu()
{
    system("cls");
    cout << "1.\t Duyet cay" << endl;
    cout << "2.\t Chen Node" << endl;
    cout << "3.\t Xoa Node" << endl;
    cout << "4.\t Dem Node" << endl;
    cout << "5.\t So lan xuat hien khi chen" << endl;
    cout << "6.\t Chieu cao cay" << endl;
    cout << "7.\t Copy cay" << endl;
    cout << "8.\t Xoa cay" << endl;
    cout << "9.\t Tim Node" << endl;
    cout << "10.\t Nhap cay" << endl;
    cout << "0.\t Thoat" << endl;
    cout << "Lua Chon: ";
}
void main()
{
    TREE Root;
    CreateTree(Root);
    int x;
    int Value;
    int dem = 0;
    do
    {
        menu();
        cin >> x;
        switch (x)
        {
        case 1:
            system("cls");
            cout << "LNR:\n";
            LNR(Root);
            getch();
            system("cls");
            cout << "LRN:\n";
            LRN(Root);
            getch();
            system("cls");
            cout << "NLR:\n";
            NLR(Root);
            getch();
            break;
        case 2:
            system("cls");
            cout << "Nhap gia tri chen: ";
            cin >> Value;
            InsertNode(Root, Value);
            getch();
            break;
        case 3:
            system("cls");
            cout << "Nhap gia tri xoa: ";
            cin >> Value;
            Deletenode(Root, Value);
            getch();
            break;
        case 4:
            system("cls");
            cout << "So node: " << DemNode(Root) << endl;
            dem = 0;
            DemLa(Root, dem);
            cout << "So node la: " << dem << endl;
            dem = 0;
            DemNode1CayCon(Root, dem);
            cout << "So node 1 cay con: " << dem << endl;
            dem = 0;
            DemNode2CayCon(Root, dem);
            cout << "So node 2 cay con: " << dem << endl;
            getch();
            break;
        case 5:
            system("cls");
            Output(Root);
            getch();
            break;
        case 6:
            system("cls");
            cout << "Chieu cao cay: " << Height(Root) << endl;
            getch();
            break;
        case 7:
            system("cls");
            TREE Root2;
            CreateTree(Root2);
            CopyTree(Root, Root2);
            LNR(Root2);
            DeleteTree(Root2);
            getch();
            break;
        case 8:
            system("cls");
            DeleteTree(Root);
            getch();
            break;
        case 9:
            system("cls");
            cout << "Nhap gia tri can tim: ";
            cin >> Value;
            if (SearchNode(Root, Value)) cout << "Co gia tri " << Value << " trong cay\n";
            else cout << "Khong co gia tri " << Value << " trong cay\n";
            getch();
            break;
        case 10:
            system("cls");
            Input(Root);
            break;
        }
    } while (x != 0);
}