首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

在清华大学出版的C++数据结构这本书中,关于树那一章节的删除子树的这个函数体是否存在着这样的一个严重有关问题呢

2012-03-31 
在清华大学出版的C++数据结构这本书中,关于树那一章节的删除子树的这个函数体是否存在着这样的一个严重问

在清华大学出版的C++数据结构这本书中,关于树那一章节的删除子树的这个函数体是否存在着这样的一个严重问题呢?
在199页,有这样的的一个函数体:

template<class type> void Tree<type>::RemovesubTree(TreeNode<type>*p){
  //私有函数:删除以P为根结点的子树
  TreeNode<type>*q=p->firstChild, *next;
  while(q!=NULL){
  next=q->nextSibiling;
  RemovesubTree(q);q=next;
  }
  delete p;
}



我的观点是,很明显,这个函数在删除了所有P与P的子树和兄弟节点后并没有把指向P的指针改为NULL,将使得树在进行类似于遍历的操作时对一个不存在的节点(通过指针)进行危险的操作。
事实上我还有一种不成熟的意见,或者说是偏见,我认为树是一种很尴尬的数据结构,因为当树里面的节点数目到达一定数量级时(比如2000或3000,在实际问题求解中几乎可以轻易地到达这个数量),对其的任何操作在时间代价上都是无法接受的。

[解决办法]
不是的 树首先要带有sort功能
然后插入 删除操作将会具有log2(n)的复杂度
在大数据的时候大大缩短运行时间

热点排行