第十七章 高级数据表示

四、二叉搜索树

先梳理一下链表和数组方式对几种操作的利弊特点：

a.访问：链表形式，必须从首节点开始找起，直到要访问的节点为止，这个称为顺序访问。而数组方式则方便的多，可直接定位到某个元素，这称为随机访问。

b.插入/删除：对于链表形式，插入或删除操作仅需要修改前续和后续节点就可以完成；而数组方式需修改被增加或删除元素后面所有的元素。

c.查找/搜索：其实也是一种访问形式。一般情况，对于顺序排列的“数据堆”，可以通过"折半查找法”非常效率的进行查找。可折半查找，首先得定位到中间的元素，对数组而言，因为有下标，很容易定位；而对于链表定位中间元素，首先要知道数据堆里总共有多少个节点，然后从首节点开始，pnode->next一直操作下去，直至定位到中间元素，再进行比较。

如果需要一种既方便插入/删除，又方便搜索查找的数据堆形式，那该选用哪种形式呢？我们暂时不必去想如何去设计，去想出这样一种形式我们已经有了答案：二叉树。

二叉树的特点：每个节点除去item本身信息外，描述该节点还需要两个指针成员，分别为左指针，右指针。和单链表不一样的是，二叉树每个节点链接下去有两个后续节点。

为使搜索工作可以利用“折半法”，使每个节点按一种顺序的关系排列：对于节点和他的左子节点、右子节点的关系为：左子节点<节点<右子节点。

这样的一种二叉树，称为“二叉搜索树”（binary search tree.bst)。

1、二叉搜索树ADT的数据定义描述

//项目依据实际所需去定义typedef something Item;//二叉树节点定义typedef struct node{    Item item;    struct node *left;    struct node *right;}Node;//树的定义//通过定位树的根节点可以找到该数，同时增加树的节点数目丰富树的信息typedef struct tree{    Node *root;    int size;}Tree;

2、二叉搜索树的操作定义

（1）初始化一棵树

void InitializeTree(Tree *ptree){     ptree->root=NULL;     ptree->size=0;}

