2024/6/8 数据结构数据结构

二叉查找树

先附上完整的代码

template <class KEY,class OTHER>
struct SET
{
    KEY key;																		
    OTHER other;																	
};

template<class KEY,class OTHER>
class dynamicSearchTable
{
public:
    virtual SET<KEY, OTHER>* find(const KEY& x) = 0;
    virtual void insert(const SET<KEY, OTHER>& x) = 0;
    virtual void remove(const KEY& x) = 0;
    virtual ~dynamicSearchTable() {};
};

template<class KEY, class OTHER>
class BinarySearchTree :public dynamicSearchTable<KEY, OTHER>
{
private:
    struct BinaryNode
    {
        SET<KEY, OTHER>data;
        BinaryNode* left;
        BinaryNode* right;
        BinaryNode(const SET<KEY, OTHER>& thedata, BinaryNode* It = NULL,
            BinaryNode* rt = NULL):data(thedata),right(rt){}
    }; 
    BinaryNode* root;
    
public:
    BinarySearchTree();
    ~BinarySearchTree();
    SET <KEY, OTHER>* find(const KEY& x)const;
    void insert(const SET<KEY, OTHER>& x);
    void remove(const KEY& x);
    
private:
    void insert(const SET<KEY, OTHER>& x, BinaryNode*& t);
    void remove(const KEY& x, BinaryNode*& t);
    SET <KEY, OTHER>* find(const KEY& x,BinaryNode* t)const;
    void makeEmpty(BinaryNode* t);
};


template<class KEY, class OTHER>
SET <KEY, OTHER>* BinarySearchTree<KEY, OTHER>::find(const KEY& x)const
{
    return find(x, root);
}


template<class KEY, class OTHER>
SET <KEY, OTHER>* BinarySearchTree<KEY, OTHER>::find(const KEY& x, BinaryNode* t)const
{
    if (t == NULL || (t->data.key == x))				
        return (SET<KEY,OTHER>*)t;										
    if (x < t->data.key)								
        return find(x.t->left);							
    else return find(x, right);							
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x)
{
    insert(x, root);
}


