文档章节

第17章 高级数据表示 17.7 二叉搜索树 (第三部分 完整包)

idreamo
 idreamo
发布于 2017/09/09 07:04
字数 825
阅读 8
收藏 0
点赞 0
评论 0

下面给出完整的tree.c代码。tree.h和tree.c共同组成树程序包。

tree.c实现文件

/*tree.c --树类型的支持函数*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "tree.h"

/*局部数据类型*/
typedef struct pair{
     Node * parent;
     Node * child;
 }pair;

 /*局部函数的原型*/
 static Node * MakeNode(const Item * pi);
 static bool ToLeft(const Item *i1,const Item *i2);
 static bool ToRight(const Item *i1,const Item *i2);
 static void AddNode(Node *new_node,Node * root);
 static void InOrder(const Node *root,void (*pfun)(Item item));
 static Pair SeekItem(const Item *pi,const Tree *ptree);
 static void DeleteNode(Node **ptr);
 static void DeleteAllNodes(Node *ptr);
/*函数定义*/
void InitializeTree(Tree * ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

bool TreeIsEmpty(const Tree * ptree)
{
    if(ptree->root == NULL)
        return true;
    else
        return false;
}

bool TreeIsFull(const Tree * ptree)
{
    if(ptree->size == MAXITEMS)
        return true;
    else
        return false;
}

int TreeItemCount(const Tree * ptree)
{
    return ptree->size;
}

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(now_node == NULL)
    {
        fprintf(stderr,"Couldn't create node\n");
        return false;                   /*提前返回*/
    }
    /*成功创建了一个新节点*/
    ptree->size++;

    if(ptree->root == NULL)              /*情况1:树为空树*/
        ptree->root = new_node;          /*新节点即为树的根节点*/
    else                                 /*情况2:树非空*/
        AddNode(new_node,ptree->root);   /*把新节点添加到树中*/
    return true;
}

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

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

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

void DeleteAll(Tree * ptree)
{
    if(ptree != NULL)
        DeleteAllNodes(ptree->root);
    ptree->root = NULL;
    ptree->size = 0;
}

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

static void DeleteAllNodes(Node * root)
{
    Node * pright;

    if(root != NULL)
    {
        pright = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}

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);     /*否则处理该子树*/
    }
    else if (ToRight(&new_node->item,&root->item))
    {
        if(root->right == NULL)
            root->right = new_node;
        else
            AddNode(new_node,root->right);
    }
    else                                       /*不应含有相同的项目*/
    {
        fprintf(stderr,"location error in AddNode()\n");
        exit(1);
    }
}

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->petkind)<0)
        return true;
    else
        return false;
}

static bool ToRight(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->petkind)>0)
        return true;
    else
        return false;
}

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

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.right;
        }
        else
            break;    /*如果前面两个都不满足,必定为相等的情况,look.child是目标项目节点的地址*/
    }
    return look;      /*成功返回*/
}

static void DeleteNode(Node ** ptr)
/*ptr是指向目标节点的父节点指针成员的地址*/
{
    Node * 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 = (*ptr)->left;temp->right != NULL;
            temp = temp->right)
            continue;
            temp->right = (*ptr)->right;
            temp = *ptr;
            *ptr = (*ptr)->left;
            free(temp);
    }
}

 

© 著作权归作者所有

共有 人打赏支持
idreamo
粉丝 12
博文 139
码字总数 224743
作品 0
青岛
产品经理
算法知识梳理(10) - 二叉查找树

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛 ⋅ 2017/12/18 ⋅ 0

《java数据结构和算法》读书笔记

《Java多线程编程核心技术》读书笔记 常用数据结构 第2章 数组 最简单的数据结构,在查找上比链表有优势,但是在插入与删除上比不上链表。 Java中的数组有长度限制,为int值。在内存模型中,...

刀狂剑痴 ⋅ 2016/05/27 ⋅ 0

无处不在的算法---《算法神探》读后感

最近,我参加了CSDN举办的“从高考到程序员”征文活动,获赠了一本图书。在众多图书中,我选了《算法神探》,觉得这本书从名字上来看就比较有意思。拿到书之后,我分两次就把它读完了,可以毫...

zhouzxi ⋅ 2017/07/22 ⋅ 0

算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴 ⋅ 2017/11/08 ⋅ 0

Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛 ⋅ 2017/11/10 ⋅ 0

微软面试、经典算法、编程艺术、红黑树4大系列总结

无私分享,造福天下 以下是本blog内的微软面试100题系列,经典算法研究系列,程序员编程艺术系列,红黑树系列4大经典原创系列作品与一些重要文章的集锦。 一、微软面试100题系列 横空出世,席...

长平狐 ⋅ 2013/01/06 ⋅ 0

算法导论复习:第十二章

