二叉排序树
1.定义
二叉排序树(Binary Search Tree)又称二叉搜索(查找)树，其定义如下：
(1)若它的左子树非空，则左子树上所有结点的权值都比根结点的权值小;
(2)若它的右子数非空，则右子树上所有结点的权值都比根结点的权值大;
(3)左、右子树本身又是一棵二叉排序树。
以上既是二叉排序树的定义，同时也是它的性质。从定义可以看出，二叉排序树的定义是一个递归的定义。对于一棵二叉排序树的中序遍历则是一个递增有序序列。
2.二叉排序树的插入Insert
根据二叉排序树的递归定义，进行插入操作的时候可以用递归实现，其插入过程如下：
(1)如果二叉排序树为空，则创建一个关键字为key的结点，并将其作为根结点;
(2)否则将key和根结点的key值比较，若相等则返回;
1)若key值小于根结点的key值，判断根结点的左孩子是否为空，如果为空，则创建一个关键字为key的结点，并将该结点作为根结点的
左孩子;如果不为空，则递归插入到该根结点的左子树当中。
2)若key值大于根结点的key值，判断根结点的右孩子是否为空，如果为空，则创建一个关键字为key的结点，并将该结点作为根结点的
右孩子;如果不为空，则递归插入到该根结点的右子树当中。
递归实现：
void insert(BSTNode *&root,ElemType key) //注意这里为什么用指针的引用 { if(root==NULL) //如果该树为空 { root=(BSTNode *)malloc(sizeof(BSTNode)); root->key=key; root->left=NULL; root->right=NULL; } else { if(root->key==key) return; else if(root->key>key) //key小于根结点的权值 { if(root->left==NULL) //root的左孩子为空，则创建一个结点作为root的左孩子 { BSTNode *p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=key; p->left=NULL; p->right=NULL; root->left=p; } else insert(root->left,key); //递归插入到左子树中 } else //key大于根结点的权值 { if(root->right==NULL) //root的右孩子为空，则创建一个结点作为root的右孩子 { BSTNode *p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=key; p->left=NULL; p->right=NULL; root->right=p; } else insert(root->right,key); //递归插入到右子树中 } } }
非递归实现：
void insert(BSTNode *&root,ElemType key) //非递归实现 { if(root==NULL) { root=(BSTNode *)malloc(sizeof(BSTNode)); root->key=key; root->left=NULL; root->right=NULL; return; } BSTNode *p1,*p2; int flag; p1=root; while(p1!=NULL) { p2=p1; if(key==p1->key) return; else if(key<p1->key) { p1=p1->left; flag=0; } else { p1=p1->right; flag=1; } } BSTNode *p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=key; p->left=NULL; p->right=NULL; if(flag==0) p2->left=p; else p2->right=p; }
3.二叉排序树的查找
最坏情况的查找是二叉排序树行成的是一个高度为n的线性树，其平均查找长度跟顺序查找的相同，为n+1/2;
最好情况是与二分判定树形态相同，其平均查找长度和二分查找相同为logn;
BSTNode* search(BSTNode *root,ElemType key) { if(root==NULL||root->key==key) return root; else if(key<root->key) search(root->left,key); else search(root->right,key); } BSTNode* search(BSTNode *root,ElemType key) { if(root==NULL||root->key==key) return root; BSTNode *p=root; while(p!=NULL&&key!=p->key) { if(key<p->key) p=p->left; else p=p->right; } return p; }
关于二叉排序树的运用可以看一下POJ2418
http://poj.org/problem?id=2418
这道题目有2种解法，一种是采用二叉排序树去实现，一种是直接采用STL模板实现，下面只给出STL的实现。
#include<iostream> #include<string> #include<map> #include<algorithm> using namespace std; int main(void) { int i; int n=0; map<string,int> tree; map<string,int>::iterator it; char str[31]; while(gets(str)) { string name; for(i=0;str[i]!='\0';i++) { name+=str[i]; } tree[name]++; //map<string,int>若没有赋初值，则value值默认为0 n++; } for(it=tree.begin();it!=tree.end();it++) { cout<<it->first; printf(" %.4lf\n",100*(double)(it->second)/n); } return 0; }