首页 > 其他分享 >山东大学数据结构实验11 搜索树

山东大学数据结构实验11 搜索树

时间：2023-04-26 12:56:36浏览次数：39  
标签：11 NULL currentNode parent leftChild key BSTNode 数据结构 山东大学

描述

创建带索引的二叉搜索树类。存储结构使用链表，提供操作:插入、删除、按名次删除、查找、按名次查找、升序输出所有元素。

格式

输入格式

输入第一行一个数字m (m<=1000000)，表示有m个操作。
接下来m行，每一行有两个数字a，b：

  • 当输入的第一个数字 a 为 0 时，输入的第二个数字 b 表示向搜索树中插入 b
  • 当输入的第一个数字 a 为 1 时，输入的第二个数字 b 表示向搜索树中查找 b
  • 当输入的第一个数字 a 为 2 时，输入的第二个数字 b 表示向搜索树中删除 b
  • 当输入的第一个数字 a 为 3 时，输入的第二个数字 b 表示查找搜索树中名次为 b 的元素
  • 当输入的第一个数字 a 为 4 时，输入的第二个数字 b 表示删除搜索树中名次为 b 的元素

输出格式

对于输入中的每一种操作，输出执行操作的过程中依次比较的元素值的异或值。

注意

  • 查询与删除操作中，待查询的元素也需要异或入答案中
  • 查找（删除）操作中，如果未找到，或者插入操作，已存在，输出 0（不插入），不需要输出异或和
  • 查找（删除）第b大，如果不存在，输出 0
  • 删除操作中，如果当前元素有两个孩子，替换的为 右子树中最小的，如果只有一个孩子，直接用该孩子替换当前元素，如果没有孩子，直接删除
  • 删除操作的替换过程中所有比较操作不计入答案

样例1

输入

13
0 6
0 7
0 4
0 5
0 1
1 5
0 7
3 3
2 4
1 5
3 4
4 3
0 4

输出

0
6
6
2
2
7
0
7
2
3
1
6
3

样例2

输入

14
0 43
0 17
0 55
0 62
0 57
0 66
0 67
4 5
0 67
0 70
3 6
4 7
0 20
2 43

输出

0
43
43
28
34
34
96
34
0
29
29
91
58
43

限制

1s, 10240KiB for each test case.

提示

  • 查找和删除第k大的元素时，可以先把第k的元素找到，再按照该元素查找和删除
#include <iostream>
#include<cstring>
#include<algorithm>

using namespace std;

template<class K>
struct BSTNode {
    BSTNode *leftChild;
    BSTNode *rightChild;
    K key;
    int index;

    BSTNode() {};

    BSTNode(K theKey) {
        key = theKey;
        leftChild = NULL;
        rightChild = NULL;
        index = 0;
    }

    BSTNode(BSTNode *bst) {
        bst->rightChild = this->rightChild;
        bst->leftChild = this->leftChild;
        bst->key = this->key;
        bst->index = this->index;
    }

    BSTNode(const K &theElement, BSTNode<K> *theLeft, BSTNode<K> *theRight, int LeftTreeSize) {
        key = theElement;
        leftChild = theLeft;
        rightChild = theRight;
        index = LeftTreeSize;
    }

};

template<class K>
class BSTWithIndex {
public:
    BSTWithIndex() {
        root =NULL;
        Treesize=0;
    };

    //插入、删除、按名次删除、查找、按名次查找、升序输出所有元素。
    int insert(K theKey);

    int erase(K theKey);

    int eraseWithIndex(int theIndex);

    int find(K theKey);

    int findWithIndex(int theIndex);

    void out();

private:
    int Treesize;
    BSTNode<K> *root;

};

template<class K>
int BSTWithIndex<K>::insert(K theKey) {
    BSTNode<K> *currentNode = root;
    BSTNode<K>  *parent = NULL;
    int sum = 0;

    while (currentNode != NULL) {
        if (theKey < currentNode->key) {
            sum ^= currentNode->key;
            parent = currentNode;
            currentNode = currentNode->leftChild;
        } else if (theKey > currentNode->key) {
            sum ^= currentNode->key;
            parent = currentNode;
            currentNode = currentNode->rightChild;
        } else if (theKey == currentNode->key){
            return 0;
        }
    }
    BSTNode<K> *newNode = new BSTNode<K>(theKey);
    if (parent != NULL) {
        if (parent->key > theKey)
            parent->leftChild = newNode;
        else
            parent->rightChild = newNode;
    } else {
        root = newNode;
    }
    Treesize++;
    currentNode = root;
    while (currentNode->key != theKey) {
        if (currentNode->key < theKey) {
            currentNode = currentNode->rightChild;
        } else if (currentNode->key > theKey) {
            currentNode->index++;
            currentNode = currentNode->leftChild;
        }
    }
    return sum;
}

