C语言之平衡二叉树详解
//查找节点
//找最大节点
Node *maxNode(Node *curRoot)
{
if (curRoot == NULL)
return NULL;
//往右边找
while (curRoot->RChild)
curRoot = curRoot->RChild;
return curRoot;
}
//找最小节点
Node *minNode(Node *curRoot)
{
if (curRoot == NULL)
return NULL;
while (curRoot->LChild)
curRoot = curRoot->LChild;
return curRoot;
}
//删除数据
Node *deleteNode(Node *curRoot, Ty data)
{
//删除数据有四个大情况
if (curRoot == NULL) //当前节点是空的
return NULL; //删除了个寂寞直接结束掉整个函数
if (data < curRoot->data) //要删除的数据比当前节点的数据小
{
//往左边跑
curRoot->LChild = deleteNode(curRoot->LChild, data);
//获取新高度
curRoot->height = GET_NEW_HEIGHT(curRoot);
//判断需不需要调整
if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
curRoot = HEIGHT(curRoot->RChild->LChild) > HEIGHT(curRoot->RChild->RChild) ? RL_Rotation(curRoot) : RR_Rotation(curRoot);
}
else if (data > curRoot->data) //要删除的数据比当前节点的数据大
{
//往右边跑
curRoot->RChild = deleteNode(curRoot->RChild, data);
curRoot->height = GET_NEW_HEIGHT(curRoot);
if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
curRoot = HEIGHT(curRoot->LChild->RChild) > HEIGHT(curRoot->LChild->LChild) ? LR_Rotation(curRoot) : LL_Rotation(curRoot);
}
else
{ //要删除的数据和当前节点的数据一样大
//针对于curRoot这个节点做删除操作
//主要有两个主要的情况
if (curRoot->LChild && curRoot->RChild) // curRoot有左子树和右子树
{
//先判断左右子树的高度，将高度比较高的子树的节点拿到上面来
if (HEIGHT(curRoot->LChild) > HEIGHT(curRoot->RChild))
{ //左子树的高度比右子树的高度高
//找到左子树的最大节点
Node *max = maxNode(curRoot->LChild);
//找到之后就将max的数据替换curRoot的数据
curRoot->data = max->data;
//赋值完成之后继续递归，然后释放掉max对应的节点，不能直接在这里释放，因为要调整树的高度
curRoot->LChild = deleteNode(curRoot->LChild, max->data);
}
else
{ //左子树的高度小于等于右子树的高度
//找到右子树的最小节点
Node *min = minNode(curRoot->RChild);
curRoot->data = min->data;
curRoot->RChild = deleteNode(curRoot->RChild, min->data);
}
}
else //上一种情况的否定，即curRoot没有子树或者只有一边
{
//释放内存
Node *temp = curRoot;
// curRoot拿到存在的子树
curRoot = curRoot->LChild ? curRoot->LChild : curRoot->RChild;
free(temp);
}
}
return curRoot; //删除完成之后就返回当前节点
}