二叉搜索树的实现: 备注:算法导论中文版第168页中删除节点时候,y=TREEMINIMUM(z.right)是错误的,应该寻找后继结点,为y=TREESUCCESSOR(z.right). #include <stdio.h> include <stdlib.h> inc......

fzyz_sb ⋅ 2014/01/05 ⋅ 0

二叉树,排序二叉树

说到二叉树,这可是数据结构里面的非常重要的一种数据结构,二叉树是树的一种,本身具有递归性质,所以基于二叉树的一些算法很容易用递归算法去实现。作为一种非线性结构,比起线性结构还是相...

长平狐 ⋅ 2013/12/25 ⋅ 0

当我们在聊TreeMap(一)——红黑树详解Java代码实现

本文出自:https://blog.csdn.net/DT235201314/article/details/80661157 一丶概述 上一篇讲HashMap,避开了红黑树,这边讲TreeMap,好好说一下红黑树。 二丶概述目录图 三丶聊聊TreeMap 数据...

天一方蓝 ⋅ 06/13 ⋅ 0

数据结构-二叉搜索树的实现

定义 二叉搜索树(Binary Search Tree,BST),也称为二叉排序树或二叉查找树。 相较于普通的二叉树,非空的二叉搜索树有如下性质: 非空左子树的所有键值小于其根结点的键值; 非空右子树的所有...

IAM四十二 ⋅ 2017/10/27 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

linux 安装docker

通过以下命令下载安装docker wget -qO- https://get.docker.com | sh 执行以上命令后输出以下内容说明安装成功,注意红框中的内容,docker安装成功后默认只有root能使用,红框中给出的提示是...

haoyuehong ⋅ 3分钟前 ⋅ 0

482. License Key Formatting - LeetCode

Question 482. License Key Formatting Solution 思路:字符串转化为char数组,从后遍历,如果是大写字母就转化为小写字母,如果是-就忽略,如果遍历了k个字符(排除-)就追加一个-。 Java实现...

yysue ⋅ 22分钟前 ⋅ 0

聊聊spring cloud gateway的LoadBalancerClientFilter

序 本文主要研究一下spring cloud gateway的LoadBalancerClientFilter GatewayLoadBalancerClientAutoConfiguration spring-cloud-gateway-core-2.0.0.RELEASE-sources.jar!/org/springfram......

go4it ⋅ 46分钟前 ⋅ 0

详解:Nginx反代实现Kibana登录认证功能

Kibana 5.5 版后,已不支持认证功能,也就是说,直接打开页面就能管理,想想都不安全,不过官方提供了 X-Pack 认证,但有时间限制。毕竟X-Pack是商业版。 下面我将操作如何使用Nginx反向代理...

问题终结者 ⋅ 53分钟前 ⋅ 0

002、nginx配置虚拟主机

一、nginx配置虚拟主机可分为三种方式,分别为: 1、基于域名的虚拟主机,通过域名来区分虚拟主机——应用:外部网站 2、基于端口的虚拟主机,通过端口来区分虚拟主机——应用:公司内部网站...

北岩 ⋅ 56分钟前 ⋅ 0

shell脚本之死循环写法

最近在学习写shell脚本,在练习if while等流程控制时,突然它们的死循环写法是怎么样的?经过百度与亲测记录如下: for死循环 #! /bin/bashfor ((;;));do date sleep 1d...

hensemlee ⋅ 58分钟前 ⋅ 0

苹果的ARKit2.0有多可怕,看了就知道

序言 ARKit主要由三部分组成: 跟踪(Tracking) 跟踪是ARKit的核心组件之一,其提供了设备在物理世界中的位置与方向信息,并对物体进行跟踪,如人脸。 2.场景理解(Scene Understanding) 场...

_小迷糊 ⋅ 59分钟前 ⋅ 0

5.1 vim介绍 5.2 vim移动光标 5.3 ,5.4vim一般模式下移动光标,复制粘贴

vim命令 vim是vi的一个升级版;vim可以显示文字的颜色 安装vim这一个包vim-enhanced 如果不知道安装包,可以使用 命令下面命令来查看vim命令是那个包安装的。 [root@linux-128 ~]# yum prov...

Linux_老吴 ⋅ 今天 ⋅ 0

vim一般模式

vim 是什么 vim是什么 ? 在之前接触Linux,编辑网卡配置文件的时候我们用过了vi ,vim简单说就是vi的升级版,它跟vi一样是Linux系统中的一个文本编辑工具。 如果系统中没有vim ,需要安装一...

李超小牛子 ⋅ 今天 ⋅ 0

docker实战

构建企业级Docker虚拟化平台实战 重点剖析虚拟化和云计算概念; 分析Docker虚拟化的概念和原理; 从0开始实战Docker虚拟化平台; 基于Docker构建Nginx WEB服务器和CentOS虚拟机; 基于开源监...

寰宇01 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部