(2)判断树是否为空(判断为满也类似）

int TreeIsEmpty(Tree *ptree){    return (ptree->size==0);}

（3）向树中添加一个项目

因为二叉搜索树中不能含有项目相同的节点，所以这里假设树中没有与被添加项目相同的节点项目，并且假设树非满。添加一个项目的几个主要步骤如下：

step1:找到合适位置；

step2:设置一个新节点，将添加项目纳入该节点，并使该节点的两个指针成员为空;

step3:将该新节点放进合适位置，具体为：使合适位置的父节点与其链接

其中第2、3步都可以简单实现，关键是第1步，如何找到合适位置？

考虑二叉搜索树的特征：左<父<右。

那么，先判断x（设x为要添加的项目）在树根节点的左还是右边；

假设在左，如果刚好左为空，则找到了合适位置；如果左不为空，那就要继续判断：x再以该左节点为根节点的树的左还是右？依次类推进行下去。这里自然想到递归方法。

关键函数代码如下：

//Toleft和ToRight函数为判断左右函数//对ToLeft（），若左则true,若右则false;ToRight()类似void AddNode(Node *newnode,Node *root){   if(ToLeft(&(newnode->item),&(root->item))   {       if(root->left==NULL)         root->left=newnode;       else         AddNode(newnode,root->left);   }   if(ToRight(&(newnode->item),&(root->item))   {       if(root->right==NULL)         root->right=newnode;       else         AddNode(newnode,root->right);    }}

（4）查找项目：查找树中包含相同项目的节点；往往查找项目是为了后续操作服务（比如，删除），因此查找项目的函数须返回该项目的父节点，同时也需要返回包含该项目的节点，若没有找到，该返回项即为NULL。

要返回两个节点指针，一般函数只能返回某个数据类型的单个变量，这里自然又想到创建一个结构，匹配这两个要返回的数据：

typedef struct pair{   Node *parent;   //指向父节点   Node *child;    //指向找到的节点}Pair;

 用递归方法实现：

//未测试，以后检查Pair SeekItem(const Item *pi,const Tree *ptree){   Pair look;   Tree newtree;   newtree=*ptree;   if(*pi==newtree.root->item)   {      look.parent=NULL;      look.child=newtree.root;      return look;    }    else        if(ToLeft(pi,&(newtree.root->item)))       {            newtree.root=newtree.root->left;            SeekItem(pi,&newtree);        }       if(ToRight(pi,&(newtree.root->item)))       {            newtree.root=newtree.root->right;            SeekItem(pi,&newtree);        }        else        {             look.parent=NULL;             look.child=NULL;             return look;        } }

用while()方法实现：

Pair SeekItem(const Item *item,const Tree *ptree){    Pair look;    look.parent=NULL;    look.child=ptree->root;    while(look.child!=NULL)    {         if(ToLeft(item,&(look.child->item)))         {             look.parent=look.child;             look.child=look.child->left;             continue;          }         if(ToRight(item,&(look.child->item)))         {             look.parent=look.child;             look.child=look.child->right;             continue;          }          else             break;      }      return look;}

(4)删除项目：

第一种情况：被删除节点没有子节点，则将被删除节点的父节点的相应成员设为NULL。

第二种情况：被删除节点只有一个子节点，考虑二叉搜索树的特性，可以知道要做的只是把被删除节点的子树链接到父节点的相应成员。

第三种情况：被删除节点有两个子节点。分析二叉搜索树的特性：左、右子树任意节点必定都同时大于或小于被删节点的父节点，因此这两个子树都应被归并到父节点的同一边去；同时右子树任意节点都大于左子树任意节点，因此：

若被删节点位于父节点左边，说明左右子树均小于父节点，则将其左子节点链接到父节点左边，同时在左子节点为根节点的树的右边寻找空位去添加右子树，这个空位是左子树的右边中第一个空缺的右节点（因为这个位置相对于被删除节点的左子树是最大的位置）。

若被删节点位于父节点右边，说明左右子树均大于父节点，则将其右子节点链接到父节点右边，同时在右子节点为根节点的树的左边寻找空位去添加左子树，这个空位是右子树的左边中第一个空缺的右节点（因为这个位置相对于被删除节点的右子树是最小的位置）。

关键函数：

//删除结点函数，参数如何描述？//删除操作后被删除结点的父节点的“指向被删结点的指针成员”要重新赋值//所以要用指向“父节点指针成员”的指针去描述//而父节点指针成员本身是一个Node*指针型，所以参数类型为Node **//注意：这里的ptr是指向父节点指针成员（指向被删结点）的指针类型//*ptr描述的是父节点中指向被删结点的指针成员，也即被删结点的地址指针类型//**ptr则是描述被删除的结点类型static void DeleteNode(Node **ptr){  Node *temp;  puts((*ptr)->item.petname);//*ptr为被删结点父节点的指针成员，该成员指向被删结点，//(*ptr)->left即指向被删结点的左子节点//若其左子节点为空，将其右子节点链接到父节点原先指向被删结点的指针成员  if((*ptr)->left==NULL)     {    temp=*ptr;    *ptr=(*ptr)->right;    free(temp);  }//若其右子节点为空，将其左子节点链接到父节点原先指向被删结点的指针成员  else if((*ptr)->right==NULL)  {    temp=*ptr;    *ptr=(*ptr)->left;    free(temp);  }  else  //被删除结点有两个子结点  {    for(temp=(*ptr)->left;temp->right!=NULL;temp=temp->right)        continue;    temp->right=(*ptr)->right;    temp=*ptr;    *ptr=(*ptr)->left;    free(temp);  }}

 (5)遍历树

void InOrder(const Node *root,void(*pfun)(Item item)){   if(root!=NULL)   {      InOrder(root->left);      (*pfun)(root->item);      InOrder(root->right);    }}//pfun函数先处理左节点，再处理根节点，最后处理右节点

（6）清空树

void DeleteTree(Tree *ptree){   if(ptree!=NULL)         DeleteAllNodes(ptree->root);  ptree->root=NULL;  ptree->size=0;}static void DeleteAllNodes(Node *root){    Node *pright;    if(root!=NULL)    {       pright=root->right;       DeleteAllNodes(root->left);       free(root);       DeleteAllNodes(pright);     }}