非递归实现伸展树
文章目录
前言
完成递归实现伸展树后将递归操作转化为非递归操作完成，详细介绍可以看我的第三十五篇随记
一、非递归操作与递归操作有什么不一样的地方？
非递归实现伸展树与递归实现相比较而言只是将函数的递归调用返回待操作的结点地址通过循环直接定位，以及将结点路径使用栈进行记录达到自底向上进行回溯的目的，结点的旋转是一样的，其他操作也十分类似。
二、程序解析
1. 结点声明
typedef int ElementType;
typedef struct Treenode{
ElementType data=0;
struct Treenode* Left=nullptr;
struct Treenode* Right=nullptr;
}Treenode;
typedef Treenode* Splaytree;
2. 插入函数
函数参数： 根结点地址，待插入元素
函数功能：在树中找到合适的位置创建一个结点，存储待插入的元素，若树中已存在则提示错误
函数实现：因为我不太喜欢使用二级指针所以我在设计时通过每次返回根结点的地址避免二级指针的使用，若根结点为空指针则为其开辟一块空间，使其数据域存储待插入元素然后返回结点地址，之后的每次插入都先设置一个父指针，每次循环时将结点地址传给父指针然后循环找到合适位置插入结点，为其开辟一块空间将待插入元素赋给其数据域，然后使父指针指向这个结点即可。
Splaytree Insert(Splaytree root,ElementType x){
Splaytree father=nullptr,cur=root;
if(root==nullptr){
root=new struct Treenode;
root->data=x;
}else{
while(cur){
father=cur;
if(cur->data>x)cur=cur->Left;
else if(cur->data<x)cur=cur->Right;
else cout<<"Data collision."<<endl;
}
cur=new struct Treenode;
cur->data=x;
if(father->data>x) father->Left=cur;
else father->Right=cur;
}
return root;
}
3. 删除函数
函数参数：根结点地址，待删除元素
函数功能：在树中删除一个结点
函数实现：通过循环定位到待删除元素所在的结点，每次循环时使用一个父结点指针定位其父结点；若这个结点有两个儿子则先使父指针指向这个结点（防止待删除的结点只有两个儿子）循环找到其右子树中最小的结点并每次记录这个结点地址，循环结束时则为最小结点的父结点，然后用右子树中最小结点的数据覆盖待删除结点的数据域；不管待删除的结点有几个子结点进行到这一步时结点指针指向的结点都最多有一个子树，其父指针指向它，所以用一个中间指针保存这个结点的地址，若这个结点有左儿子则移动指针到其左儿子，反之移动到其右儿子，使其父指针指向移动后的结点，再删除中间指针保存的结点即可。
void Delete(Splaytree root,ElementType x){
Splaytree father=nullptr,min=nullptr,tempcell=nullptr;
while(root!=nullptr&&root->data!=x){
father=root;
if(root->data>x)root=root->Left;
else root=root->Right;
}
if(root==nullptr)cout<<"Not have this data."<<endl;
else{
if(root->Left&&root->Right){
father=root; //为了防止root刚好只有两个子结点
for(min=root->Right;min->Left;min=min->Left)father=min;
root->data=min->data;
root=min;
}
tempcell=root;
if(root->Left)root=root->Left;
else root=root->Right;
if(father->data>tempcell->data) father->Left=root;
else father->Right=root;
delete(tempcell);
}
}
4. 查找函数
函数参数：根结点地址，待查找元素
函数功能：在树中找到待查找元素所在结点（若没找到则输出提示信息）并将这个结点旋转成为新的根结点。
函数实现：声明一个结点指针类型的栈，若根结点不为空且结点数据与待查找元素不相等则通过循环在树中定位到待查找结点的地址并用栈记录访问路径，循环结束后若结点指针为空指针则输出提示信息并结束查找函数；若未结束则说明结点指针指向的结点即为待查找结点，进行循环条件为栈非空的循环，每次取栈顶指针为父指针，然后出出栈，若栈非空则再取栈顶元素为爷爷指针，若空则使爷爷指针等于父指针（作为待查找结点的父结点为根结点的标志）；若待查找结点为父指针指向的结点的子结点，且父指针指向的结点为爷爷指针指向的结点的子结点或爷爷指针等于父指针则进行旋转；否则若爷爷指针不等于父指针则使待查找结点成为爷爷结点的子结点，所有循环结束后返回新根结点地址。
Splaytree Find(Splaytree root,ElementType x){
Splaytree father=nullptr,grandfather=nullptr,first=root;
stack<Splaytree>str;
while(root!=nullptr&&root->data!=x){
str.push(root);
if(root->data>x) root=root->Left;
else root=root->Right;
}
if(root==nullptr){
cout<<"Not found."<<endl;
return first;
}
while(!str.empty()){
father=str.top();
str.pop();
if(!str.empty())grandfather=str.top();
else grandfather=father; //防止待查找结点在第一，二层导致空指针的使用
if((father->Left==root||father->Right==root)&&((grandfather->Left
==father||grandfather->Right==father)||grandfather==father)){
Rotate(root,father,grandfather);
}else{
if(grandfather!=father){
if(grandfather->data>root->data) grandfather->Left=root;
else grandfather->Right=root;
}
}
}
return root;
}
5. 旋转函数
与递归实现伸展树的旋转函数一样见我的三十五篇随记，不在赘述。
6. 整体代码：
#include<iostream>
#include<stack>
typedef int ElementType;
typedef struct Treenode{
ElementType data=0;
struct Treenode* Left=nullptr;
struct Treenode* Right=nullptr;
}Treenode;
typedef Treenode* Splaytree;
using namespace std;
Splaytree Insert(Splaytree,ElementType);
Splaytree Find(Splaytree,ElementType);
void Delete(Splaytree,ElementType);
void Rotate(Splaytree,Splaytree,Splaytree);
void PrintTree(Splaytree);
int main(void){
Splaytree root=nullptr;
ElementType x;
while(cin>>x) root=Insert(root,x);
cin.clear();
cin.ignore();
cout<<endl<<endl;
while(cin>>x){
root=Find(root,x);
cout<<endl;
PrintTree(root);
}
return 0;
}
Splaytree Insert(Splaytree root,ElementType x){
Splaytree father=nullptr,cur=root;
if(root==nullptr){
root=new struct Treenode;
root->data=x;
}else{
while(cur){
father=cur;
if(cur->data>x)cur=cur->Left;
else if(cur->data<x)cur=cur->Right;
else cout<<"Data collision."<<endl;
}
cur=new struct Treenode;
cur->data=x;
if(father->data>x) father->Left=cur;
else father->Right=cur;
}
return root;
}
Splaytree Find(Splaytree root,ElementType x){
Splaytree father=nullptr,grandfather=nullptr,first=root;
stack<Splaytree>str;
while(root!=nullptr&&root->data!=x){
str.push(root);
if(root->data>x) root=root->Left;
else root=root->Right;
}
if(root==nullptr){
cout<<"Not found."<<endl;
return first;
}
while(!str.empty()){
father=str.top();
str.pop();
if(!str.empty())grandfather=str.top();
else grandfather=father; //防止待查找结点在第一，二层导致空指针的使用
if((father->Left==root||father->Right==root)&&((grandfather->Left
==father||grandfather->Right==father)||grandfather==father)){
Rotate(root,father,grandfather);
}else{
if(grandfather!=father){
if(grandfather->data>root->data) grandfather->Left=root;
else grandfather->Right=root;
}
}
}
return root;
}
void Rotate(Splaytree root,Splaytree father,Splaytree grandfather){
if(father->data<grandfather->data){
if(root->data<father->data){ //左一字形旋转
grandfather->Left=father->Right;
father->Right=grandfather;
father->Left=root->Right;
root->Right=father;
}else{ //左之字形旋转
father->Right=root->Left;
root->Left=father;
grandfather->Left=root->Right;
root->Right=grandfather;
}
}else if(father->data>grandfather->data){
if(root->data>father->data){ //右一字形旋转
grandfather->Right=father->Left;
father->Left=grandfather;
father->Right=root->Left;
root->Left=father;
}else{ //右之字形旋转
father->Left=root->Right;
root->Right=father;
grandfather->Right=root->Left;
root->Left=grandfather;
}
}else{ //待查找元素结点的父结点为根结点
if(father->data>root->data){
father->Left=root->Right;
root->Right=father;
}else{
father->Right=root->Left;
root->Left=father;
}
}
}
void Delete(Splaytree root,ElementType x){
Splaytree father=nullptr,min=nullptr,tempcell=nullptr;
while(root!=nullptr&&root->data!=x){
father=root;
if(root->data>x)root=root->Left;
else root=root->Right;
}
if(root==nullptr)cout<<"Not have this data."<<endl;
else{
if(root->Left&&root->Right){
father=root; //为了防止root刚好只有两个子结点
for(min=root->Right;min->Left;min=min->Left)father=min;
root->data=min->data;
root=min;
}
tempcell=root;
if(root->Left)root=root->Left;
else root=root->Right;
if(father->data>tempcell->data) father->Left=root;
else father->Right=root;
delete(tempcell);
}
}
void PrintTree(Splaytree root){
stack<Splaytree>str;
while(root||!str.empty()){
for(;root;root=root->Left)str.push(root);
if(!str.empty()){
root=str.top();
str.pop();
cout<<root->data<<endl;
root=root->Right;
}
}
}
总结
我发现将递归函数转化为非递归实现往往可以使用栈来实现，这与函数调用中经常依靠栈有关。