## 第17章 高级数据表示 17.7 二叉搜索树 （第三部分 完整包） 顶原

idreamo

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)
{
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：树非空*/
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
}
else if (ToRight(&new_node->item,&root->item))
{
if(root->right == NULL)
root->right = new_node;
else
}
else                                       /*不应含有相同的项目*/
{
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

程序 = 数据结构 + 算法 　　——图灵奖得主，计算机科学家N.Wirth(沃斯) 　　 　　作为程序员，我们做机器学习也好，做python开发也好，java开发也好。 　　有一种对所有程序员无一...

java进阶架构师
10/25
0
0

2017/12/18
0
0
LeetCode算法题-Convert Sorted Array to Binary Search Tree（Java实现）

11/09
0
0
《java数据结构和算法》读书笔记

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

2016/05/27
155
0

2017/11/08
0
0

EOS官方钱包keosd

EOS官方钱包的名称是keosd，它负责管理你的私钥，并且帮你进行交易的签名。 不过不幸的是，keosd钱包对普通用户并不友好，它是一个命令行程序，目前还没有像以太坊的mist那样的图形化界面，而...

10
0
ArrayList的实现原理以及实现线程安全

13
0
Netty 备录 (一)

_大侠__

22
0
Django简单介绍和用户访问流程

Python下有许多款不同的 Web 框架。Django是重量级选手中最有代表性的一位。许多成功的网站和APP都基于Django。 Django是一个开放源代码的Web应用框架，由Python写成。 Django遵守BSD版权，初...

26
0
Spring Cloud Stream消费失败后的处理策略（四）：重新入队（RabbitMQ）

14
0