2017-02-18 09:27:00

```typedef struct Node
{
int m_key;
int m_height;
Node* m_lChild;
Node* m_rChild;
Node(int key)
{
m_key = key;
m_height = 1;
m_rChild = m_lChild = nullptr;
}
}* PNode;```

1.左左情况

```/* 左左情况 */
PNode LL_Rotate(PNode & p)
{
cout << "LL\n";

PNode top = p->m_lChild;
p->m_lChild = top->m_rChild;
top->m_rChild = p;

p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
top->m_height = max(Height(top->m_lChild), Height(top->m_rChild)) + 1;

}```

2.右右情况

```/* 右右情况 */
PNode RR_Rotate(PNode & p)
{
cout << "RR\n";

PNode top = p->m_rChild;
p->m_rChild = top->m_lChild;
top->m_lChild = p;

p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
top->m_height = max(Height(top->m_lChild), Height(top->m_rChild)) + 1;

}```

3.左右情况

```/* 左右情况 */
PNode LR_Rotate(PNode & p)
{
cout << "LR\n";

p->m_lChild = RR_Rotate(p->m_lChild);
return LL_Rotate(p);
}```

4.右左情况

```/* 右左情况 */
PNode RL_Rotate(PNode & p)
{
cout << "RL\n";

p->m_rChild = LL_Rotate(p->m_rChild);
return RR_Rotate(p);
}
```

```/* 计算当前节点的高度 */
int Height(PNode & p)
{
return (p == nullptr) ? 0 : p->m_height;
}

/* 找到该节点下的最小值节点，返回该最小值，注意参数不是引用传递 */
int FindMin(PNode  p)
{
while (p->m_lChild)
p = p->m_lChild;
return p->m_key;
}```

1.插入

```/* 添加操作 */
bool Add(int key, PNode & p)
{
if (p == nullptr)
{
p = new Node(key);
return true;
}
else
{
if (key == p->m_key)//已存在，直接退出
return false;

if (key < p->m_key)//左子树
{
{
if (Height(p->m_lChild) - Height(p->m_rChild) == 2)//高度差等于2，得旋转调整
{
if (key < p->m_lChild->m_key)
p = LL_Rotate(p);//左左情况
else
p = LR_Rotate(p);//左右情况
}
p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;//更新高度
return true;
}
else
return false;
}

else //右子树
{
{
if (Height(p->m_lChild) - Height(p->m_rChild) == -2)
{
if (key > p->m_rChild->m_key)
p = RR_Rotate(p);
else
p = RL_Rotate(p);
}
p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;//更新高度
return true;
}
else
return false;
}
}
}```

2.删除

```/* 删除操作 */
bool Delete(int key, PNode & p)
{
if (p == nullptr)
return false;
else
{
if (key == p->m_key)//找到该点
{
if (p->m_lChild && p->m_rChild)//左右孩子都存在
{
p->m_key = FindMin(p->m_rChild);//找到该节点下的最小节点
Delete(p->m_key, p->m_rChild);//转化为: 删除找到的这个最小节点
}
else if (!p->m_lChild && !p->m_rChild)//左右孩子都不存在
{
PNode t = p;//注意p是引用类型
p = nullptr;
delete t;
return true;
}
else//左右孩子只存在一个
{
PNode t = p;
p = (p->m_lChild == nullptr) ? p->m_rChild : p->m_lChild;
delete t;
return true;
}
}

else if (key < p->m_key)//在左子树删除
{
if (Delete(key, p->m_lChild))
{
if (Height(p->m_lChild) - Height(p->m_rChild) == 2)
{
if (key < p->m_lChild->m_key)
p = LL_Rotate(p);
else
p = LR_Rotate(p);
}

p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
return true;
}
else
return false;
}
else//在右子树删除
{
if (Delete(key, p->m_rChild))
{
if (Height(p->m_lChild) - Height(p->m_rChild) == -2)
{
if (key > p->m_rChild->m_key)
p = RR_Rotate(p);
else
p = RL_Rotate(p);
}
p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
return true;
}
else
return false;
}
}
}```

3.查找

```/* 查找操作 */
bool Find(int key, PNode & p)
{
if (p == nullptr)
return false;
else
{
if (key == p->m_key)
return true;
else if (key < p->m_key)
return Find(key, p->m_lChild);
else
return Find(key, p->m_rChild);
}
}```

4.层次遍历

```/* 层次遍历，和普通的层次遍历不一样，打印的结果模拟了树的形状 */
void PrintTheLevel(PNode & p, int level)
{
if (p == nullptr || level <= 0)
return;
if (level == 1)
{
cout << p->m_key << "," << p->m_height << "  ";//输出节点及对应的高度
return;
}

PrintTheLevel(p->m_lChild, level - 1);
PrintTheLevel(p->m_rChild, level - 1);
}

void LevelOrder(PNode & p)
{
int depth = Height(p);
for (int i = 1; i <= depth; i++)
{
PrintTheLevel(p, i);//打印树的第i行
cout << endl;
}
}
```

