image.png
int leafNum(CSTree T)
{
if (T == NULL)
return 0;
if (T->firstchild == NULL)
return leafNum(T->nextsibling) + 1;
else
return leafNum(T->firstchild) + leafNum(T->nextsibling);
}
参考答案：
image.png
image.png
我的错误之处是在于没有
int depth(CSTree T)
{
if (T == NULL)
return 0;
int dep = 0;
//应该是for(dep=depth(T->firstchild)+1;T->nextsibling!=NULL;T=T->nextsibling)
//因为在计算depth(T->firstchild)时候，T自身没有计算，因此需要加一，非常容易出错
for (dep = depth(T->firstchild); T->nextsibling != NULL; T = T->nextsibling)
if (dep < depth(T->nextsibling))
dep = depth(T->nextsibling);
return dep;
}
image.png
image.png
image.png
/*
se是层序序列，A[i]记录编号为i的结点的度，1<=i<=n
*/
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild, *nextsibling;
}CSNode,*CSTree;
CSTree createCSTree(ElemType se[], int A[])
{
int i=0;
CSTree p = (CSTree)malloc(sizeof(CSNode));
CSTree T = p;
p->nextsibling = NULL;//根节点的右子树为空
CSTree s;
Queue Q;
InitQueue(Q);
EnQueue(Q);
while (!IsEmpty(Q)) {
DeQueue(Q,p);
i++;
p.data = se[i]; //每当一个元素出队列的时候，给她赋值
if (A[i] > 0) { //如果有孩子结点
s = (CSNode*)malloc(sizeof(CSNode));
//这里少了一个入队的操作
EnQueue(Q, s);
p->firstchild = s; //连接孩子
A[i]--;
while (A[i]) { //如果有不止一个孩子结点
p = s;
s = (CSNode*)malloc(sizeof(CSNode));
s->firstchild = NULL;//一个结点的左子树初始值为空
p->nextsibling = s; //连接兄弟
}
s->nextsibling = NULL; //最后一个结点的兄弟指针为空
}
}
return T;
}
参考方法：
预备知识之如何使用new声明一个结构体？
image.png
image.png
image.png
#define maxNodes 15
void createCSTree_Degree(CSTree &T, DataType e[], int degree[], int n)
{
//e层序序列，degree结点的度，n结点的个数
CSNode *pointer = new CSNode[maxNodes];
int i, j, d, k=0;
for (int i = 0; i < n; i++) {
pointer[i] = new CSNode;
pointer[i].data = e[i];
pointer[i].firstchild = pointer[i].nextsibling = NULL;
}
for (int i = 0; i < n; i++) {
d = degree[i];
if (d) {
k++;
pointer[i]->firstchild = pointer[k];
for (j = 2; j <= d; j++) {
pointer[j - 1]->nextsibling = pointer[j];
}
}
}
T = pointer[0];
delete[]pointer;
}
