...链表存储结构,根结点指针为T,请写出计算二叉树中度为2的结点数目的...

发布网友 发布时间：2024-10-23 23:43

我来回答

共2个回答

热心网友 时间：2024-11-09 17:14

采用深度或者广度遍历就可以，分别采用栈或者队列结构。对于访问到的每个节点，如果度为2，就是所求的。比如用栈的话
push(ST,root)
while(not empty(ST))
{
node=pop(ST)
if(node->left)
push(ST,node->left)
if(node->right)
push(ST,node->right)
}

上面的伪代码实际上就是图的深度遍历，二叉树算是一种特殊的图。
具体的写法可以搜索一下就可以找到。

热心网友 时间：2024-11-09 17:16

int Count(AGraph *T,int v,int visit[maxSize])
{
ArcNode *p;
int que [maxSize],front=0,rear=0;
int j;
int s=0;
Visit(v);
visit(v)=1;
rear=(rear+1）%maxSize
que[rear]=v；

while(front!=rear)
{
int k=0;
front=(front+1）%maxSize;
j=que[front];
p=T->adjlist[j].firstarc
while(p！=NULL)
{
k++;
if(visit [p->adjvexj==0）
{
Visit(p->adjvex);
visit[p->adjvex]=1;
rear=(rear+1)%maxSize;
que[rear]=p->adjvex;
}
p=p->nextarc;
}
}
if(k==2)
{
s++;
}
return s;
}