数据结构试验七：搜索树与堆

写的好乱。有空再整理吧

1、 输入一系列不为零的正整数（最多不超过20个），遇到0代表输入结束（不包含0）。

2、 根据上面输入的数据序列，用初始化方法创建最大堆（不要用节点依次插入的办法创建最大堆），然后输出最大堆的层次序列。

3、 输出用堆排序后的排序结果。

4、 根据上面输入的数据，创建二叉搜索树（关键字不允许重复，如遇重复，则不重复插入该关键字），输出二叉搜索树的前序序列、中序序列（分行输出）。

#include<iostream>
#include<queue>

using namespace std;
int allCount, counter = 0;

class BStreeNode {
public:
    int data;
    BStreeNode *leftChild, *rightChild;
    BStreeNode() {
        leftChild = rightChild = nullptr;
        data = 0;
    }
};

class MaxHeap {
public:
    int elements[21]{};
    int size = 0;
    void init();
};

void MaxHeap::init() {
    if (size != 0) {
        for (int i = size / 2; i > 0; --i) {
            int currentElementLocate = i;
            int childLocate = 2 * i;
            int data ;
            while (childLocate <= size) {
                if (childLocate < size && elements[childLocate] < elements[childLocate + 1]) {
                    childLocate++;
                }
                if (elements[currentElementLocate] < elements[childLocate]) {
                    data = elements[currentElementLocate];
                    elements[currentElementLocate] = elements[childLocate];//把子节点的值往上移
                    elements[childLocate] = data;
                }
                currentElementLocate = childLocate;
                childLocate = 2 * currentElementLocate;
            }
        }
    }
}

void preOrder(BStreeNode *node) {//前序遍历输出
    if (node != nullptr) {
        if (counter != allCount - 1) cout << node->data << ",";
        else cout << node->data << endl;
        counter++;
        preOrder(node->leftChild);
        preOrder(node->rightChild);
    }
}

void inOrder(BStreeNode *node) {//中序遍历输出
    if (node != nullptr) {
        inOrder(node->leftChild);
        if (counter != allCount - 1) cout << node->data << ",";
        else cout << node->data << endl;
        counter++;
        inOrder(node->rightChild);
    }
}

void postOrder(BStreeNode *node) {//后序遍历输出
    if (node != nullptr) {
        postOrder(node->leftChild);
        postOrder(node->rightChild);
        if (counter != allCount - 1) cout << node->data << ",";
        else cout << node->data << endl;
        counter++;
    }
}

//这是一个构造可能的平衡二叉树的方法
void addToBSTree(BStreeNode *pNode, int *list, int leftFrom, int leftTo, int rightFrom, int rightTo) {

    if (leftTo >= leftFrom || rightTo >= rightFrom) {
        if (leftTo >= leftFrom) {
            BStreeNode *leftNode = new BStreeNode();
            int leftMiddle = (leftFrom + leftTo) / 2;
            leftNode->data = list[leftMiddle];
            if (pNode->data != leftNode->data) {
                pNode->leftChild = leftNode;
            }
            addToBSTree(leftNode, list, leftFrom, leftMiddle - 1, leftMiddle + 1, leftTo);
        }
        if (rightTo >= rightFrom) {
            BStreeNode *rightNode = new BStreeNode();
            int rightMiddle = (rightFrom + rightTo) / 2;
            rightNode->data = list[rightMiddle];
            if (pNode->data != rightNode->data) {
                pNode->rightChild = rightNode;
            }
            addToBSTree(rightNode, list, rightFrom, rightMiddle - 1, rightMiddle + 1, rightTo);
        }
    }
}

//找到二叉树中新插入的node的节点的位置并插入
void find(BStreeNode *root, BStreeNode *node) {
    BStreeNode *current = root;
    if (node->data > current->data) {
        if (current->rightChild != nullptr) {
            current = current->rightChild;
            find(current, node);
        } else {
            current->rightChild = node;
        }
    } else if (node->data < current->data) {
        if (current->leftChild != nullptr) {
            current = current->leftChild;
            find(current, node);
        } else {
            current->leftChild = node;
        }
    }
}

int main() {
    cout << "Input" << endl;
    MaxHeap *heap = new MaxHeap();
    int inputData[21];//后面要用，记录输入的数据
    bool has;//数据是否存在
    int locate = 0;//data放在堆中的位置
    int data = 0;

    cin >> data;

    inputData[allCount] = data;
    allCount++;//先++，避免for循环出问题
    while (data != 0) {
        locate++;
        heap->elements[locate] = data;
        cin >> data;

        //收集输入的数据，后面要用
        has = false;
        for (int i = 0; i < allCount; ++i) {
            if (data == inputData[i]) { has = true; }
        }
        if (!has && data != 0) {
            inputData[allCount] = data;
            allCount++;
        }
    }
    heap->size = locate;

    heap->init();

    cout << "Output" << endl;

    //输出层次序列
    for (int i = 1; i < heap->size; ++i) {
        cout << heap->elements[i] << ",";
    }
    cout << heap->elements[heap->size] << endl;

    //堆排序,有瑕疵但是能用
    int counts = heap->size;
    int result[counts];
    locate = counts - 1;
    for (int i = 1; i <= counts; ++i) {
        //从后往前收集从堆中删除的数据，就是堆排序的结果
        result[locate] = heap->elements[1];
        for (int j = 1; j < heap->size; ++j) {
            //理论上后一个应该是0，会把原本的末尾覆盖掉，其实不覆盖也无妨
            heap->elements[j] = heap->elements[j + 1];
        }
        //所以--放在这
        heap->size--;
        locate--;
        heap->init();
    }
    //输出堆排序结果
    for (int i = 0; i < counts - 1; ++i) {
        cout << result[i] << ",";
    }
    cout << result[counts - 1] << endl;

//    //创建二叉搜索树
    BStreeNode *root = new BStreeNode();
    root->data = inputData[0];
    for (int i = 1; i < allCount; ++i) {
        BStreeNode *node = new BStreeNode();
        node->data = inputData[i];
        find(root, node);
    }
    
    preOrder(root);
    counter = 0;
    inOrder(root);
    cout << "End" << endl;
    return 0;
}