## 第17章 高级数据表示 17.7 二叉搜索树(第二部分 二叉树分步实现) 顶原

idreamo

``````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(new_node == NULL)
{
fprintf(stderr,"Couldn't create node\n");
return false;                       /*提前返回*/
}
/*成功创建了一个新节点*/
ptree->size++;
if(ptree->root == NULL)                 /*情况1：树为空树，新节点即为根节点*/
ptree->root = new_node;
else
return true;
}``````

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

``````static void AddNode(Node * new_node,Node * root)
{
if(ToLeft(&new_node->item,&root->item))
{
if(root->left == NULL)  /*空子树*/
root->left = new_node;  /*因此把节点添加到此处*/
else
}
if(ToRight(&new_node->itm,&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->petkid))<0)
return true;
else
return false;
}``````

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

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

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

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

1、删除节点

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

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

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

2、删除项目

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

1、处理节点中的项目；

2、处理左子树（递归调用）；

3、处理右子树（递归调用）；

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

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

### idreamo

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

java进阶架构师
2018/10/25
0
0

2017/12/18
0
0

2018/10/30
0
0
LeetCode算法题-Convert Sorted Array to Binary Search Tree（Java实现）

2018/11/09
0
0

2017/12/19
0
2

import javax.servlet.ServletException;import javax.servlet.annotation.WebServlet;import javax.servlet.http.Cookie;import javax.servlet.http.HttpServlet;import javax.serv......

gwl_

1
0

stars永恒

1
0

NotFound403

3
0
day22:

1、写一个getinterface.sh 脚本可以接受选项[i，I]，完成下面任务： 1）使用格式：getinterface.sh [-i interface | -I ip] 2）当用户使用-i选项时，显示指定网卡的IP地址；当用户使用-I选项...

2
0
Spring Cloud Alibaba基础教程：使用Nacos实现服务注册与发现

4
0