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;
}
如果删除的次数不多,通常会采用的策略是懒惰删除,当一个元素要被删除时,它仍然留在树中,只是被标记为无效。
阅读(621) | 评论(0) | 转发(0) |