BTREE_FULL

#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>

// Khai báo
struct TNode
{
    int Info;
    TNode *Left;
    TNode *Right;
};

struct BTree
{
    TNode *Root;
};

// Khời tạo
void InitBTree(BTree &bt)
{
    bt.Root = NULL;
}

// Tạo TNode
TNode *CreateTNode(int data)
{
    TNode *p = new TNode();
    if(!p)
    {
        printf("\nMemory low");
        getch();
        return NULL;
    }

    p ->Info = data;
    p ->Left = NULL;
    p ->Right = NULL;

    return p;
}

// Show TNode
void ShowTNode(TNode *p)
{
    printf("%d ", p ->Info);
}

// Thêm TNode p vào Tree
int InsertTNode(TNode *&root, TNode *p)
{
    // Kiểm tra bộ nhớ
    if(!p)
        return 0;

    // Nếu gốc rỗng
    if(!root)
    {
        root = p;
        return 1;
    }

    // trùng
    if(root ->Info == p ->Info)
        return 0;
    if(p ->Info < root ->Info)
        InsertTNode(root -> Left, p); // thêm vào trái
    else
        InsertTNode(root -> Right, p);
    return 1;
}

void CreateAuToBTree(BTree &bt, int n)
{
    int data;
    InitBTree(bt);
    srand((unsigned)time(NULL));
    for(int i = 0; i < n; i++)
    {
        data = rand() % 100;
        TNode *p = CreateTNode(data);
        InsertTNode(bt.Root, p);
    }
}

void NLR(TNode *p)
{
    if(!p)
        return;
    printf("%d ", p ->Info);
    NLR(p ->Left);
    NLR(p ->Right);
}

void LNR(TNode *root)
{
    if(!root)
        return;
    LNR(root -> Left);
    printf("%d ", root ->Info);
    LNR(root -> Right);
}

int IsLeaf(TNode *root)
{
    if(root ->Left || root ->Right)
        return 0;
    return 1;
}

// Đếm số Node
int CountNode(TNode *root)
{
    if(!root)
        return 0;
    int nl = CountNode(root -> Left);
    int nr = CountNode(root -> Right);

    return (1 + nl + nr);
}

// Đếm số nút lá
int CountNodeLeaf(TNode *root)
{
    if(!root)
        return 0;
    if(!root -> Left && !root -> Right) // nếu là lá
        return 1;
    int nl = CountNodeLeaf(root -> Left);
    int nr = CountNodeLeaf(root -> Right);

    return (nl + nr);
}


int CountNodeLeaf_v2(TNode *root)
{
    if(!root)
        return 0;

    int nl = CountNodeLeaf(root -> Left);
    int nr = CountNodeLeaf(root -> Right);

    if(!root -> Left && !root -> Right) // nếu là lá
        return (1 + nl + nr);
    return (nl + nr);
}

// đếm nút trung gian
int CountNodeMedium(TNode *root)
{
    if(!root)
        return 0;
    if(!root -> Left && !root -> Right) // nếu là lá
        return 0;
    int nl = CountNodeMedium(root -> Left);
    int nr = CountNodeMedium(root -> Right);

    return (1 + nl + nr);
}

// đếm nút có 2 con
int CountNodeHaveTwoChild(TNode *root)
{
    if(!root)
        return 0;
    if(!root ->Left || !root -> Right)
        return 0;
    int nl = CountNodeHaveTwoChild(root -> Left);
    int nr = CountNodeHaveTwoChild(root ->Right);

    return (1 + nl + nr);
}

// đếm nút có 2 con ver 2
int CountNodeHaveTwoChild_v2(TNode *root)
{
    if(!root)
        return 0;

    int nl = CountNodeHaveTwoChild_v2(root ->Left);
    int nr = CountNodeHaveTwoChild_v2(root ->Right);

    if(root ->Left && root ->Right)
        return (1 + nl + nr);
    return nl + nr;
}

// Đếm nút chỉ có 1 con
int CountNodeHaveOnceChild(TNode *root)
{
    if(!root)
        return 0;
    int nl = CountNodeHaveOnceChild(root -> Left);
    int nr = CountNodeHaveOnceChild(root -> Right);

    if(!root -> Left && root -> Right || root -> Left && !root -> Right)
        return (1 + nl + nr);
    return nl + nr;
}


// tính tổng các Node
int SumAllnode(TNode *root)
{
    if(!root)
        return 0;
    int suml = SumAllnode(root ->Left);
    int sumr = SumAllnode(root ->Right);

    return (root ->Info + suml + sumr);
}

// Kiểm tra 1 nút có phải là nút lá


// Đếm nút con là nút lá
int CountNodeHaveChildIsLeaf(TNode *root)
{
    if(!root)
        return 0;

    int nl = CountNodeHaveChildIsLeaf(root -> Left);
    int nr = CountNodeHaveChildIsLeaf(root -> Right);

    if(IsLeaf(root ->Left) || IsLeaf(root ->Right))
        return (1 + nl + nr);
    return (nl + nr);
}

int CalHightTree(TNode *root)
{
    if(!root)
        return 0;
    int hl = CalHightTree(root -> Left);
    int hr = CalHightTree(root ->Right);

    if(hl > hr)
        return 1 + hl;
    return 1 + hr;
}

