第4章第1节练习题3 二叉树特殊节点个数统计

时间：2023-02-22 22:11:43

为了方便说明二叉树的递归传值过程，这里首先给出一个基本的二叉树结构。

第4章第1节练习题3 二叉树特殊节点个数统计

图中值为NULL的节点实际是不存在的，故与父亲节点之间的连接用灰色的虚线表示。只是为了便于说明，才假设了一个NULL的空节点。
以下图中，黄色的线表明了传值的方向；绿色的数值表明了子节点传到父亲节点时的值，即根据递归公式计算便可。

一.统计二叉树中度为0的节点个数（递归/非递归）

递归方式实现

二叉树中，度为0则表明该节点的左孩子、右孩子均为空，根据二叉树的特性，最容易想到的便是采用递归方式实现该答案。首先列出基本递归公式：

f(T)=⎧⎩⎨0,f(T−>lchild)+f(T−>rchild)+1,f(T−>lchild)+f(T−>rchild),若T=NULL若T为叶子节点其他情况，若T为单分支节点，或双分支节点

然后可以参考下图

第4章第1节练习题3 二叉树特殊节点个数统计

当指针遍历到叶子节点的子节点（NULL节点）时，向父节点返回一个0，又因为该节点是本次遍历需要统计的节点，然后再向父节点返回的时候+1，这样便完成了一次简单的统计，然后再由父节点的父节点对其“汇总”一次，不断的向上递归传值，便完成了叶子节点的统计。

算法描述如下

int CntLfNode_recursive(BiTNode* T){
if(T==NULL){
return 0;
    }
if(T->lchild==NULL&&T->rchild==NULL){
return CntLfNode_recursive(T->lchild)+CntLfNode_recursive(T->rchild)+1;
    }else{
return CntLfNode_recursive(T->lchild)+CntLfNode_recursive(T->rchild);
    }
}

非递归方式实现

非递归方式的实现就比较容易理解了，只需要使用第4章第3节 二叉树的基本操作（非递归实现）中给到的遍历二叉树的方法，在访问节点时，判断下该节点的度是否为0：如果是0，则对其计数；如果不是，跳过便可。

这里便主体使用层次遍历方式实现，后对叶子节点进行计数，返回该数目。

int CntLfNode_norecursive(BiTNode* T){
    BiTNode* p=T;
    SqQueue Q;

    InitQueue(&Q);
    EnQueue(&Q,p);

int cnt=0;
while(IsEmptyQueue(&Q)!=0){
        p=DeQueue(&Q);
if(p->lchild==NULL&&p->rchild==NULL){
            cnt++;
        }
if(p->lchild!=NULL){
            EnQueue(&Q,p->lchild);
        }
if(p->rchild!=NULL){
            EnQueue(&Q,p->rchild);
        }
    }
return cnt;
}

二.统计二叉树中度为1的节点个数（递归/非递归）

递归方式实现

统计度为1的节点的递归实现方式与统计度为0的类似，首先列出基本递归公式：

f(T)=⎧⎩⎨0,f(T−>lchild)+f(T−>rchild)+1,f(T−>lchild)+f(T−>rchild),若T=NULL或T为叶子节点若T为单分支节点其他情况，若T为双分支节点

然后可以参考下图

第4章第1节练习题3 二叉树特殊节点个数统计

统计度为1的节点的传值过程与度为0的节点的传值过程类似，只是本次统计的是单分支节点而已，然后对此节点向父节点的传值的时候+1便可。

算法描述如下

int CntDONode_recursive(BiTNode* T){
if(T==NULL||(T->lchild==NULL&&T->rchild==NULL)){
return 0;
    }else if((T->lchild!=NULL&&T->rchild==NULL)||(T->lchild==NULL&&T->rchild!=NULL)){
return CntDONode_recursive(T->lchild)+CntDONode_recursive(T->rchild)+1;
    }else{
return CntDONode_recursive(T->lchild)+CntDONode_recursive(T->rchild);
    }
}

非递归方式实现

非递归方式的实现方式与统计度为0的节点方式类似，在访问节点时，判断下该节点的度是否为1：如果是1，则对其计数；如果不是，跳过便可。

这里同样主体使用层次遍历方式实现，后对单分支节点进行计数，返回该数目。

