第17章 高级数据表示 17.7 二叉搜索树(第二部分 二叉树分步实现)
博客专区 > idreamo 的博客 > 博客详情
第17章 高级数据表示 17.7 二叉搜索树(第二部分 二叉树分步实现)
idreamo 发表于3个月前
第17章 高级数据表示 17.7 二叉搜索树(第二部分 二叉树分步实现)
  • 发表于 3个月前
  • 阅读 8
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

下面的任务是实现tree.h中描绘的伟大的函数。InitializeTree()、EmptyTree()、FullTree()和TreeItems()函数比较简单,与列表和队列抽象数据类型中的同类函数差不多。我们重点讨论其余的函数。

一、添加项目

在向树中添加一个项目时,应该 首先检查树中是否还有空位 给新节点。然后,由于二叉搜索树被定义成不含有相同的项目,所以要检查树中是否已经有该项目。如果这个新项目通过了前面两步的检查,就可以 创建一个新的节点将项目复制到节点中并设置该节点的左右指针为NULL。这表示该节点无子节点。然后要更新Tree的Size成员,以记录添加了一个新的项目。接下来,要找出该把此节点放在树中的什么位置如果树为空,就要将根节点指针指向该新节点。否则,在树中查找到放置该新节点的位置。AddItem()函数按照这条思路实现,并将其中的一些工作交给尚未定义的函数:SeekItem()、MakeNode()和AddNode()。

bool AddItem(const Item * pi,Tree * ptree)
{
    Node * new_node;
    
    if(TreeIsFull(ptree))
    {
        fprintf(stderr,"Tree is full\n");
        return false;                       /*提前返回*/
    }
    if(SeekItem(pi,ptree).child != NULL)
    {
        fprintf(stderr,"Attempted to add duplicate item\n");
        return false;                       /*提前返回*/
    }
    new_node = MakeNode(pi);                /*指向新节点*/
    if(new_node == NULL)
    {
        fprintf(stderr,"Couldn't create node\n");
        return false;                       /*提前返回*/
    }
    /*成功创建了一个新节点*/
    ptree->size++;
    if(ptree->root == NULL)                 /*情况1:树为空树,新节点即为根节点*/
        ptree->root = new_node;
    else 
        AddNode(new_node,ptree->root);      /*情况2:树非空,把新节点添加到树中*/
    return true;
}

SeekItem()、MakeNode()和AddNode()函数并不是Tree类型公用接口的一部分。它们是隐藏在tree.c文件中的静态函数。它们处理实现的细节,例如节点、指针、和结构这些不属于公用接口的部分。

MakeNode()函数比较简单。它处理动态内存分配和节点的初始化。函数的参数是一个指向新项目的指针,函数的返回值是一个指向新节点的指针。回忆一下,malloc()在无法完成请求的分配时返回空指针,MakeNode()函数只在内存分配成功时初始化新节点。以下是MakeNode()的代码。

static Node * MakeNode(const Item * pi)
{
    Node * new_node;
    
    new_node = (Node *)malloc(sizeof(Node));
    if(new_node != NULL)
    {
        new_node->item = *pi;
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}

AddNode()函数在二叉搜索树包中是很难的函数(其难度仅次于另一个函数)。它要判断新节点去向何方并添加之。具体地,它要比较新项目和根项目来决定新项目要添加到左子树还是右子树。如果项目是一个数字可以用大于号">"或小于号"<"来比较。如果项目是一个字符串,可以用strcmp()来比较。但本例中的项目是包含两个字符串的结构,所以必须定义执行比较的函数。后面定义的ToLeft()函数当新项目应在左子树时返回True,而ToRight()函数当新项目应在右子树时返回True。这两个函数相当于">"和"<"。假设新项目要到左子树去,左子树可能是空的。在这种情况下,AddNode()函数只用把左子指针指向新节点。但如果左子树非空呢?则此函数就应比较新项目和左子节点的项目,以决定新项目应到此子节点的左子树还是右子树中去。

这个过程继续进行,直到函数到达一个空的子树,在那一节点添加新节点。递归是一种实现这种搜索的方法即,在子节点而非根节点应用AddNode()函数当左子树或右子树为空,即当root->left或root->right为NULL时函数的递归调用序列结束。切记root为指向当前子树顶部的指针,所以每次递归调用使它指向一个新的下一级子树(请参见第9章中关于递归的讨论)。

static void AddNode(Node * new_node,Node * root)
{
    if(ToLeft(&new_node->item,&root->item))
    {
        if(root->left == NULL)  /*空子树*/
            root->left = new_node;  /*因此把节点添加到此处*/
        else
            AddNode(new_node,root->left);  /*否则处理该子树*/
    }
    if(ToRight(&new_node->itm,&root->item))
    {
        if(root->right == NULL)
            root->right = new_node;
        else 
            AddNode(new_node,root->right);
    }
    else    /*不应含有相同的项目*/
    {
        fprint(stderr,"location error in AddNode()\n");
        exit(1);
    }
}

ToLeft()和ToRight()函数有赖于Item类型的特性。Nerfville宠物俱乐部的成员以名字的字母顺序排序。如果两个宠物重名,将其按种类排序。如果它们又是相同种类的,则这两个项目是相同的,这在基本的二叉搜索树中是不允许的。回忆一下标准C库函数strcmp()的用法:如果第一个参数表示的字符串在第二个参数之前则返回负数,如果两者相等则返回零,如果第一个字符串在第二个字符串之后则返回正数。ToRight()函数与之有相似的代码。用这两个函数进行比较,而不是直接在AddNode()中处理,会比较容易地适应新的需求。当需要不同形式的比较时,不必重写整个AddNode()函数,只须重写ToLeft()和ToRight()即可。

static bool ToLeft(const Item *i1,const Item *i2)
{
    int compl;
    if((compl = strcmp(i1->petname,i2->petname))<0)
        return true;
    else if (compl == 0  && strcmp(i1->petkind,i2->petkid))<0)
        return true;
    else 
        return false;
}

