Splay Tree的插入操作，搜索操作，和删除操作都实现了，那么就能够使用来解题了。
指针的删除操作的处理还是那么难的，非常多坎须要避开.
同一个坎还是坑了我好多次，就是指针传递的问题，什么时候须要改动指针本身的值，就必须返回指针或者传递指针的指针，或者传递指针的的实參。
这里的删除操作就是须要改变传递到函数的指针本身的，所以我这里使用了返回指针操作。
还有删除树的问题，之前的代码没做删除操作，所以没问题，如今须要逐个节点删除，所以要小心不能把整个树都删除了。
至此， splay 树的功能差点儿相同完好了。
代码中凝视标明了几个坑都被我碰到了。
#pragma once
#include <stdio.h> class SplayTreeComplete
{
struct Node
{
int key;
Node *left, *right;
explicit Node(int k):key(k),left(NULL),right(NULL){}
/*~Node()
{教训：这种话整颗树都删除了，不能这么删除，要逐个节点删除
if (left) delete left, left = NULL;
if (right) delete right, right = NULL;
}*/
}; Node *leftRotate(Node *x)
{
Node *y = x->right;
x->right = y->left;
y->left = x;
return y;
} Node *rightRotate(Node *x)
{
Node *y = x->left;
x->left = y->right;
y->right = x;
return y;
} Node *splay(Node *root, const int key)
{
if (!root || key == root->key) return root; if (key < root->key)
{
if (!root->left) return root; if (key < root->left->key)
{
root->left->left = splay(root->left->left, key);
root = rightRotate(root);
}
else if (root->left->key < key)
{
root->left->right = splay(root->left->right, key);
if (root->left->right) root->left = leftRotate(root->left);
}
return root->left? rightRotate(root) : root;
} if (!root->right) return root;
if (root->right->key < key)
{
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
else if (key < root->right->key)
{
root->right->left = splay(root->right->left, key);
if (root->right->left) root->right = rightRotate(root->right);
}
return root->right? leftRotate(root) : root;
} Node *insert(Node *root, const int key)
{
if (!root) return new Node((int)key);//别忘了创建新的节点 root = splay(root, key);//别忘了 root = if (key == root->key) return root; Node *newNode = new Node((int)key);
if (key < root->key)
{
newNode->right = root;
newNode->left = root->left;
root->left = NULL;//别漏了这句，否则破坏了树结构
}
else
{
newNode->left = root;
newNode->right = root->right;
root->right = NULL;
}
return newNode;
} Node *deleteNode(Node *root, const int key)
{
if (!root) return root; root = splay(root, key); if (key == root->key)
{
if (!root->left)
{
Node *x = root;
root = root->right;
delete x, x = NULL;
}
else
{
Node *x = root->right;
Node *y = root->left;
delete root;
root = splay(y, key);
root->right = x;
}
}
return root;
} void preOrder(Node *root)
{
if (root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
public:
SplayTreeComplete()
{
Node *root = NULL;
int keys[] = {100, 50, 200, 40, 30, 20, 25};
int n = sizeof(keys) / sizeof(keys[0]);
for (int i = 0; i < n; i++)
{
root = insert(root, keys[i]);
} printf("\nInser create Preorder traversal Splay tree is \n");
preOrder(root);
putchar('\n'); root = splay(root, 50);
bool found = root->key == 50; printf("\n50 is %s the tree\n", found? "in" : "not in"); root = deleteNode(root, 50);//root 发生改变了，所以必须返回新的指针值 root = splay(root, 50);
found = root->key == 50; printf("\n50 is %s the tree\n", found? "in" : "not in"); printf("\nInser create Preorder traversal Splay tree is \n");
preOrder(root);
putchar('\n'); deleteTree(root);
} void deleteTree(Node *root)
{
if (root)
{
deleteTree(root->left);
deleteTree(root->right);
delete root, root = NULL;
}
}
};