```#define _CRT_SECURE_NO_DEPRECATE

#include
#include
using namespace std;

typedef struct Node
{
int m_key;
int m_height;
Node* m_lChild;
Node* m_rChild;
Node(int key)
{
m_key = key;
m_height = 1;
m_rChild = m_lChild = nullptr;
}
}* PNode;

PNode pRoot = nullptr;//根节点

/* 计算当前节点的高度 */
int Height(PNode & p)
{
return (p == nullptr) ? 0 : p->m_height;
}

/* 找到该节点下的最小值节点，返回该最小值，注意参数不是引用传递 */
int FindMin(PNode  p)
{
while (p->m_lChild)
p = p->m_lChild;
return p->m_key;
}

/* 左左情况 */
PNode LL_Rotate(PNode & p)
{
cout << "LL\n";

PNode top = p->m_lChild;
p->m_lChild = top->m_rChild;
top->m_rChild = p;

p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
top->m_height = max(Height(top->m_lChild), Height(top->m_rChild)) + 1;

}

/* 右右情况 */
PNode RR_Rotate(PNode & p)
{
cout << "RR\n";

PNode top = p->m_rChild;
p->m_rChild = top->m_lChild;
top->m_lChild = p;

p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
top->m_height = max(Height(top->m_lChild), Height(top->m_rChild)) + 1;

}

/* 左右情况 */
PNode LR_Rotate(PNode & p)
{
cout << "LR\n";

p->m_lChild = RR_Rotate(p->m_lChild);
return LL_Rotate(p);
}

/* 右左情况 */
PNode RL_Rotate(PNode & p)
{
cout << "RL\n";

p->m_rChild = LL_Rotate(p->m_rChild);
return RR_Rotate(p);
}

/* 添加操作 */
bool Add(int key, PNode & p)
{
if (p == nullptr)
{
p = new Node(key);
return true;
}
else
{
if (key == p->m_key)//已存在，直接退出
return false;

if (key < p->m_key)//左子树
{
{
if (Height(p->m_lChild) - Height(p->m_rChild) == 2)//高度差等于2，得旋转调整
{
if (key < p->m_lChild->m_key)
p = LL_Rotate(p);//左左情况
else
p = LR_Rotate(p);//左右情况
}
p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;//更新高度
return true;
}
else
return false;
}

else //右子树
{
{
if (Height(p->m_lChild) - Height(p->m_rChild) == -2)
{
if (key > p->m_rChild->m_key)
p = RR_Rotate(p);
else
p = RL_Rotate(p);
}
p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;//更新高度
return true;
}
else
return false;
}
}
}

/* 删除操作 */
bool Delete(int key, PNode & p)
{
if (p == nullptr)
return false;
else
{
if (key == p->m_key)//找到该点
{
if (p->m_lChild && p->m_rChild)//左右孩子都存在
{
p->m_key = FindMin(p->m_rChild);//找到该节点下的最小节点
Delete(p->m_key, p->m_rChild);//转化为: 删除找到的这个最小节点
}
else if (!p->m_lChild && !p->m_rChild)//左右孩子都不存在
{
PNode t = p;//注意p是引用类型
p = nullptr;
delete t;
return true;
}
else//左右孩子只存在一个
{
PNode t = p;
p = (p->m_lChild == nullptr) ? p->m_rChild : p->m_lChild;
delete t;
return true;
}
}

else if (key < p->m_key)//在左子树删除
{
if (Delete(key, p->m_lChild))
{
if (Height(p->m_lChild) - Height(p->m_rChild) == 2)
{
if (key < p->m_lChild->m_key)
p = LL_Rotate(p);
else
p = LR_Rotate(p);
}

p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
return true;
}
else
return false;
}
else//在右子树删除
{
if (Delete(key, p->m_rChild))
{
if (Height(p->m_lChild) - Height(p->m_rChild) == -2)
{
if (key > p->m_rChild->m_key)
p = RR_Rotate(p);
else
p = RL_Rotate(p);
}
p->m_height = max(Height(p->m_lChild), Height(p->m_rChild)) + 1;
return true;
}
else
return false;
}
}
}

/* 查找操作 */
bool Find(int key, PNode & p)
{
if (p == nullptr)
return false;
else
{
if (key == p->m_key)
return true;
else if (key < p->m_key)
return Find(key, p->m_lChild);
else
return Find(key, p->m_rChild);
}
}

/* 层次遍历，和普通的层次遍历不一样，打印的结果模拟了树的形状 */
void PrintTheLevel(PNode & p, int level)
{
if (p == nullptr || level <= 0)
return;
if (level == 1)
{
cout << p->m_key << "," << p->m_height << "  ";//输出节点及对应的高度
return;
}

PrintTheLevel(p->m_lChild, level - 1);
PrintTheLevel(p->m_rChild, level - 1);
}

void LevelOrder(PNode & p)
{
int depth = Height(p);
for (int i = 1; i <= depth; i++)
{
PrintTheLevel(p, i);
cout << endl;
}
}

int main()
{

return 0;
}

```