二、查找项目

有3个接口函数需要用到搜索树中特定项目的功能:AddItem()、InTree()和DeleteItem()。在实现中由SeekItem()函数提供这一服务。DeleteItem()函数还有另一个需求:需要知道被删除项目的父节点,以便子节点被删除时父节点指向该子节点的指针可以得到更新。因此,两个指针SeekItem()设计成返回包含的结构。其中一个指针指向包含该项目的节点(如果没找到项目就为NULL),另一个指向父节点(如果该节点为根节点,也即没有父节点,就为NULL)。这个结构类型定义如下:

typedef struct pair
{
    Node * parent;
    Node * child;
} pair;

SeekItem()函数可以通过递归的方法实现。但是为了向您介绍更多的编程技术,我们用while循环来控制树中从上到下的搜索。像AddNode()一样,SeekItem()使用ToLeft()和ToRight()在树中导航开始时SeekItem()设置look.child指针指向树的根节点,然后沿着目标项应在的路径重置look.child到后续的子树。同时,look.parent指向它的父节点如果未找到匹配的项目,look.child为NULL。如果匹配的项目在根节点,look.parent为NULL,因为根节点无父节点。以下是SeekItem()的代码:

static pair SeekItem(const Item * pi,const Tree * ptree)
{
    pair look;
    look.parent = NULL;
    look.child = ptree->root;
    
    if(look.child == NULL)
        return look;
    while(look.child != NULL)
    {
        if(ToLeft(pi,&(look.child->Item)))
        {
            look.parent = look.child;
            look.child = look.child->left;
        }
        else if (ToRight(pi,&(look.child->Item)))
        {
            look.parent = look.child;
            look.child = look.child->right;
        }
        else
            break;  /*如果前面两种情况都不满足,必定为相等的情况*/
                    /*look.child是目标项目节点的地址*/ 
    }
    return look;
}

注意,由于SeekItem()函数返回一个结构,所以它能和结构成员运算符一起使用。例如,AddItem()函数中使用了如下代码:

if(SeekItem(pi,ptree).child != NULL)

有了SeekItem()之后,编写InTree()仅用接口函数是很简单的:

bool InTree(const Item * pi,const Tree * ptree)
{
    return (SeekItem(pi,ptree).child == NULL)?false:true;
}

三、删除项目

删除一个项目是最困难的任务,因为要将剩下的子树重新连接起来,以形成一个合法的树。在尝试编程完成这个任务之前,我们最好考虑清楚需要做什么。

最简单的一种情况是要删除的节点没有子节点,这种节点被称为叶节点(leaf)。在这种情况下我们要做的就是将父节点的相应指针置为NULL,并用free()函数释放被删除节点占用的内存

接下来,要删除一个有子节点的节点就有些复杂了。删除该节点使其子节点树与树的其他部分分离了。为了修复这种情况,需要把子节点子树的地址存储在先前被删除的地址在父节点占据的位置中

最后,要删除有两个子树的节点。其中一个子树,例如左子树,可依附在被删除节点先前依附的位置。但剩下的子树要去哪里呢?紧记树的基本设计:每一个在左子树中的项目都是父节点项目的前序项,而每一个右子树中的项目都是父节点项目的后序项这意味着,所有右子树中的项目都是所有左子树项目的后序项。而且,因为右子树曾经是以被删除项目为根的子树的一部分,所以所有右子树中的项目都是被删除节点的父节点的前序项。想象一下,如何在树中自上而下寻找右子树的头应在的位置。它应在父节点的前面,所以要沿父节点的左支向下找。但是它又在左子树所有项目的后面,这样就要查找左子树的右支是否有新节点的空位。如果没有就要沿着左子树的右支向下找直到找到一个空位。

1、删除节点

现在可以设计需要的函数了。可以将工作分成两个任务:第一个任务是将一个特定的项目与待删除的节点联系起来第二个任务是实际删除此节点。有一点需要注意的是,在所有的情况下都必须修改父节点的指针,这导致两个重要的结论:

    *程序要能表示待删除节点的父节点;

    *要修改指针,代码必须将该指针的地址传递给执行删除任务的函数

