1.相对链表的O(N)的平均访问时间，树的为O(lgN)
2.一棵树是N个节点和N-1条变的集合
3.一般树的实现
struct treenode
{
elementtype element；
ptrtonode firstchild；//纵向链表，指向该节点的第一个儿子
ptrtonode nextsibling；//横向链表，指向儿子链表的下一个元素（下一兄弟）
}
4.二叉树
二叉树是一棵树，每个节点有不多于两个的儿子。平均深度为O(sqrt（N）)
实现：
struct treenode
{
elementtype element；
tree left；
tree right；
}
5.二叉查找树
对于二叉查找树中的每一个节点X,其左子树中所有关键字的值都小于X,右子树则大于X。二叉查找树的平均深度为O(lgN)。
1）清空
makeempty（searchtree T）
{
if（T!=null）
{
makeempty（T->left）；
makeempty（T->right）；
free(T);
}
return null;
}
2）查找
find（elementtype X,tree T）
{
if（T==NULL）
return null；
if（Xelement）
find（X,T->left）；
else if（X>T->element）
find（X,T->left）；
else
return T;
}
在所有的实现中都要注意“边界情况”的处理，如对空树的判断和处理。
insert（elementtype X,tree T）
{
if（T==NULL）
{
T=maloc（sizeof（treenode））；
if（T==NULL）
FATALERROR("out of space");
else
{
T->element=X;
T->left=T->right=null；
}
}
else
if（Xleft）
T->left=insert（X,T->left）；
else
if（X>T->right）
T->right=insert（X,T->right）；
return T;
}
3）删除
delete(elementtype X,T)
{
if(T==NULL)
ERROR("EMPTY TREE");
else
if(Xelement)
delete(X,T->left);
else
if(X>T->element)
delete(X,T->right);
else
if(T->right&&T->left)
{
tmpnode=findsmall(T->right);
T->element=tmpnode->element;
T->right=delete(tmpnode->element,T->right);
}
else
{
tmpt=T;
if(T->left==NULL)
T=T->right;
else
if(T->right==NULL)
T=T->left;
free(tmpt);
}
}
return T;
}
如果删除的次数不多，通常会采用的策略是懒惰删除，当一个元素要被删除时，它仍然留在树中，只是被标记为无效。
阅读(613) | 评论(0) | 转发(0) |