int CntDONode_norecursive(BiTNode* T){
    BiTNode* p=T;
    SqQueue Q;

    InitQueue(&Q);
    EnQueue(&Q,p);

int cnt=0;
while(IsEmptyQueue(&Q)!=0){
        p=DeQueue(&Q);
if((p->lchild!=NULL&&p->rchild==NULL)||(p->lchild==NULL&&p->rchild!=NULL)){
            cnt++;
        }
if(p->lchild!=NULL){
            EnQueue(&Q,p->lchild);
        }
if(p->rchild!=NULL){
            EnQueue(&Q,p->rchild);
        }
    }
return cnt;
}

三.统计二叉树中度为2的节点个数（递归/非递归）

递归方式实现

统计度为2的节点的递归实现方式与统计度为1或度为0的方式类似，首先列出基本递归公式：

f(T)=⎧⎩⎨0,f(T−>lchild)+f(T−>rchild)+1,f(T−>lchild)+f(T−>rchild),若T=NULL若T为双分支节点其他情况，若T为单分支节点，或叶子节点

然后可以参考下图

第4章第1节练习题3 二叉树特殊节点个数统计

与统计度为0和度为1的传值过程类似，只是需要统计的是双分支节点而已，在传值的时候，需要对双分支节点特殊处理，其他一样。

算法描述如下

int CntDTNode_recursive(BiTNode* T){
if(T==NULL){
return 0;
    }
if(T->lchild!=NULL&&T->rchild!=NULL){
return CntDTNode_recursive(T->lchild)+CntDTNode_recursive(T->rchild)+1;
    }else{
return CntDTNode_recursive(T->lchild)+CntDTNode_recursive(T->rchild);
    }
}

非递归方式实现

与度为0和度为1的节点统计方式类似，在访问节点时，判断下该节点的度是否为2：如果是2，则对其计数；如果不是，跳过便可。

同样主体使用层次遍历方式实现，后对双分支节点进行计数，返回该数目。

int CntDTNode_norecursive(BiTNode* T){
    BiTNode* p=T;
    SqQueue Q;

    InitQueue(&Q);
    EnQueue(&Q,p);

int cnt=0;
while(IsEmptyQueue(&Q)!=0){
        p=DeQueue(&Q);
if(p->lchild!=NULL&&p->rchild!=NULL){
            cnt++;
        }
if(p->lchild!=NULL){
            EnQueue(&Q,p->lchild);
        }
if(p->rchild!=NULL){
            EnQueue(&Q,p->rchild);
        }
    }
return cnt;
}

具体代码见附件。

附件

