开发者社区> eddie小英俊> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

二叉排序(查找)树

简介:
+关注继续查看

  二叉排序树

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;
}

如需转载自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
图与二叉查找树
图的存储方式 1、邻接矩阵(二维数组) //邻接矩阵构建图 #include "stdafx.h" #include #include using namespace std; void Creat_graph(...
839 0
二叉排序树
二叉排序树又称二叉查找树,它是一种对排序和查找都很有用的特殊二叉树。 定义: (1)若它的左子树不为空,则左子树上的所有结点的值均小于它的根结点的值; (2)若它的右子树不为空,则右子树上所有结点的值均小于它的根结点上的值; (3)它的左右子树本身也分别为二叉排序树。
1036 0
二叉查找树(二叉排序树)(C语言)
#include #include "fatal.h" struct TreeNode; typedef struct TreeNode *Position; typedef struct TreeNode *SearchTree; typedef int ElementType; ...
558 0
925
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载