如何得到一般树（c++链表描述）的结点个数？
我的Tree定义如下：
template<class T>class Tree;
template<class T>class TreeNode{
friend class Tree<T>;
private:
T data;
TreeNode<T>* firstChild,*nextSibling;
public:
TreeNode(T value,TreeNode<T> *fc=NULL,TreeNode<T> *ns=NULL):
data(value),firstChild(fc),nextSibling(ns){}
T GetData(){return data;}
};
template<class T> class Tree{
public:
Tree():root(NULL),current(NULL){}
void BuildRoot(T rootVal);
int Root();
long Size( TreeNode<T>* &t);
TreeNode<T>* GetRoot(){return root;}
TreeNode<T>* GetCurrent(){return current;}
int FirstChild();
int NextSibling();
void InsertChild(T value);
void RemovesubTree();
int RemoveChild(int i);
int Parent();
int Find(T target);
TreeNode<T>* Build(int A[],int n,int i);
void Build(int A[],int n,int i,TreeNode<T>* &ptr);
void Search(T &statr,T &purpose,TreeNode<T>* &ptr);
virtual int IsEmpty(){return root==NULL?1:0;}
void visit();
void PreOrder();
void PostOrder();
void LevelOrder(int DefaultSize);
private:
TreeNode<T> *root,*current;
void PreOrder(ostream&out,TreeNode<T>*p);
int Find(TreeNode<T>*p,T target);
void RemovesubTree(TreeNode<T>* p);
int FindParent(TreeNode<T>*t,TreeNode<T>*p);
};
我写了一个Size函数：
可是我用每个结点有四个孩子的“完全四叉树”验证，但结果不对：
比如：
实际结点为 10个，但Size 为3个，
实际结点为 10个，但Size 为3个，
我百思不得其解：
template <class T>long Tree<T>::Size( TreeNode<T>* &t)
{
if(t==NULL)return 0;
else{
TreeNode<T>*q,*q1;
q=q1=t->firstChild;
int k=0,count=0;
while(q!=NULL){q=q->nextSibling;k++;}
if(q1!=NULL)
count=1+Size(q1);
for(int i=2;i<=k;i++){
count+=Size(q1->nextSibling);
q1=q1->nextSibling;
}
return count;
}
}
哪位大哥帮帮小弟？我出50分。
问题点数：50、回复次数：7Top
1 楼liulin（liulin）回复于 2002-05-18 15:18:47 得分 5
厉遍呗Top
2 楼bluegirl2003（小笨笨猫）回复于 2002-05-18 19:10:14 得分 0
how?Top
3 楼thinice（cursor）回复于 2002-05-18 19:56:09 得分 0
用递归，结点个数等于左右结点个数和再加1Top
4 楼alonejilin（）回复于 2002-05-20 13:57:09 得分 0
这是一般树，每个结点不止是左右两个结点。Top
5 楼bjay（ben）回复于 2002-05-20 14:58:13 得分 45
广度优先遍历，（描述性算法，要用改造一下。）
其中用到的栈，自己构造一下吧。
int i_count=0;
counting(TreeNode<T> *T_cur)
{
TreeNode<T> *T_temp;
if (T_cur==null) then return();
i_count ++;
push(firstchild());
while ((T_temp =nextchild()) !=NULL)
push (T_temp);
T_temp =pop();
counting(T_temp);
}
main()
{
TreeNode<T> *T_temp;
T_temp =GetRoot();
counting (T_temp);
}Top
6 楼goodsong（风卷残云~不要把简单的事搞得N复杂）回复于 2002-05-20 19:02:27 得分 0
gzTop
7 楼sylmoon（专注Oracle）回复于 2002-05-21 20:34:49 得分 0
gzTop