//AB#DG###CE##F##
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 10
typedef char ElemType;
typedef struct BiTNode{
    ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct{
    BiTNode* data[MaxSize];
int front, rear;
}SqQueue;

BiTNode* CreateBiTree(BiTNode*);

void InitQueue(SqQueue*);
void EnQueue(SqQueue*,BiTNode*);
BiTNode* DeQueue(SqQueue*);
int IsEmptyQueue(SqQueue*);

void PreOrder(BiTNode*);
void InOrder(BiTNode*);


int CntLfNode_recursive(BiTNode*);
int CntLfNode_norecursive(BiTNode*);
int CntDONode_recursive(BiTNode*);
int CntDONode_norecursive(BiTNode*);
int CntDTNode_recursive(BiTNode*);
int CntDTNode_norecursive(BiTNode*);

int main(int argc, char* argv[]){
    BiTNode* T=(BiTNode*)malloc(sizeof(BiTNode));
    T=CreateBiTree(T);

    PreOrder(T);printf("\n");
    InOrder(T);printf("\n");

int count_lf;
    count_lf=CntLfNode_recursive(T);
printf("recursive:The count of leaf node is %d\n",count_lf);
    count_lf=CntLfNode_norecursive(T);
printf("non-recursive:The count of leaf node is %d\n",count_lf);

int count_do;
    count_do=CntDONode_recursive(T);
printf("recursive:The count of node of degree one is %d\n",count_do);
    count_do=CntDONode_norecursive(T);
printf("non-recursive:The count of degree one node is %d\n",count_do);

int count_dt;
    count_dt=CntDTNode_recursive(T);
printf("recursive:The count of degree two node is %d\n",count_dt);
    count_dt=CntDTNode_norecursive(T);
printf("non-recursive:The count of degree two node is %d\n",count_dt);

return 0;
}

//-------------------------------------------------------------------------------------

BiTNode* CreateBiTree(BiTNode* T){
    ElemType ch;
scanf("%c",&ch);
if(ch=='#'){
return NULL;
    }
    T=(BiTNode*)malloc(sizeof(BiTNode));
    T->data=ch;
    T->lchild=CreateBiTree(T->lchild);
    T->rchild=CreateBiTree(T->rchild);
return T;
}

//-------------------------------------------------------------------------------------

//统计二叉树中度为0的节点个数（递归）
int CntLfNode_recursive(BiTNode* T){
if(T==NULL){
return 0;
    }
if(T->lchild==NULL&&T->rchild==NULL){
return CntLfNode_recursive(T->lchild)+CntLfNode_recursive(T->rchild)+1;
    }else{
return CntLfNode_recursive(T->lchild)+CntLfNode_recursive(T->rchild);
    }
}

//统计二叉树中度为0的节点个数（非递归）
int CntLfNode_norecursive(BiTNode* T){
    BiTNode* p=T;
    SqQueue Q;

    InitQueue(&Q);
    EnQueue(&Q,p);

int cnt=0;
while(IsEmptyQueue(&Q)!=0){
        p=DeQueue(&Q);
if(p->lchild==NULL&&p->rchild==NULL){
            cnt++;
        }
if(p->lchild!=NULL){
            EnQueue(&Q,p->lchild);
        }
if(p->rchild!=NULL){
            EnQueue(&Q,p->rchild);
        }
    }
return cnt;
}

//-------------------------------------------------------------------------------------

//统计二叉树中度为1的节点个数（递归）
int CntDONode_recursive(BiTNode* T){
if(T==NULL||(T->lchild==NULL&&T->rchild==NULL)){
return 0;
    }else if((T->lchild!=NULL&&T->rchild==NULL)||(T->lchild==NULL&&T->rchild!=NULL)){
return CntDONode_recursive(T->lchild)+CntDONode_recursive(T->rchild)+1;
    }else{
return CntDONode_recursive(T->lchild)+CntDONode_recursive(T->rchild);
    }
}

//统计二叉树中度为1的节点个数（非递归）
int CntDONode_norecursive(BiTNode* T){
    BiTNode* p=T;
    SqQueue Q;

    InitQueue(&Q);
    EnQueue(&Q,p);

int cnt=0;
while(IsEmptyQueue(&Q)!=0){
        p=DeQueue(&Q);
if((p->lchild!=NULL&&p->rchild==NULL)||(p->lchild==NULL&&p->rchild!=NULL)){
            cnt++;
        }
if(p->lchild!=NULL){
            EnQueue(&Q,p->lchild);
        }
if(p->rchild!=NULL){
            EnQueue(&Q,p->rchild);
        }
    }
return cnt;
}

//-------------------------------------------------------------------------------------

//统计二叉树中度为2的节点个数（递归）
int CntDTNode_recursive(BiTNode* T){
if(T==NULL){
return 0;
    }
if(T->lchild!=NULL&&T->rchild!=NULL){
return CntDTNode_recursive(T->lchild)+CntDTNode_recursive(T->rchild)+1;
    }else{
return CntDTNode_recursive(T->lchild)+CntDTNode_recursive(T->rchild);
    }
}

//统计二叉树中度为2的节点个数（非递归）
int CntDTNode_norecursive(BiTNode* T){
    BiTNode* p=T;
    SqQueue Q;

    InitQueue(&Q);
    EnQueue(&Q,p);

int cnt=0;
while(IsEmptyQueue(&Q)!=0){
        p=DeQueue(&Q);
if(p->lchild!=NULL&&p->rchild!=NULL){
            cnt++;
        }
if(p->lchild!=NULL){
            EnQueue(&Q,p->lchild);
        }
if(p->rchild!=NULL){
            EnQueue(&Q,p->rchild);
        }
    }
return cnt;
}

//-------------------------------------------------------------------------------------

//先序遍历
void PreOrder(BiTNode* T){
if(T==NULL){
return;
    }
printf("%c",T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

//中序遍历
void InOrder(BiTNode* T){
if(T==NULL){
return;
    }
    InOrder(T->lchild);
printf("%c",T->data);
    InOrder(T->rchild);
}

//-------------------------------------------------------------------------------------

//队列的基本操作

void InitQueue(SqQueue* Q){
    Q->front=0;
    Q->rear=0;
}

void EnQueue(SqQueue* Q, BiTNode* T){
if((Q->rear+1)%MaxSize==Q->front){
return;
    }
    Q->data[Q->rear++]=T;
}

BiTNode* DeQueue(SqQueue* Q){
if(Q->front==Q->rear){
return NULL;
    }
return Q->data[Q->front++];
}

int IsEmptyQueue(SqQueue* Q){
if(Q->rear==Q->front){
return 0;
    }else{
return -1;
    }
}
标签：

相关文章