MENU

求二叉树叶子结点个数

• November 12, 2020 •

编写算法,求二叉树叶子结点的个数


题目分析:

求二叉树的叶子结点,就是求二叉树上左右孩子结点都是空的结点,还记得二叉树的三种遍历方式吗?前序遍历、中序遍历和后序遍历,在递归遍历算法中,无论采取哪种遍历方式,我们只需要添加一个条件就可以求得树的叶子结点啦

判断是否是叶子结点的条件是:

题中我采用的前序遍历,我们看代码吧

建立的二叉树形状:

代码实现:

注:此代码除《Domain.h》里面的算法之外,其余代码皆为二叉树的基本操作内容,若有不明白的地方可参考文章:树的基本操作

BiTree.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
//结点的结构体
struct  BiTreeNode
{
    char data;             //数据域
    BiTreeNode *LeftChild; //左指针域
    BiTreeNode *RightChild;//右指针域
};
typedef BiTreeNode DataType;
//初始化
void initiate(BiTreeNode **root)
{
    (*root) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    (*root)->LeftChild = NULL;
    (*root)->RightChild = NULL;
}
//在结点的左孩子结点插入新的数据结点
BiTreeNode *LeftInsert(BiTreeNode *root, char data)
{
    if (root == NULL)
    {
        printf("未找到当前结点,插入失败!\n");
        return NULL;
    }
    BiTreeNode *q = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    q->data = data;
    q->RightChild = NULL;
    q->LeftChild = root->LeftChild;
    root->LeftChild = q;
    return q;
}
//在结点的右孩子结点插入新的数据结点
BiTreeNode *RightInsert(BiTreeNode *root, char data)
{
    if (root == NULL)
    {
        printf("未找到当前结点,插入失败!\n");
        return NULL;
    }
    BiTreeNode *q = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    q->data = data;
    q->LeftChild = NULL;
    q->RightChild = root->RightChild;
    root->RightChild = q;
    return q;
}
//访问数据域
void Visit(char data)
{
    printf("%c  ", data);
}
//二叉树的前序遍历
void PreOrder(BiTreeNode *root)
{
    if (root != NULL)
    {
        Visit(root->data);
        PreOrder(root->LeftChild);
        PreOrder(root->RightChild);
    }
}

Domain.h:

#pragma once
#include"BiTree.h"
/*求二叉树叶子结点个数,采用前序遍历*/
int NumOfLeff(DataType *root)
{
    //采用static,每次进入函数的时候number不会被重新置0
    static int number = 0;
    if (root != NULL)
    {
        /*判断为叶子结点的条件——没有左右孩子结点*/
        if (root->LeftChild == NULL && root->RightChild == NULL)
            number++;
        NumOfLeff(root->LeftChild);
        NumOfLeff(root->RightChild);
    }
    return number;
}

main.c:

#include"Domain.h"
int main()
{
    DataType *root,*p;
    initiate(&root);
    p = root;
    p = LeftInsert(p, 'A');
    p = LeftInsert(p, 'B');
    p = LeftInsert(p, 'D');
    LeftInsert(p, 'H');
    RightInsert(p, 'G');
    p = RightInsert(root->LeftChild , 'C');
    LeftInsert(p, 'E');
    RightInsert(p, 'F');
    //以上为创建一颗二叉树
    printf("前序遍历:\n");
    PreOrder(root->LeftChild);
    //测试叶子结点个数
    printf("\n叶子结点个数:");
    printf("%d  \n", NumOfLeff(root->LeftChild));
    system("pause");
    return 0;
}

代码编译器:Visual Studio 2017
ok

Archives QR Code Tip
QR Code for this page
Tipping QR Code