// Tìm Node lớn nhất
int NodeMax(TNode *root)
{
    TNode *p = root;
    while(p -> Right)
        p = p -> Right;
    return p -> Info;
}

int SumOfTree(TNode *root)
{
    if(!root)
        return 0;
    int sl = SumOfTree(root ->Left);
    int sr = SumOfTree(root ->Right);

    return (root ->Info + sl + sr);
}

// Xuất ra màn hình các nút ở mức K
void ShowNodeOfLevelK(TNode *root, int k)
{
    if(!root)
        return;
    k--;
    ShowNodeOfLevelK(root -> Left, k);
    ShowNodeOfLevelK(root ->Right, k);

    if(k == 0)
        printf("%d ", root -> Info);
}

// Xuất ra màn hình các nút lá ở mức k
void ShowNodeLeafOfLvK(TNode *root, int k)
{
    if(!root)
        return;
    k--;
    ShowNodeLeafOfLvK(root ->Left, k);
    ShowNodeLeafOfLvK(root -> Right, k);

    if(k == 0 && (!root -> Left && !root ->Right))
        printf("%d ", root ->Info);
}

int CountNodeOfLvK(TNode *root, int k)
{
    if(!root)
        return 0;
    k--;
    int cl = CountNodeOfLvK(root ->Left, k);
    int cr = CountNodeOfLvK(root ->Right, k);

    if(k == 0)
        return (1 + cl + cr); // mỗi lần tìm thấy tăng lên 1.
    return cl + cr; // ngược lại vẫn tiếp tiếp đếm cl, cr.
}

// Đếm Node ở mức k
int CountNodeLeafOfLVK(TNode *root, int k)
{
    if(!root)
        return 0;
    k--;
    int cl = CountNodeLeafOfLVK(root ->Left, k);
    int cr = CountNodeLeafOfLVK(root ->Right, k);

    if(k == 0 && !root ->Left && !root ->Right)
        return (1 + cl + cr);
    return (cl + cr);
}

int SumNodeLeafOfLVK(TNode *root, int k)
{
    if(!root)
        return 0;
    k--;
    int sl = SumNodeLeafOfLVK(root ->Left, k);
    int sr = SumNodeLeafOfLVK(root ->Right, k);

    if(k == 0 && !root ->Left && !root ->Right)
        return (root ->Info + sl + sr);
    return sl + sr;
}

int TimNutCoGiatriGanXNhat(TNode *root, int x)
{
    if(!root)
        return 0;

    int min = root ->Info;
    int mindis = abs(x - min); // khoảng cách nhỏ nhất
    while(root)
    {
        if(root ->Info == x)
            return x;
        if(abs(x - root ->Info) < mindis)
        {
            min = root ->Info;
            mindis = abs(x - min);
        }
        if(x > root ->Info)
            root = root ->Right;
        else
            root = root ->Left;
    }
    return min;
}

void InRaNutCoChieuCao_Trai_3(TNode *root, int k)
{
    if(!root)
        return;
    k--;
    InRaNutCoChieuCao_Trai_3(root -> Left, k);
    if(k == 0)
        printf("%d ", root -> Info);
}

void InRaNutCoGiaTri_le_Co1Child(TNode *root)
{
    if(!root)
        return;
    InRaNutCoGiaTri_le_Co1Child(root ->Left);
    InRaNutCoGiaTri_le_Co1Child(root ->Right);

    if(root ->Info % 2 && (root ->Left || root ->Right))
        printf("%d ", root ->Info);
}

int main()
{
    int n;
    do{
        printf("\nNhap vao so nut cua cay: ");
        scanf("%d", &n);
    }while(n < 0);

    BTree bt;
    CreateAuToBTree(bt, n);
    printf("\nShow list: ");
    NLR(bt.Root);


    int child = CountNodeHaveTwoChild(bt.Root);
    printf("\nCount node have two child: %d", child);

    int sum = SumAllnode(bt.Root);
    printf("\nSum all Node: %d", sum);

    int node_count = CountNode(bt.Root);
    printf("\nNode had been count:  %d", node_count);

    int leaf_count = CountNodeLeaf(bt.Root);
    printf("\nLeaf had been count:  %d", leaf_count);



    int nodemedium_count = CountNodeMedium(bt.Root);
    printf("\nMedium Node had been count:  %d", nodemedium_count);

    //int childisleaf_cout = CountNodeHaveChildIsLeaf(bt.Root);
    //  printf("\nChild is Leaf Node had been count:  %d", childisleaf_cout);

    int hight_tree = CalHightTree(bt.Root);
    printf("\nHight of tree: %d", hight_tree);

    printf("\nNut co chieu cao trai la 3: ");
    InRaNutCoChieuCao_Trai_3(bt.Root, 3);

    printf("\nIn ra nut co gia tri le co it nhat 1 con: ");
    InRaNutCoGiaTri_le_Co1Child(bt.Root);

    int k;
    do
    {
        printf("\nNhap vao chieu cao: ");
        scanf("%d", &k);
        printf("\nShow node level k = %d: ", k);
        ShowNodeOfLevelK(bt.Root, k);


        int count_lvk = CountNodeOfLvK(bt.Root, k);
        printf("\nCount node of level k = %d: %d", k, count_lvk);

    }while(k != 0);




    getch();
    return 0;
}