实验11 二叉搜索树（带索引）

描述

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

格式

输入格式

输入第一行一个数字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
删除操作中，如果当前元素有两个孩子，替换的为右子树中最小的，如果只有一个孩子，直接用该孩子替换当前元素，如果没有孩子，直接删除
删除操作的替换过程中所有比较操作不计入答案

思路和探讨

搜索树相关知识

笔记补充——第十四章：搜索树

整体思路描述

该实验中的基础操作和笔记所列代码除没有用字典这一差别外大体一致。

且因有对于输入中的每一种操作，输出执行操作的过程中依次比较的元素值的异或值。这一规则，在操作过程中添加了异或值计算。

首先定义一个带索引的二叉搜索树，依次定义并实现构造函数插入函数、搜索函数、删除函数、按名次搜索函数、按名次删除函数。

细节思路补充

find

搜索先从根开始。
如果根为空，那么搜索树不包含任何元素，查找失败.
如果theElement 小于根节点的关键字，在左子树中搜索theElement。
如果theElement 大于根节点的关键字，在右子树中搜索theElement。
如果theElement等于根节点的关键字，则查找成功。

insert

在二叉搜索树中插入一个新元素theElement：
首先搜索，验证theElement是否存在
如果搜索成功，那么不需要插入
如果搜索不成功，那么新元素将被插入到搜索的中断点
并完成左子树元素个数更新

erase

情况①：被删除元素的节点p是树叶

直接丢弃树叶节点

情况②：被删除元素的节点p只有一个非空子树
情况③：被删除元素的节点p有两个非空子树
可以用它左子树的最大元素或者右子树的最小元素来替换它
左子树的最大元素或者右子树的最小元素一定是叶子或者一个度为1的节点

而后转换为删除元素的节点p只有一个非空子树或删除元素的节点p是树叶
并关注删除时的leftSize更新

search(a)

按名次搜索
x从根开始
如果index = x.leftSize，第index个元素是x.element
如果index < x.leftSize，第index个元素是x的左子树的第index个元素
如果index > x.leftSize，第index个元素是x的右子树的第index – (x.leftSize + 1)个元素

delete_(a)

按名次删除
完成按名次搜索对应节点
后按erase思路完成删除

若已看懂思路，试着自己写~

实现代码

#include <iostream>
using namespace std;

template <class T>
struct BinaryTreeNode//二叉树节点 
{//二叉树节点 
    T element;
    BinaryTreeNode<T>* leftChild;
    BinaryTreeNode<T>* rightChild;
    int leftSize;//规定为该节点左子树的元素个数 

    BinaryTreeNode(const T& theElement)
	{
        element = theElement;
        leftChild = NULL;
        rightChild = NULL;
        leftSize = 0;
    }
    
    BinaryTreeNode(const T& theElement, BinaryTreeNode<T>* theLeft, BinaryTreeNode<T>* theRight, int LeftSize)
	{
        element = theElement;
        leftChild = theLeft;
        rightChild = theRight;
        leftSize = LeftSize;
    }
};

template <class T>
class indexedBSTree
{//二叉搜索树 （带索引） 
	public:
    	indexedBSTree()
		{//初始化 
			root = NULL;
        	size = 0;
    	}
    	int insert(const T& theElement);//插入函数 
    	int find(const T& theElement);//搜索函数 
    	int erase(const T& theElement);//删除函数 
    	int Search(int a);//按名次搜索函数 
    	int delete_(int a);//按名次删除函数 
	private:
    	int size;
    	BinaryTreeNode<T>* root;
};

