08-二叉排序树的创建和插入操作

二叉排序树的创建和插入操作

问题描述

实现算法，要求根据一个元素序列创建一棵二叉排序树，并将给定的元素插入二叉排序树中，使其仍然是一棵二叉排序树。

【二叉排序树的定义】

二叉排序树也称为二叉查找树，它或者是一棵空二叉树，或者具有以下性质。

• 如果二叉排序树的左子树不空，则左子树上的每一个节点的元素值都小于其对应的根节点元素值。
• 如果二叉排序树的右子树不空，则右子树上的每一个节点的元素值都大于其对应的根节点的元素值。
• 该二叉排序树的左子树和右子树也满足前两个性质，即左子树和右子树也是一棵二叉排序树。

显然，这是一个递归的二叉排序树定义。例如，一棵二叉排序树如图9.9所示。

图9.9　一棵二叉排序树

从图9.9中不难看出，每个节点元素值都大于其所有左子树中的节点元素值，且小于其所有右子树中的节点元素值。例如，80大于左子节点的元素值70，小于右子节点的元素值87。

【分析】

二叉排序树的插入操作过程其实就是二叉排序树的建立过程。二叉排序树的插入操作从根节点开始，首先要检查当前节点元素是否是要查找的元素，如果是，则不进行插入操作；否则，将节点插入查找失败时节点的左指针或右指针处。在算法的实现过程中，需要设置一个指向下一个要访问节点的双亲节点指针parent，就是需要记下前驱节点的位置，以便在查找失败时进行插入操作。

初始时，当前节点指针cur为空，说明查找失败，将插入的第1个元素作为根节点元素，然后让parent指向根节点元素。如果parent−>data小于要插入的节点元素值x，则需要将parent的左指针指向x，使x成为parent的左子节点元素；如果parent−>data大于要插入的节点元素值x，则需要将parent的右指针指向x，使x成为parent的右子节点元素。在整个二叉排序树的插入过程中，插入操作都是在叶子节点处进行的。

【示例】

假设一个元素序列{55,43,66,88,18,80,33,21,72}，根据二叉排序树的插入算法思想，对应的二叉排序树的插入操作过程如图9.10（a）～（i）所示。

图9.10　二叉排序树的插入操作过程

从图9.10中可以看出，通过中序遍历二叉排序树，可以得到一个有序的元素序列{18,21,33,43, 55,66,72,80,88}。

第9章\实例9-04.cpp

/********************************************
*实例说明：基于二叉排序树的查找
*********************************************/
#include<stdio.h>
#include<malloc.h>
typedef struct Node    /*二叉排序树的类型定义*/
{
    int data;
    struct Node *lchild,*rchild;
}BiTreeNode,*BiTree;
BiTree BSTSearch(BiTree T,int x);
int BSTInsert(BiTree *T,int x);
void InOrderTraverse(BiTree T);
void main()
{
    BiTree T=NULL,p;
    int table[]={55,33,44,66,99,77,88,22,11};
    int n=sizeof(table)/sizeof(table[0]);
    int x,i;
    for(i=0;i<n;i++)
        BSTInsert(&T,table[i]);
    printf("中序遍历二叉排序树得到的序列为\n");
    InOrderTraverse(T);
    printf("\n请输入要查找的元素:");
    scanf("%d",&x);
    p=BSTSearch(T,x);
    if(p!=NULL)
        printf("二叉排序树查找:元素%d查找成功.\n",x);
    else
        printf("二叉排序树查找:没有找到元素%d.\n",x);
}
BiTree BSTSearch(BiTree T,int x)
/*二叉排序树的查找操作*/
{
    BiTreeNode *p;
    if(T!=NULL)                  /*如果二叉排序树不空*/
    {
        p=T;
        while(p!=NULL)
        {
            if(p->data==x)      
                return p;
            else if(x<p->data)  
                p=p->lchild;
            else
                p=p->rchild;  
        }
    }
    return NULL;
}
int BSTInsert(BiTree *T,int x)
/*二叉排序树的插入操作*/
{
    BiTreeNode *p,*cur,*parent=NULL;
    cur=*T;
    while(cur!=NULL)
    {
        if(cur->data==x)    
            return 0;
        parent=cur;         
        if(x<cur->data)     
            cur=cur->lchild;
        else
            cur=cur->rchild;
    }
    p=(BiTreeNode*)malloc(sizeof(BiTreeNode));
    if(!p)
        exit(-1);
    p->data=x;
    p->lchild=NULL;
    p->rchild=NULL;
    if(!parent)               /*如果二叉排序树已空，则第一个节点成为根节点*/
        *T=p;
    else if(x<parent->data)
        parent->lchild=p;
    else
        parent->rchild=p;
    return 1;    
}
void InOrderTraverse(BiTree T)
/*中序遍历二叉排序树*/
{
    if(T)                              /*如果二叉排序树不空*/
    {
        InOrderTraverse(T->lchild);
        printf("%4d",T->data);     
        InOrderTraverse(T->rchild);
    }
}

运行结果如图9.11所示。

图9.11　运行结果

【特点】

• 基于二叉排序树的查找算法分为插入操作和查找操作两个部分。
• 插入操作不需要移动节点，仅需要移动节点的指针。

【效率分析】

在基于二叉排序树的查找过程中，查找某个元素的过程正好经过从根节点到要查找节点的路径，其比较的次数正好是路径长度加1，这类似于折半查找。与折半查找不同的是，由n个节点构成的判定树是唯一的，而由n个节点构成的二叉排序树则不唯一。例如，元素序列{6,12,24,30,44,55,70}对应的两棵不同形态的二叉排序树如图9.12（a）与（b）所示。

在图9.12中，假设每个元素的查找概率都相等，则在查找成功时左边的树的ASL_成功= ×(1+2×2+4×3)=，右边的树的ASL_成功= ×(1+2+3+4+5+6+7)=。

图9.12　两棵不同形态的二叉排序树

因此，平均查找长度与二叉排序树的形态有关。如果二叉排序树有n个节点，则在最坏的情况下，平均查找长度为(n+1)/2；在最好的情况下，平均查找长度为log₂n。