template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x, BinaryNode*& t)
{
    if (t == NULL)
        t = new BinaryNode(x, NULL, NULL);							
    else if (x.key < t->data.key)									
        insert(x, t->left);					
    else if (t->data.key < x.key)									
        insert(x, t->right);
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::remove(const KEY& x)
{
    remove(x, root);
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::remove(const KEY& x, BinaryNode*& t)
{
    if (t == NULL)return;											
    if (x < t->data.key)remove(x, t->left);							
    else if (t->data.key < x)remove(x, t->right);
    else if (t->left != NULL && t->right != NULL)					
    {																
        BinaryNode* tmp = t->right;									
        while (tmp->left != NULL)tmp = tmp->left;					
        t->data = tmp->data;										
        remove(t->data.key, t->right);								
    }
    else
    {
        BinaryNode* oldNode = t;									
        t = (t->left != NULL) ? t->left : t->right;					
        delete oldNode;												
    }
}

template<class KEY, class OTHER>
BinarySearchTree<KEY, OTHER>::BinarySearchTree()
{
    root = NULL;
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::makeEmpty(BinaryNode* t)
{
    if (t == NULL)return;										
    makeEmpty(t->left);
    makeEmpty(t->right);
    delete t;
}

template<class KEY, class OTHER>
BinarySearchTree<KEY, OTHER>::~BinarySearchTree()
{
    makeEmpty(root);
}

int main()
{
    return 0;
}

前提组成

template <class KEY,class OTHER>
struct SET
{
    KEY key;																		//关键字信息
    OTHER other;																	//和其他信息
};

这是基本的数据元素

分别包括键值key和其他值value（就像字典里面对应的查找关键和词语解释）

template<class KEY,class OTHER>
class dynamicSearchTable
{
public:
    virtual SET<KEY, OTHER>* find(const KEY& x) = 0;						//查找目标元素，返回值为指针
    virtual void insert(const SET<KEY, OTHER>& x) = 0;						//插入功能
    virtual void remove(const KEY& x) = 0;									//显然是删除功能
    virtual ~dynamicSearchTable() {};										//析构函数
};

这就是二叉查找树的父类动态查找表，也可以看作一个模板而已，提供了基础的一个动态查找的基本功能模板

动态二叉树

动态二叉树的主体类函数

template<class KEY, class OTHER>
class BinarySearchTree :public dynamicSearchTable<KEY, OTHER>
{
private:
    struct BinaryNode
    {
        SET<KEY, OTHER>data;
        BinaryNode* left;
        BinaryNode* right;

        BinaryNode(const SET<KEY, OTHER>& thedata, BinaryNode* It = NULL,
            BinaryNode* rt = NULL):data(thedata),right(rt){}
    }; BinaryNode* root;

public:
    BinarySearchTree();										//构造函数
    ~BinarySearchTree();									//析构函数
    SET <KEY, OTHER>* find(const KEY& x)const;				//查找函数（公有，面向使用者）
    void insert(const SET<KEY, OTHER>& x);					//插入函数（公有，面向使用者）
    void remove(const KEY& x);								//删除函数（公有，面向使用者）
private:
    void insert(const SET<KEY, OTHER>& x, BinaryNode*& t);		//查找函数（私有，面向公有调用函数）
    void remove(const KEY& x, BinaryNode*& t);					//插入函数（公有，面向公有调用函数）
    SET <KEY, OTHER>* find(const KEY& x,BinaryNode* t)const;	//删除函数（公有，面向公有调用函数）
    void makeEmpty(BinaryNode* t);								//清空函数
};

树的节点分析：

struct BinaryNode
    {
        SET<KEY, OTHER>data;								//本体的数据
        BinaryNode* left;									//左子节点的指针
        BinaryNode* right;									//右子节点的指针

        BinaryNode(const SET<KEY, OTHER>& thedata, BinaryNode* It = NULL,	//节点的构造函数，可以直接设定三个成员
            BinaryNode* rt = NULL):data(thedata),right(rt){}
    }; BinaryNode* root;

注意：后面经常会用到公有函数调用私有函数，虽然名称一样，但一个面向使用者，私有的面向共有的函数调用内部

void remove(const KEY& x)								//删除函数（公有，面向使用者）
{
    remove(x,root);										//这里调用的就是私有函数
}
void remove(const KEY& x, BinaryNode*& t);				//这就是私有函数的接口和实现

接下来分析函数的实现

构造函数

template<class KEY, class OTHER>
BinarySearchTree<KEY, OTHER>::BinarySearchTree()
{
    root = NULL;										//简单初始化了一下根节点
}

makempty

主要还是递归循环删除，采用了前序遍历的思想

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::makeEmpty(BinaryNode* t)
{
    if (t == NULL)return;									//递归终止的条件（删到了空节点）
    makeEmpty(t->left);										//正常步骤先删左节点，往下递归
    makeEmpty(t->right);									//再删右节点，往下递归
    delete t;												//删除自己	
}//最后就删除了所给节点和节点的所有子节点

拓展：其实最近刷题还看到了一种实现方法就是入队和出队在这里

优点：就是摆脱了递归的对于空间的大量调用，利用循环和队列实现（更多是在链表使用的方法）

其实这是层序遍历的使用方法，只是用这个实现了层序遍历的删除方式

**自己拓展的，不是范例的**
Queue<BinaryNode*>  queue;									//存放节点指针的队列

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::makeEmpty(BinaryNode* t)
{
queue.enqueue(t);										//先把根节点放入队列
   while(t.isempty())										//终止条件：检查队列是否为空，不空则继续进行
   {
       BinaryNode* t=queue.dequeue();						//出队队列的第一个节点
       if(t->left!=nullptr)queue.enqueue(t->left);			//左子节点有就放进队列，没则不处理
       if(t->right!=nullptr)queue.enqueue(t->right);		//同理
       delete t;											//然后删除自己
   }
}

析构函数

template<class KEY, class OTHER>
BinarySearchTree<KEY, OTHER>::~BinarySearchTree()
{
    makeEmpty(root);											//就从root开始删除，很简单，不解释了
}

插入函数（insert）

从这插入函数观察二叉树的构成特点：左子节点小于父节点，右子节点大于父节点（节点不会重复）

这个特点就导致插入的时候有一个特性：以这个特点往下寻找插入点必然是叶节点，从而使插入特别方便。

函数还是递归实现的函数，逐次往下寻找（二叉树的结构导致如果树高了必然会导致搜索耗费大量的时间，之后会有扁平的处理方法）

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x)
{
    insert(x, root);												//表示从根节点往下寻找插入点
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x, BinaryNode*& t)
{
    if (t == NULL)
        t = new BinaryNode(x, NULL, NULL);							//若根节点不存在，则直接存进去
    else if (x.key < t->data.key)									//若小于当前节点则向左递归
        insert(x, t->left);					
    else if (t->data.key < x.key)									//大于则向右递归
        insert(x, t->right);										
                                                                    //等于的情况直接退出不干，二叉树的插入必须是不同
}

查找函数（find）

查找函数就是基于二叉树的结构特点建立的，左小右大

template<class KEY, class OTHER>
SET <KEY, OTHER>* BinarySearchTree<KEY, OTHER>::find(const KEY& x)const
{
    return find(x, root);
}

template<class KEY, class OTHER>
SET <KEY, OTHER>* BinarySearchTree<KEY, OTHER>::find(const KEY& x, BinaryNode* t)const
{
    if (t == NULL || (t->data.key == x))				//如果是不存在或者就是当前的节点
        return (SET<KEY,OTHER>*)t;						//找到就返回这个指针,没有的话就是返回空指针
    if (x < t->data.key)								//如果小于则向左找
        return find(x.t->left);							
    else return find(x, right);							//大于则向右找
}

注意：有人可能会注意到，t不是BinarNode吗，怎么能强制转换为SET类的指针啊
return (SET<KEY,OTHER>*)t;
这里需要解释一下结构体和类的一个特点：

对于类和结构的存贮使从第一个数据成员开始的。

举个例子：对于BinarNode的存储空间第一个就是存放的SET，因为在定义里面是写在第一个的。

从而对于指向BinaryNode存储空间的指针某种意义上也是指向了SET的开头，进而可以进行强制转换
//树节点的结构体
struct BinaryNode
    {
        SET<KEY, OTHER>data;
        BinaryNode* left;
        BinaryNode* right;

        BinaryNode(const SET<KEY, OTHER>& thedata, BinaryNode* It = NULL,
            BinaryNode* rt = NULL):data(thedata),right(rt){}
    }; BinaryNode* root;

删除函数（remove）

主体思路：

删除大体是这个思路为了保证树的结构不变，主要分三种情况
1.如果这个删除节点没有度数为0，很简单删除就好了
2.只有一个子节点，把字节点复制上去，把字节点删除
3.这个最复杂，因为他又俩个节点，为了保证树结构不变必然是在叶子节点中找到最靠近这个节点的数
其实根据这个查找二叉树的结构，分析出最接近的是左子节点一直往子节点的右子节点找（左子节点<x<当前节点），或者是右子节点的左子节点一直找（当前节点<x<右子节点）
对于这题我们假设向右子节点寻求最接近的值

最关键的是：

首先，替代问题，为了保证稳定性必须要替换一个最接近的节点互换位置，顶替

其次由于结构最接近无非最近但小于（左节点的最右节点）和最近但大于（右节点的最左字节点）

这个寻找方法便捷的地方在于必然是叶子节点替换，也易于删除

//这里的实现主要是最右子节点最左节点（大于且最靠近的树）
template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::remove(const KEY& x)
{
    remove(x, root);
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::remove(const KEY& x, BinaryNode*& t)
{
    //先找到要删除的节点
    if (t == NULL)return;
    //第一种情况空节点返回

    if (x < t->data.key)remove(x, t->left);
    //第二种情况，要删除小于当前节点，往左递归
    
    else if (t->data.key < x)remove(x, t->right);
    //第三种情况要找的大于当前节点，往右边递归

    else if (t->left != NULL && t->right != NULL)					
    {																
        BinaryNode* tmp = t->right;									
        while (tmp->left != NULL)tmp = tmp->left;
        //循环找到右子节点的最左节点
        
        t->data = tmp->data;
        //替换俩个节点顺序
        remove(t->data.key, t->right);
        //删除替换后的叶子节点，结束
    }
    //第四种，找到了当前节点就是要删除的节点，但是左右都有子节点
    
    
    else
    {
        BinaryNode* oldNode = t;																					t = (t->left != NULL) ? t->left : t->right;
        //如果有一个子节点，t就是直接替换为子节点，然后删除原来的节点，即使没有子节点，t变为空间点也合乎逻辑
        delete oldNode;
    }
    //第五种，找到了要么一个子节点，要么没有

    //有没有发现，我选择右子树寻找替代，那么替代的那个点也是右子树要处理
}

有一点需要注意：
void BinarySearchTree<KEY, OTHER>::remove(const KEY& x, BinaryNode*& t)
我们发现节点的参数传递都是引用传递，那是为了方便节点直接替换

例如remove，正是因为引用传递，在层层递归中确保每次传下来的t都是确确实实来自于父节点里面直接的左右节点的指针

这样就维持了上下关系，确保修改是有效的

##总结：至此就分析结束了

（有时间在这里补一个二叉树查找性能的分析）

LOADING

二叉查找树

前提组成

动态二叉树

接下来分析函数的实现