template<class K>
int BSTWithIndex<K>::erase(K theKey) {
    BSTNode<K> *currentNode = root;
    BSTNode<K> *parent = NULL;
    int sum = 0;
    while (currentNode != NULL && currentNode->key != theKey) {
        sum ^= currentNode->key;
        parent = currentNode;
        if (currentNode->key < theKey) {
            currentNode = currentNode->rightChild;
        } else if (currentNode->key > theKey) {
            currentNode = currentNode->leftChild;
        }
    }
    if (currentNode == NULL) {
        return 0;
    }
    sum ^= currentNode->key;
    currentNode = root;
    while (currentNode != NULL && currentNode->key != theKey) {
        if (currentNode->key < theKey) {
            currentNode = currentNode->rightChild;
        } else if (currentNode->key > theKey) {
            currentNode->index--;
            currentNode = currentNode->leftChild;
        }
    }

    if (currentNode->leftChild != NULL && currentNode->rightChild != NULL) {
        BSTNode<K> *ps = currentNode->rightChild;
        BSTNode<K> *s = currentNode;
        while (ps->leftChild != NULL) {
            ps->index--;
            s = ps;
            ps = ps->leftChild;
        }

        BSTNode<K> *newNode = new BSTNode<K>(ps->key, currentNode->leftChild, currentNode->rightChild,
                                             currentNode->index);
        if (parent == NULL)
            root = newNode;
        else if (currentNode == parent->leftChild)
            parent->leftChild = newNode;
        else
            parent->rightChild = newNode;

        if (s == currentNode)
            parent = newNode;
        else
            parent = s;

        delete currentNode;
        currentNode = ps;
    }

    BSTNode<K> *c;
    if (currentNode->leftChild != NULL)
        c = currentNode->leftChild;
    else
        c = currentNode->rightChild;
    if (currentNode == root)
        root = c;
    else {
        if (currentNode == parent->leftChild)
            parent->leftChild = c;
        else
            parent->rightChild = c;
    }
    Treesize--;
    return sum;

}

template<class K>
int BSTWithIndex<K>::eraseWithIndex(int theIndex) {
    BSTNode<K> *currentNode = root;
    BSTNode<K> *parent = NULL;
    int sum = 0;
    while (currentNode != NULL && currentNode->index != theIndex) {
        sum ^= currentNode->key;
        parent = currentNode;
        if (currentNode->index > theIndex) {
            currentNode = currentNode->leftChild;
        } else if (currentNode->index < theIndex) {
            theIndex = theIndex - currentNode->index - 1;
            currentNode = currentNode->rightChild;
        }
    }
    if (currentNode == NULL)
        return 0;
    sum ^= currentNode->key;
    int theElement = currentNode->key;
    currentNode = root;
    while (currentNode != NULL && currentNode->key != theElement) {
        if (currentNode->key < theElement) {
            currentNode = currentNode->rightChild;
        } else if (currentNode->key > theElement) {
            currentNode->index--;
            currentNode = currentNode->leftChild;
        }
    }

    if (currentNode->leftChild != NULL && currentNode->rightChild != NULL) {
        BSTNode<K> *ps = currentNode->rightChild;
        BSTNode<K> *s = currentNode;
        while (ps->leftChild != NULL) {
            ps->index--;
            s = ps;
            ps = ps->leftChild;
        }

        BSTNode<K> *newNode = new BSTNode<K>(ps->key, currentNode->leftChild, currentNode->rightChild, currentNode->index);
        if (parent == NULL)
            root = newNode;
        else if (currentNode == parent->leftChild)
            parent->leftChild = newNode;
        else
            parent->rightChild = newNode;

        if (s == currentNode)
            parent = newNode;
        else
            parent = s;

        delete currentNode;
        currentNode = ps;
    }

    BSTNode<K> *c;
    if (currentNode->leftChild != NULL)
        c = currentNode->leftChild;
    else
        c = currentNode->rightChild;

    if (currentNode == root)
        root = c;
    else {
        if (currentNode == parent->leftChild)
            parent->leftChild = c;
        else
            parent->rightChild = c;
    }
    Treesize--;
    delete currentNode;
    return sum;


}

template <class K>
int BSTWithIndex<K>::find(K theKey)
{
   BSTNode<K>* currentNode = root;
    int sum = 0;
    while (currentNode != NULL && currentNode->key != theKey)
    {
        sum ^= currentNode->key;
        if (currentNode->key > theKey)
        {
            currentNode = currentNode->leftChild;
        }
        else if (currentNode->key < theKey)

        {
            currentNode = currentNode->rightChild;
        }
    }
    if (currentNode == NULL)
        return 0;
    else
    {
        sum ^= currentNode->key;
        return sum;
    }
}


template<class K>
int BSTWithIndex<K>::findWithIndex(int theIndex) {
    BSTNode<K> *p = root;
    int sum = 0;
    while (p != NULL && p->index != theIndex) {
        sum ^= p->key;
        if (p->index > theIndex) {
            p = p->leftChild;
        } else if (p->index < theIndex) {
            theIndex = theIndex - p->index - 1;
            p = p->rightChild;
        }
    }
    if (p == NULL)
        return 0;
    else {
        sum ^= p->key;
        return sum;
    }

}

