main.cpp

#include <iostream>
#include "Ksort/BubbleSort.h"
#include "Ksort/QuickSort.h"
#include "Ksort/InsertSort.h"
//#include "Ksort/ShellSort.h"
#include "Ksort/SelectionsSort.h"
#include "Ksort/HeapSort.h"
#include "Ksort/MergeSort.h"
#include "BinaryTree/BinaryTree.h"
#include "BinaryTree/BinaryTreeUtils.h"
#include "BinaryTree/AVLTree/AVLTreeUtils.h"
#include "BinaryTree/BRTree/BRtreeHelper.h"
#include <ctime>
#include <stdlib.h>


vector<int> getRandom(int total)
{

   // srand((int)time(NULL));
    std::vector<int> input = *new std::vector<int>();
    for (int i = 0; i < total; i++) {
        input.push_back(i);
    }
    vector<int> output = *new vector<int>();

    int end = total;
    for (int i = 0; i < total; i++) {
        vector<int>::iterator iter = input.begin();
        int num = rand()%end;
        iter = iter+num;
        cout<<"生成随机数"<< i +1<<":" <<*iter<<endl ;
        output.push_back(*iter);
        input.erase(iter);
        end--;
    }

    return output;
}
void BRtreeTest(){
    int MMM = 10000 ;
    cout <<"红黑随机数测试"<<endl;
    vector<int> output = getRandom(MMM);
    BRtree  yy = NULL ;
    for (int i = 0; i < MMM; ++i) {
        cout<<"插入数据"<< i +1<<":"<< output.at(i)<<endl ;
        insertBRTree(yy , output.at(i));
        logInOrderAVL(yy);
    }

    vector<int> output1 = getRandom(MMM);

    for (int i = 0; i < MMM; ++i) {
        cout<<"删除"<< i +1<<":"<< output1.at(i)<<endl ;
        if( i ==16){
            cout<<"debug"<<endl;
        }
        deleteBRTree(yy , output1.at(i));
        logInOrderAVL(yy);
        cout<<endl;
    }
}