//插入函数 
template <class T>
int indexedBSTree<T>::insert(const T& theElement)
{
    BinaryTreeNode<T>* p = root;
    BinaryTreeNode<T>* pp = NULL;
    //pp相当于一个影子跟屁虫，记p的父节点，与p同步下移，保证插入 
    int sum = 0;
    while (p != NULL)
	{
        if (p->element < theElement)
		{//要插入的元素大，放右节点去 
            sum ^= p->element;
            pp = p;
            p = p->rightChild;
        }
        else if (p->element > theElement)
		{//要插入的元素小，放左节点去 
            sum ^= p->element;
            pp = p;
            p = p->leftChild;
        }
        else if (p->element == theElement) 
		{//恰好相等，不需要插入
            return 0;
        }
    }
    
    //为新元素建立新节点，与pp相连 
    BinaryTreeNode<T>* newNode = new BinaryTreeNode<T>(theElement);
    
    if (pp != NULL)
	{
		//新元素比父节点大，为pp的右孩子
        if (theElement > pp->element)
            pp->rightChild = newNode;
        //新元素比父节点小，为pp的左孩子
        else if (theElement < pp->element)
            pp->leftChild = newNode;
    }
    else
	{//空树，直接插入到根节点
        root = newNode;
    }
    
    size++;
    
    p = root;
    while (p->element != theElement)
    {//左子树元素个数更新 （即索引更新） 
        if (p->element < theElement)
        {
            p = p->rightChild;
        }
        else if (p->element > theElement)
        {
            p->leftSize++;
            p = p->leftChild;
        }
    }
    return sum;
}

//搜索函数 
template <class T>
int indexedBSTree<T>::find(const T& theElement)
{
    BinaryTreeNode<T>* p = root;
    int sum = 0;
    while (p != NULL && p->element != theElement)
    {
        sum ^= p->element;
        if (p->element > theElement)
        {
            p = p->leftChild;
        }
        else if (p->element < theElement)
        {
            p = p->rightChild;
        }
    }
    //【查找中，未找到，输出 0】 
    if (p == NULL)
        return 0;
    //找到了
    else
    {
    	//补充p->element=theElement的异或计算 
        sum ^= p->element;
        return sum;
    }
}

//删除函数
template <class T>
int indexedBSTree<T>::erase(const T& theElement)
{
    BinaryTreeNode<T>* p = root;
    BinaryTreeNode<T>* pp = NULL;
    int sum = 0;
    while (p != NULL && p->element != theElement)
    {//未完且还没到要删除的元素 
        sum ^= p->element;
        pp = p;
        if (p->element < theElement)
        {
            p = p->rightChild;
        }
        else if (p->element > theElement)
        {
            p = p->leftChild;
        }
    }
    
    if (p == NULL)
    {//未找到 
        return 0;
    }
    
    //p->element=theElement 异或计算补充 
    sum ^= p->element;
    
    p = root;
    while (p != NULL && p->element != theElement)
    {//左子树元素个数更新(即索引值更新 
        if (p->element < theElement)
        {
            p = p->rightChild;
        }
        else if (p->element > theElement)
        {
            p->leftSize--;
            p = p->leftChild;
        }
    }

	//当前元素有两个孩子 
    if (p->leftChild != NULL && p->rightChild != NULL)
    { 
    	//min_right是删除节点的右孩子，用来找那个最小的右元素 
        BinaryTreeNode<T>* min_right = p->rightChild;
        //s是待删除节点 
        BinaryTreeNode<T>* s = p;
        
		//【替换的为右子树中最小的】
        while (min_right->leftChild != NULL)
        {
            min_right->leftSize--;
            s = min_right;//用s记录最小元素的父节点的位置
            min_right = min_right->leftChild;//min_right记录最小元素的位置
        }
   
   		//用newNode存好找到的最小元素 
        BinaryTreeNode<T>* newNode = new BinaryTreeNode<T>(min_right->element, p->leftChild, p->rightChild, p->leftSize);
        
		//开始替换 
		if (pp == NULL)
            root = newNode;
        else if (p == pp->leftChild)
            pp->leftChild = newNode;
        else
            pp->rightChild = newNode;
    	 
        if (s == p) 
            pp = newNode;  
        else
            pp = s;

        delete p;   
        p = min_right; 
    }

	//当前元素只有一个孩子，【直接用该孩子替换当前元素】 
    BinaryTreeNode<T>* c;
    if (p->leftChild != NULL)
        c = p->leftChild;
    else
        c = p->rightChild;
    
    //删除节点位于根节点
	if (p == root)
        root = c;//根节点更新为孩子节点
    //删除节点不是根节点
	else
    {
        if (p == pp->leftChild) //p是pp的左孩子
            pp->leftChild = c;
        else //p是pp的右孩子
            pp->rightChild = c;
    }
    size--;
    delete p;
    return sum;
}