void inorderHelper(BSTNode<int> *root) {
    if (root == NULL)return;
    inorderHelper(root->leftChild);
    cout << root->key << " ";
    inorderHelper(root->rightChild);
}


int main() {
    int m;
    scanf("%d", &m);
    BSTWithIndex<int> B;
    int a, b;
    while (m--) {
        scanf("%d%d", &a, &b);
        switch (a) {
            case 0:
                cout << B.insert(b) << endl;
                break;
            case 1:
                cout << B.find(b) << endl;
                break;
            case 2:
                cout << B.erase(b) << endl;
                break;
            case 3:
                b--;
                cout << B.findWithIndex(b) << endl;
                break;
            case 4:
                b--;
                cout << B.eraseWithIndex(b) << endl;
                break;


        }
    }


    return 0;
}

标签：11,NULL,currentNode,parent,leftChild,key,BSTNode,数据结构,山东大学
From： https://www.cnblogs.com/lyz103/p/17355578.html

相关文章

  • 山东大学数据结构实验10 堆及其应用
    内容创建最小堆类。最小堆的存储结构使用数组。提供操作:插入、删除、初始化。题目第一个操作是建堆操作，接下来是对堆的插入和删除操作，插入和删除都在建好的堆上操作。格式输入第一行一个数n（n<=5000)，代表堆的大小。第二行n个数，代表堆的各个元素。第三行一个数m(m<=1000)，代......
  • 山东大学数据结构实验9 二叉树操作
    描述创建二叉树类。二叉树的存储结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。格式输入格式第一行为一个数字n(10<=n<=100000)，表示有这棵树有n个节点，编号为1~n。之后n行每行两个数字，第i行的两个数字a、b表示编号......
  • 山东大学数据结构实验8 散列表
    要求使用线性开型寻址实现描述给定散列函数的除数D和操作数m，输出每次操作后的状态。有以下三种操作：插入x，若散列表已存在x，输出“Existed”，否则插入x到散列表中，输出所在的下标。查询x，若散列表不含有x，输出“-1”，否则输出x对应下标。删除x，若散列表不含有x，输出“NotFound”，否......
  • Python通过GPIO从DHT11温度传感器获取数据
    Python通过GPIO从DHT11温度传感器获取数据设备：树莓派4B、DHT11、杜邦线DHT11DHT11是一款有已校准数字信号输出的温湿度传感器。其精度湿度±5%RH，温度±2℃，量程湿度20-90%RH，温度0~50℃。精度不高，但价格低廉。DHT11使用单总线通信。供电电压3.3~5V。线路连接DHT11 树莓......
  • c++，x11,linux查找窗口
    如题点击查看代码#include<X11/Xlib.h>#include<stdio.h>voidfindWindow(Display*display,Windowwindow,char**windowName,Window*result){Windowroot,parent,*children;unsignedintnChildren;if(XFetchName(display,window,windo......
  • C++数据结构(树)
    树是一种递归定义的数据结构，如果树中节点的各子树从左到右是有次序的，不能互换，则称该树为有序树，否则叫无序树。关于树的节点：节点拥有的子树的个数叫做节点的度如果度为0，那么该节点叫做叶节点或终端节点，除了根节点外的分支节点称为内部节点树的度是各节点度的最大值。节点的子......
  • 什么是数据结构？
    数据结构研究计算机数据间关系，包括数据的逻辑结构和存储结构及其操作。我们接触一种数据结构，一定要掌握这三个方面基本概念1.数据（Data）数据即信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。2.数据元素（DataElement）数据......
  • 初识数据结构
    什么是数据结构，数据结构可以理解为我们规定数据元素之间具有某种关系或规则，程序员根据这些规则能够更好的管理和操作这些数据。数据元素的关系包括三种：线性关系——1：1线性关系即为数据是一对一的关系，即除了开头的数据元素和最后的数据元素，其他如何应该数据元素有......
  • 2023年电子科技大学ACM-ICPC暑假前集训-数据结构
    Preface学校针对大一新生的暑假前集训的第一个专题DS，由于要求集体写题解就顺便把写好的发上来了由于下面都写了题意所以直接看也能有很多收获，当然非电专的学生的话就没法交题了代码的话由于专题还没结束怕放上来然后被CV导致被爆破，所以应该在这周六专题结束后会放上来下面都是......
  • 铠侠 RC10 固态硬盘寿命暴力写入测试：1100pe 毫发无损
    一直很好奇固态硬盘的寿命有多久，从来也没有用坏过。怀着强烈的好奇心，开始了这一马拉松测试。直接对固态做暴力写入，一直到写坏为止看看到底写入量多少。从五月份到现在，断断续续写入。现在已经写入1100tb，还没有任何坏的迹象（保修是肯定没有了）。目前缓外写入400-500m/s，与新盘差不多没有......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99