int main(int argc, const char *argv[]) {
    int ints[10] = {99, 456, 85, 216, 579, 464, 156, 416, 15, 86};

    // int  ints1[10]= {479, 99 ,86, 77, 156, 216, 416, 456, 464, 478 };
    BubbleSort sort;
    sort.log(ints, 10);
    cout << "冒泡排序:" << endl;
    sort.sort(ints, 10);
    sort.log(ints, 10);

    QuickSort qSort;
    cout << "快速排序:" << endl;
    qSort.sort(ints, 10);
    qSort.log(ints, 10);

    InsertSort iSort;
    cout << "插入排序:" << endl;
    iSort.sort(ints, 10);
    iSort.log(ints, 10);

    //    int ints4[10]= {99,456,85,216,579,464,156,416,15,86};
    //    ShellSort sSort;
    //    cout<<"希尔排序:"<<endl;
    //    sSort.sort(ints4, 10);
    //    sSort.log(ints4, 10);

    SelectionSort sSort;
    cout << "选择排序:" << endl;
    sSort.sort(ints, 10);
    sSort.log(ints, 10);

    HeapSort hSort;
    cout << "堆  排序:" << endl;
    hSort.sort(ints, 10);
    hSort.log(ints, 10);

    //99 456 85 216 464 579 156 416 15 86 11
    MergeSort mSort;
    cout << "归并排序:" << endl;
    mSort.sort(ints, 10);
    mSort.log(ints, 10);

    cout << "二叉树:" << endl;
    BinaryTree tree = buildTree(ints, 10);
    cout << "层次遍历:" << endl;
    logLevel(tree);
    cout << "前序遍历(递归):" << endl;
    _logPreOrder(tree);
    cout << endl;
    cout << "前序遍历:" << endl;
    logPreOrder(tree);

    cout << "中序遍历(递归):" << endl;
    _logInOrder(tree);
    cout << endl;
    cout << "中序遍历:" << endl;
    logInOrder(tree);

    cout << "后序遍历(递归):" << endl;
    _logPostorder(tree);
    cout << endl;
    cout << "后序遍历:" << endl;
    logPostorder(tree);
    delete tree;


    cout << "二叉树的查找:" << endl;
    cout << "数据源:" << endl;

    mSort.log(ints, 10);
    cout << "生成二叉查找树(递归):" << endl;
    BinaryTree tree1 = NULL;
    _creatTree(tree1, ints, 10);
    logLevel(tree1);
    delete tree1;

    cout << "生成二叉查找树:" << endl;
    BinaryTree tree2 = NULL;
    creatTree(tree2, ints, 10);
    logLevel(tree2);
    cout << "二叉查找树查找:" << endl;
    logTreeNode(searchNode(tree2, 9999));
    logTreeNode(searchNode(tree2, 99));
    logTreeNode(searchNode(tree2, 85));
    logTreeNode(searchNode(tree2, 464));
    logTreeNode(searchNode(tree2, 156));
    logTreeNode(searchNode(tree2, 5555));
    logLevel(tree2);


    insertNode(tree2, -100);
    logLevel(tree2);
    insertNode(tree2, -99);
    logLevel(tree2);
    insertNode(tree2, -2);
    logLevel(tree2);
    insertNode(tree2, 12);
    logLevel(tree2);
    insertNode(tree2, -1);
    logLevel(tree2);
    insertNode(tree2, -101);
    logLevel(tree2);
    insertNode(tree2, -102);
    logLevel(tree2);
    insertNode(tree2, -103);
    logLevel(tree2);


    cout << "二叉查找树删除:" << endl;
    deleteNode(tree2, 99);
    deleteNode(tree2, 15);
    deleteNode(tree2, 86);
    deleteNode(tree2, 579);
    deleteNode(tree2, 464);
    deleteNode(tree2, 456);
    deleteNode(tree2, 85);
    deleteNode(tree2, 156);
    deleteNode(tree2, 216);
    deleteNode(tree2, 416);
    deleteNode(tree2, 15);
    deleteNode(tree2, 85);
    deleteNode(tree2, 86);
    deleteNode(tree2, 99);
    deleteNode(tree2, 156);
    deleteNode(tree2, 216);
    deleteNode(tree2, 456);
    deleteNode(tree2, 464);
    deleteNode(tree2, 759);
    deleteNode(tree2, 579);
    logLevel(tree2);
    delete tree2;

    cout << "AVL 树:" << endl;
    AVLTree treeAVL=NULL;
    cout << "AVL 树的创建:" << endl;
    creatTreeAVL(treeAVL, ints, 10);
    insertNodeAVL(treeAVL, -100);
    insertNodeAVL(treeAVL, -99);
    insertNodeAVL(treeAVL, -2);
    insertNodeAVL(treeAVL, 12);
    insertNodeAVL(treeAVL, -1);
    insertNodeAVL(treeAVL, -101);
    insertNodeAVL(treeAVL, -102);
    insertNodeAVL(treeAVL, -103);
    logLevel(treeAVL);
    deleteNodeAVL(treeAVL, 15);
    deleteNodeAVL(treeAVL, 85);
    deleteNodeAVL(treeAVL, 86);
    deleteNodeAVL(treeAVL, 99);
    deleteNodeAVL(treeAVL, 156);
    deleteNodeAVL(treeAVL, 216);
    deleteNodeAVL(treeAVL, 456);
    deleteNodeAVL(treeAVL, 464);
    deleteNodeAVL(treeAVL, 759);
    deleteNodeAVL(treeAVL, 579);

    int aa[10] = {-103, -102, -101, -100, -99, -2, -1, 12, 416, 456};
    for (int i = 0; i < 10; ++i) {
        deleteNodeAVL(treeAVL, aa[i]);
    }
    delete treeAVL;

    cout<<"红黑二叉树："<<endl;
    cout<<"红黑二叉树的创建："<<endl;
    BRtree bRtree = NULL ;
    createBRTree(bRtree,ints,10);
    logBRTree(bRtree);
    cout<<endl;
    insertBRTree(bRtree,-20);
    logBRTree(bRtree);
    cout<<endl;
    insertBRTree(bRtree,-19);
    logBRTree(bRtree);
    cout<<endl;
    insertBRTree(bRtree,-19);
    logBRTree(bRtree);
    cout<<endl;
    insertBRTree(bRtree,-17);
    logBRTree(bRtree);
    cout<<endl;
    deleteBRTree(bRtree,-10);
    logBRTree(bRtree);
    cout<<endl;
    deleteBRTree(bRtree,99);
    logBRTree(bRtree);
    cout<<endl;
    deleteBRTree(bRtree,579);
    logBRTree(bRtree);
    cout<<endl;
    deleteBRTree(bRtree,216);
    logBRTree(bRtree);
    cout<<endl;
    delete bRtree;


    int brs[20];
    for (int j = 1; j <=20; ++j) {
        brs[j-1] = j ;
    }
    BRtree bRtree1 =NULL ;
    createBRTree(bRtree1,brs,20);
    logBRTree(bRtree1);
    cout<<endl;
    deleteBRTree(bRtree1,20);

    logBRTree(bRtree1);
    cout<<endl;


    BRtreeTest();
    return 0;
}