//按名次搜索函数
template <class T>
int indexedBSTree<T>::Search(int a)
{
    BinaryTreeNode<T>* p = root;
    int sum = 0;
    while (p != NULL && p->leftSize != a)
    {
        sum ^= p->element;
        if (p->leftSize > a)
        { //该节点的索引比b大，证明b在左孩子中
            p = p->leftChild;
        }
        else if (p->leftSize < a)
        {//该节点的索引比b小，证明b在右孩子中
            a = a - p->leftSize - 1;
            p = p->rightChild;
        }
    }
    //没找到 
    if (p == NULL)
        return 0;
    //找到了 
    else
    {
    	//补充最后一次，最后一次该节点的索引等于b
        sum ^= p->element;
        return sum;
    }
}

//按名次删除函数 
template <class T>
int indexedBSTree<T>::delete_(int a)
{
    BinaryTreeNode<T>* p = root;
    BinaryTreeNode<T>* pp = NULL;
    int sum = 0;
    while (p != NULL && p->leftSize != a)
    {
        sum ^= p->element;
        pp = p;
        if (p->leftSize > a)
        {//该节点的索引比b大，证明b在左孩子中
            p = p->leftChild;
        }
        else if (p->leftSize < a)
        {//该节点的索引比b小，证明b在右孩子中
            a = a - p->leftSize - 1;
            p = p->rightChild;
        }
    }
    //没找到
    if (p == NULL)
        return 0;
    //补充最后一次比较异或计算 
    sum ^= p->element;
    int theElement = p->element;
    p = root;
    while (p != NULL && p->element != theElement)
    {
        if (p->element < theElement)
        {
            p = p->rightChild;
        }
        else if (p->element > theElement)
        {
            p->leftSize--;
            p = p->leftChild;
        }
    }
    //同erase理 
    if (p->leftChild != NULL && p->rightChild != NULL)
    {
        BinaryTreeNode<T>* min_right = p->rightChild;
        BinaryTreeNode<T>* s = p;
        while (min_right->leftChild != NULL)
        {
            min_right->leftSize--;
            s = min_right;
            min_right = min_right->leftChild;
        }

        BinaryTreeNode<T>* newNode = new BinaryTreeNode<T>(min_right->element, p->leftChild, p->rightChild, p->leftSize);
        if (pp == NULL)
            root = newNode;
        else if (p == pp->leftChild)
            pp->leftChild = newNode;
        else
            pp->rightChild = newNode;
    
        if (s == p)
            pp = newNode;
        else
            pp = s;

        delete p; 
        p = min_right; 
    }

    BinaryTreeNode<T>* c;
    if (p->leftChild != NULL)
        c = p->leftChild;
    else
        c = p->rightChild;

    if (p == root)
        root = c;
    else
    {
        if (p == pp->leftChild)
            pp->leftChild = c;
        else
            pp->rightChild = c;
    }
    size--;
    delete p;
    return sum;
}

int main()
{
    indexedBSTree<int> x;
    int m, a, b;
    cin >> m;
    for(int i=0;i<m;i++)
	{
        cin >> a >> b;
        if (a == 0)
		{
            cout << x.insert(b) << endl;
        }
        if (a == 1)
		{
            cout << x.find(b) << endl;
        }
        if (a == 2)
		{
            cout << x.erase(b) << endl;
        }
        if (a == 3)
		{
            b = b - 1;
            cout << x.Search(b) << endl;
        }
        if (a == 4)
		{
            b = b - 1;
            cout << x.delete_(b) << endl;
        }
    }
}

文章出处登录后可见！

已经登录？立即刷新

实验11 二叉搜索树（带索引）

实验11 二叉搜索树（带索引）

描述

格式

输入格式

输出格式

注意

思路和探讨

搜索树相关知识

整体思路描述

细节思路补充

实现代码

相关推荐