从二叉排序树到平衡二叉树再到红黑树系列1

本文主要是介绍从二叉排序树到平衡二叉树再到红黑树系列1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近想写一些关于红黑树的博客，既想写的全面，又直观，但是又不知道从哪里入手。斟酌再三，还是从最简单的二叉排序树开始写。

二叉排序树（Binary Sort Tree）又叫二叉查找树。它是一种特殊结构的二叉树。其或为空树，或具备下列性质：

（1）若它的左子树不为空，则左子树上所有结点的值均小于它的根节点的值。

（2）若它的右子树不为空，则左子树上所有结点的值均大于它的根节点的值。

显然，它的中序遍历就是一个递增的有序序列。

定理：在一棵高度为h的二叉搜索树上，动态集合上的操作serach,minmum,maxmum,successor,predecessor可以在O(h)时间内完成。

即查找给定结点，查找最大值最小值，以及给定结点的前驱后继，他们均可以在O(h)时间内完成。具体见算法导论第三版第12章

插入和删除

为了保持二叉排序树的有序性质，插入和删除操作会引起二叉排序树的动态变化，由于插入的结点总是成为叶子节点，而删除的结点还要修改其左右子树的指向，所以插入一个结点相比删除一个结点的处理相对复杂。

插入：首先要查找要插入节点的位置，然后插入即可。

删除：删除一个结点node要考虑三种情况：

1 node没有左右孩子节点，这种情况最为简单，直接删除它，再将父节点原来指向node的指针置NULL就行。

2 node只有一个孩子，那么将这个孩子提升到node的位置上，并修改node的父节点即可。

3 node有两个孩子。那么寻找node的后继y（中序遍历的下一个元素）,让y占据node的位置。同时node原来的右子树部分称为y的新的右子树，

node的左子树称为y的新的左子树。简单点说：就是交换要删除的node节点与node节点右子树的最左边节点位置。这样满足中序遍历递增性质。

  时刻记住二叉排序树中序是递增的，当删除一个结点时，该结点的位置就要被其后继，也就是要删除节点右子树的中序遍历第一个节点（同时也是右子树的最左节点）

下面举例说明，如图所示：

下面直接贴代码：

#include<stdio.h>
#include<stdlib.h>
#define error -1
#define OK 1
typedef struct BSTNode
{struct BSTNode *lchild,*rchild;int data;
}BSTNode,*BSTree;
/**
*@auther:jungege 2015 5.13
**/
//插入元素到二叉排序树中
BSTree InsertBST(BSTree bst,int key)
{BSTree node,parent,new_node;if(bst == NULL)//为空树，创建根节点{bst = (BSTree)malloc(sizeof(BSTNode));bst->data = key;bst->lchild = NULL;bst->rchild = NULL;return bst;}node = bst;//找到插入位置,保存bstwhile(node != NULL){if(node->data == key)return bst;else{parent = node;//记录父节点，最后保存的是插入节点的父节点if(node->data < key)node = node->rchild;elsenode = node->lchild;}}//创建节点，将新key插入到指定位置，插入的节点一定是叶子节点new_node = (BSTree) malloc (sizeof(BSTNode));if(parent->data < key)//插入到parent右孩子parent->rchild = new_node;elseparent->lchild = new_node;new_node->data = key;new_node->lchild = NULL;new_node->rchild = NULL;return bst;
}
//删除二叉排序树中元素
int deleteBST(BSTree bst, int key)
{BSTree node=bst,pre=NULL,nearestkey,nearest_pre;if(bst == NULL)return -1;//空树//寻找删除节点位置while(node != NULL && node->data != key){pre = node;//保存父结点if(node->data > key)node = node->lchild;elsenode = node->rchild;}if(node == NULL)return 0;//没有要删除的节点//找到要删除的节点node和其父节点preif((node->lchild != NULL) && (node->rchild !=NULL))//***要删除节点有左右孩子{nearestkey = node->rchild;nearest_pre = node;while(nearestkey->lchild != NULL){nearest_pre = nearestkey;//pre指向被nearestkey节点的父节点nearestkey = nearestkey->lchild;}node->data = nearestkey->data;//直接赋值，避免交换节点//处理nearestkey节点的子节点,显然其为最左节点，所以不存在左子树，只需处理其右子树nearest_pre->lchild = nearestkey->rchild;free(nearestkey);}else if(node->lchild == NULL && node->rchild !=NULL)//***要删除节点只有右孩子{if(pre->rchild == node)// node是其父节点的右子树pre->rchild = node->rchild;else pre->lchild = node->rchild;free(node);//释放节点}else if(node->lchild != NULL && node->rchild ==NULL)//***要删除节点只有左孩子{if(pre->rchild == node)// node是其父节点的右子树pre->rchild = node->lchild;else pre->lchild = node->lchild;free(node);//释放节点}else//***被删除节点没有子树{if(pre->lchild == node)pre->lchild = NULL;if(pre->rchild == node)pre->rchild = NULL;free(node);}return 1;//删除成功
}//查找
int SearchBST(BSTree bst,int key)
{printf("%d ",bst->data);if(bst==NULL)return error;if(bst->data == key)return OK;else if(key < bst->data)SearchBST(bst->lchild,key);elseSearchBST(bst->rchild,key);
}//中序遍历
void inorder(BSTree root)
{if(root){inorder(root->lchild);printf("%d ",root->data);inorder(root->rchild);}
}void main()
{int a[10]={3,2,6,5,1,9,7,7,10,8};int i;BSTree root=NULL;//初始化非常重要，不然插入时就无法判断树空//按数组构建二叉排序树for(i=0;i<10;i++)root = InsertBST(root,a[i]);//中序遍历inorder(root);printf("\n删除节点6:");deleteBST(root,6);printf("\n删除节点6后中序遍历:");inorder(root);printf("\n");
}

运行结果如下：

这篇关于从二叉排序树到平衡二叉树再到红黑树系列1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---