稍后我们会回到第一点上来讨论。同时,要修改的指针本身是Node*类型的,也即指向Node的指针类型因为函数参数是指针的地址,所以参数是Node**类型的即指向Node的指针的指针。假设您有可用的合适地址,可以将删除函数写成如下形式:

static void DeleteNode(Node **ptr)
/*ptr是指向目标节点的父节点指针成员的地址*/
{
    Node * temp;
    /*temp用来跟踪被删除节点的地址*/
    puts((*ptr)->item.petname);
    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指针向下查找左子树的右半边以找到一个空位*/
        for(temp = (*ptr)->left;temp->right != NULL; temp = temp->right)
            continue;  
        /*当找到一个空位时,把右子树依附在那儿*/
        temp->right = (*ptr)->right;
        /*再用temp保存被删除节点的地址*/
        temp = *ptr;
        /*接下来将左子树依附在父节点上*/
        *ptr = (*ptr)->left;
        /*释放temp指向的节点的内存*/
        free(temp);
    }
}

这个函数明确处理三种情况:无左子节点的节点、无右子节点的节点和有两个子节点的节点无子节点的节点可以作为无左子节点的特例。因为如果该节点无左子节点,程序就将右子节点的地址赋给父指针;但如果此时该节点也无右子节点,则其指针就为NULL,这恰好是无子节点的情况。

注意到代码用了一个临时指针来 跟踪被删除节点的地址。因为当父指针(*ptr)被重置后,程序会丢失将要删除节点的地址,但free()函数还需要此信息。所以程序将*ptr的初值存储在temp中然后用temp来释放被删除节点占用的内存。

处理有两个子节点情况的代码 首先在一个for循环中用temp指针向下查找左子树的右半边以找到一个空位当找到一个空位的时候,将右子树依附在那儿然后再用temp保存被删除节点的地址。接下来将左子树依附在父节点上,然后释放temp指向的节点的内存。

注意,因为ptr是Node**类型的,所以*ptr是Node*类型的,即和temp的类型相同。

2、删除项目

剩下的问题就是将一个特定的节点与一个特定的项目联系起来。这可以用SeekItem()函数来完成。回忆一下,它返回一个结构,此结构包含一个指向父节点的指针和一个指向包含项目的节点的指针。这样就可以通过使用父节点指针获取相应地址传递给DeleteNode()函数。DeleteItem()函数遵循这一思路,如下所示:

bool DeleteItem(const Item * pi,Tree * ptree)
{
    Pair look;
    look = SeekItem(pi,ptree);
    if(look.child == NULL)
        return false;
    
    if(look.parent == NULL)  /*删除根项目*/
        DeleteNode(&ptree->root);
    else if(look.parent->left == look.child)
        DeleteNode(&look.parent->left);
    else 
        DeleteNode(&look.parent->right);
    ptree->size--;
    return true;
}

首先把SeekItem()函数的返回值赋给look结构变量。如果look.child等于NULL,表明本次查找失败,DeleteItem()函数退出,并返回false。如果找到Item,函数处理三种情况。首先,look.parent的值为NULL意味着该项目在根节点中在这种情况下,不需要更新父节点,而是需要更新Tree结构中的根指针因此,函数将该指针的地址传递给DeleteNode()函数。否则,程序判断待删除节点是其父节点的左子节点还是右子节点,然后传递适当指针的地址。

注意公用接口函数DeleteItem()中处理的是面向最终用户的对象(项目和树),而隐藏的DeleteNode()函数则完成与指针相关的实质性任务。

四、遍历树

遍历树要比遍历链表复杂,因为每个节点有两个分支 。这种分支特性,使得分而制之的的递归方法成为处理此问题的自然选择。在每个节点上,函数要做下列工作:

1、处理节点中的项目;

2、处理左子树(递归调用);

3、处理右子树(递归调用);

可以将此过程分给两个函数来完成:Traverse()和InOrder()。注意InOder()函数先处理左子树,然后处理项目,最后处理右子树。这种遍历树的顺序是按字母排序的结果。如果您有时间,可以试试用不同的顺序,比如项目-左子树-右子树和左子树-右子树-项目看会发生什么。

void Traverse(const Tree * ptree,void (*pfun)(Item item))
{
    if(ptree != NULL)
        InOrder(ptree->root,pfun);
}

static InOrder(const Node * root,void (*pfun)(Item item))
{
    if(root != NULL)
    {
        InOrder(root->left,pfun);
        (*pfun)(root->item);
        InOrder(root->right,pfun);
    }
}

五、清空树

清空树与遍历树基本上是一个过程,即代码需要访问每个节点并用free()函数释放之。还需要重置tree结构的成员以说明是空树。DeleteAll()函数负责处理Tree结构,并将释放内存的任务分配给DeleteAllNodes()。后者和InOrder()函数构造相同。它保存了指针值root->right,以使它在根节点被释放后仍然可用。下面是两个函数的代码:

void DeleteAll(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);
    }
}

 

共有 人打赏支持
粉丝 13
博文 139
码字总数 224743
×
idreamo
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: