|
http://blog.csdn.net/chenbolyfxinsui/article/details/25461817 2014/5/10 by lyf @七里外风车磨坊 今天我们来讨论讨论二叉查找树,首先我们来看看二叉查找树的概念.
什么是二叉查找树呢?顾名思义，二叉查找树是按照二叉树的结构来进行组织的，这样的一棵二叉树可以采用链表的形式来加以描述,这样的链表包含两个指针域 （left_child,right_child），以及一个数据域(data) 树中的每个节点NODE，都采用链表中的节点加以表示，left_child与right_child分别指向树中节点的左孩子与右孩子，若树中的节点没有左孩子或者右孩子，则对应的left_child或者right_child为空NULL。树的叶子节点左右孩子均为空。二叉查找树除了满足上述基本的性质之外，还应满足如下的二叉查找树的性质： 设a为二叉查找树中的一个节点（这里假设使用data(a)为取节点a对应的数据域,后面的操作于此相同） 1. 若b为a的左子树中的一个节点,则必定有data(a)>data(b),即以a为根节点的左子树中的任意节点b的数据域都不大于a节点的数据域。 2. 若b为a的右子树中的一个节点,则必定有data(a)<=data(b),即以a为根节点的右子树中的任意节点b的数据与都不小于a节点的数据域。 3. 二叉查找树，按照中序遍历该二叉查找树，其输出结果是有序的。
如下图所示即为满足二叉查找树的一棵树  下面我们采用c语言来描述二叉查找树以及对二叉查找树的相关操作。
一、使用c语言定义二叉树的数据结构 typedef struct TreeNode{ void *data; //数据域 struct TreeNode* left_child; //左指针域 struct TreeNode* right_child;//右指针域 }TreeNode,*BinaryTree; 根据二叉查找树的定义，我们采用结构体定义二叉查找树,该结构体中包含了一个数据域（data）,和两个指向该结构体类型的两个指针域(left_child,right_child).分别用于指向当前节点的左孩子和右孩子。其实在这个结构体中我们还可以增加一个指针域,用于指向节点的父节点（parent)。
二.二叉查找树的基本操作.
在二叉查找树中，我们提供了创建一棵二叉查找树，插入新的节点到二叉查找树中,以及遍历这颗二叉查找树,删除二叉查找树中的某个节点，查找节点是否存在二叉查找树中.
1.首先我么来讨论插入一个节点到二叉查找树中。 分析:既然要插入一个节点到二叉查找树中，我们首先是要找到这个节点应该插入到二叉查找树的什么位置上。 显而易见的是新插入的节点一定是作为一个叶子节点存在二叉查找树中的。 继续，怎样找到这个节点应该插入到二叉查找树的什么位置上呢? 其实我们只需要用待插入的节点从二叉查找树的根节点遍历这颗二叉查找树，用待插入的节点去和二叉查找树中的节点进行比较，若待插入的节点比当前节点的值小 则进入到当前节点的左子树中进行比较，否则进入到当前节点的右子树中进行比较,如此返回操作.直到当前的节点的左或右孩子为空，根据当前节点的大小判断 待插入的节点应该插入在当前节点的左孩子(若当前节点值大于待插入节点的值)，还是右孩子中。 注意:需要注意的是若二叉查找树最开始就没有，即为一棵空二叉查找树,则我们就直接用待插入的新节点作为整个二叉查找树的根节点即可.
如下图模拟11插入到一棵二叉查找树中
code:使用c语言实现二叉树的插入操作。//插入节点到二叉查找树中 //插入节点到二叉查找树中 void InsertNode(BinaryTree* root,const void *data,int size,int(*comp)(const void*,const void*)){
if(*root==NULL){//二叉树为一棵空树
InitBinaryTree(root,data,size); //将当前节点作为二叉查找树的根节点 return; } //分配待插入的新节点 TreeNode*newNode=(TreeNode*)malloc(sizeof(TreeNode)); newNode->data=(void*)malloc(size); memcpy(newNode->data,data,size); newNode->left_child=newNode->right_child=NULL;
//对节点进行遍历操作，寻找查找位置 TreeNode*node=(*root); while(node->left_child!=newNode&&node->right_child!=newNode){ if(comp(data,node->data)<0){//待插入的节点值大于该节点的值 if(node->left_child==NULL) node->left_child=newNode; else node=node->left_child; }else{ if(node->right_child==NULL){ node->right_child=newNode; } else node=node->right_child; } } } //创建一棵二叉查找树，即初始化根节点 void InitBinaryTree(BinaryTree* root,const void *data,int size){ *root=(BinaryTree)malloc(sizeof(TreeNode)); (*root)->data=(void*)malloc(size); (*root)->left_child=(*root)->right_child=NULL; memcpy((*root)->data,data,size); }
2.二叉查找树的遍历操作。 根据二叉查找树的性质可以知道,按照中序的方式遍历一棵二叉查找树，遍历出来的顺序即为一个有序的序列. 遍历操作的时候，我们按照递归的方式进行遍历，即先遍历二叉查找树的左子树，在遍历二叉查找树的右子树。 当然我们也可以借助于栈进行非递归遍历操作.
code:c语言遍历二叉查找树(递归方式） //遍历这颗二叉排序树 void showTree(BinaryTree root,void (*print)(const void*)){ if(root!=NULL){ showTree(root->left_child,print); print(root->data); showTree(root->right_child,print); } } 3.查找值是否存在于二叉查找树中. 查找值是否存在于二叉查找树中只需要,只需要遍历该二叉查找树，使用二叉查找树中的每个节点和带查找的值进行比较，若该节点的值小于待查找节点的值 则进入到节点的左孩子中查找操作，否则进入到右孩子节点中查找操作.直到找到节点的值为待查找的值,否则二叉查找树中不存在待查找的节点. cod:c 语言实现查找节点是否存在于二叉查找树中 //查找指定的节点是否存在于二叉排序树中 int findDataInBinarryTree(BinaryTreeroot,void *data,int(*comp)(const void*,const void*)){ TreeNode*node=root; while(NULL!=node){ if(comp(node->data,data)==0){ return 1; }else if(comp(node->data,data)>0){ node=node->left_child; }else{ node=node->right_child; } } return 0; } 递归方式实现查找: int findDataInBinarryTree(BinaryTree root,void *data,int (*comp)(const void*,const void*)){
if(NULL!=root){ if(comp(root->data,data)==0){ return 1; } if(comp(root->data,data)>0){ return findDataInBinarryTree(root->left_child,data,comp); }else{ return findDataInBinarryTree(root->right_child,data,comp); } } return 0; }
4.二叉查找树的删除操作 二叉查找树的删除，应该算是这几个操作中比较复杂的一个。 二叉查找树在删除节点后应该保证二叉查找树的性质,因此在执行删除操作后任然需要保证这一棵二叉树为一棵二叉查找树 删除操作进行的第一步操作是首先要查找到待删除的节点。 （1）首先我们想到的是待删除的节点为叶子节点，即我们只需要将待删除节点（叶子节点）直接从二叉查找树中删除即可，因为删除叶子节点不会破坏二叉查找树的性质。 如下图所示:（需要注意的是若待删除的节点为根节点，即只有一个节点的树，直接将根节点赋值为空，删除根节点即可)
(2) 若待删除的节点不是叶子节点,但是以待删除节点为根节点的子树是一棵单子树（即待删除节点的左右孩子只有一个存在),则需要做的操作是将待删除节点父节点的指向修改为待删除节点的孩子节点(即左孩子或右孩子），然后删除该节点即可（特别的当删除的节点为根节点,则将待删除节点的左孩子或右孩子的节点作为根节点即可)。 （3）若待删除的节点的左右子树均不为空，则我们在进行节点删除操作后需要保持二叉查找树的性质，则需要做的操作是以待删除节点的左孩子为根节点的子树k中寻找最大的节点值r（遍历子树的右子树），将节点r的值赋值给待删除节点h的值，将节点r的左子树赋值给节点r父节点的右孩子，删除节点r即可.（如图七所示)
特别地，当子树k的右孩子为空，则节点k即为待删除节点h的左子树中的最大节点，则将节点k的值赋给待删除节点h,让节点k的父节点的左孩子指向节点k的左孩子,删除节点k即可。 实际上在子树k的右孩子为空的时候我们还要另外的一种思考方式，即改变待删除节点h的父节点c指向，若待删除节点h,为父节点c的左孩子，则父节点c的左孩子指向为待删除节点h的左孩子节点k，若待删除节点h为右孩子，则父节点c的右孩子指向为待删除节点h的左孩子节点k，将待删除的节点h的右孩子m赋值给,待删除节点h的左孩子k的右孩子，然后删除节点h即可.(此种方式不需向图八的方式给待删除节点赋值操作).
code:c语言实现删除二叉查找树中的某个节点 //删除二叉查找树中的某个节点 void delTreeNode(BinaryTree* root,void *data,int size,int(*comp)(const void*,const void*)){ //在删除一棵二叉查找树的时候，需要保持二叉排序树的特性，需要分几种情况进行删除操作 //1.若待删除的节点为叶子节点直接将该节点删除即可,并将父节点的对应的指针赋值为空 TreeNode*delnode=(*root); //待删除节点 TreeNode*delnodeParent=(*root);//待删除节点的父节点 while(delnode!=NULL){ if(comp(data,delnode->data)<0){ delnodeParent=delnode; delnode=delnode->left_child; }else if(comp(data,delnode->data)>0){ delnodeParent=delnode; delnode=delnode->right_child; }else{ //查找到待删除的节点 break; } }
if(NULL==delnode) { printf("没有查找到待删除的节点!"); return; } //待删除的节点为叶子节点 if(delnode->left_child==NULL&&delnode->right_child==NULL){ //若待删除的节点为根节点，则直接删除该节点即可，树为空树 if(delnode==*root) (*root)=NULL; else if(delnodeParent->left_child==delnode)//若待删除的节点为父节点的左孩子 delnodeParent->left_child=NULL; else delnodeParent->right_child=NULL; //释放该节点的内存空间 free(delnode); delnode=NULL; }
//以待删除节点为根节点的子树为单子树，则修改待删除节点父节点的孩子节点为待删除节点的孩子 else if(delnode->left_child==NULL||delnode->right_child==NULL){ //同样若待删除的节点为根节点,该变根节点的指针指向为待删除节点的孩子节点 if(delnode==*root){ if(delnode->left_child!=NULL) (*root)=delnode->left_child; else (*root)=delnode->right_child; } //待删除节点不为根节点 else{ if(delnodeParent->left_child==delnode){ if(delnode->left_child!=NULL) delnodeParent->left_child=delnode->left_child; else delnodeParent->left_child=delnode->right_child; }else{ if(delnode->left_child!=NULL) delnodeParent->right_child=delnode->left_child; else delnodeParent->right_child=delnode->right_child; } } free(delnode); delnode=NULL; }
//以待删除节点的子树都不为空,这里的做法是以待删除节点的左孩子为根节点的子树中寻找最大的节点， //即遍历到该子树最右边的孩子节点将该节点的值赋值给待删除节点,删除该节点即可 else if(delnode->left_child!=NULL&&delnode->right_child!=NULL){ TreeNode* tempNode=delnode->left_child; TreeNode*tempParentNode=delnode->left_child; while(tempNode->right_child!=NULL){ tempParentNode=tempNode; tempNode=tempNode->right_child; } memcpy(delnode->data,tempNode->data,size); if(tempNode==tempParentNode){ //待删除节点的左孩子节点的右子树为空,则待删除节点的左孩子即为寻找的节点，将寻找到的节点的左孩子连接到待删除节点的左子树上 delnode->left_child=tempNode->left_child; }else{ //找到待删除节点的左孩子节点的右子树中较大节点,将较大节点的父节点的右子树连接到较大节点的左子树 tempParentNode->right_child=tempNode->left_child; } free(tempNode); tempNode=NULL; } }
5.释放二叉查找树的内存空间 二叉查找树的空间是使用指针进行内存空间动态分配的，所以在使用完毕之后我们不要忘记释放所分配的内存空间. 释放一棵二叉查找树的空间可以这样操作，释放这棵树的左孩子，释放这颗树的右孩子，释放根节点.
code:c语言实现释放二叉查找树的动态内存空间
//释放二叉查找树的空间 void freeBinarySpace(BinaryTree* root){ //释放二叉树的内存空间 if(*root!=NULL){ //释放左子树 freeBinarySpace(&(*root)->left_child); //释放右子树 freeBinarySpace(&(*root)->right_child); //释放本身的内存空间 free((*root)->data);//释放数据域 (*root)->data=NULL; free((*root)); *root=NULL; } } 6.其他的一些辅助公共操作方法
int intBig(const void*data_one,const void*data_two){return *(int*)data_one-*(int*)data_two;} //打印输出函数 void printInt(const void*data){printf("%d",*(int*)data);}
三.二叉查找树的算法分析 在二叉查找树中查找一个关键字，恰好是走了一条从二叉树的根节点到该节点的路径的过程.在二叉查找树中查找一个关键字与二叉树中节点的比较次数最大不超过该二叉树的深度. 当含有n个节点的二叉查找树的平均查找长度是取决于二叉查找树的形态的,当在进行二叉查找树插入n个数据为有序的n个数据的时候，则得到的二叉查找树为一棵单子树,则树的深度为n 则平均查找长度为(n+1)/2.这是最极端的情况 最好的情况就是，建立的n个数据的二叉排序树的形态与二分查找的判定树相当,其平均查找长度与log2(n) 成正比。 二叉查找树的各项基本操作的运行时间都是o(h)，h为二叉排序树的高度，含有n个节点的二叉查找树在最优的情况下树的高度为o(logn),所以要使得二叉查找树最优，就的使得 二叉查找树的高度为o(logn),可以通过平衡二叉树对其进行优化。
毕！
参考：算法导论第二版，数据结构（c语言版) |
|
|
