自学内容网 自学内容网

105.【C语言】数据结构之二叉树求总节点和第K层节点的个数

目录

1.求二叉树总的节点的个数

1.容易想到的方法

代码

缺陷

思考:能否在TreeSize函数内定义静态变量解决size的问题呢?

其他写法

运行结果

2.最好的方法:分而治之

代码

运行结果

2.求二叉树第K层节点的个数

错误代码

运行结果

修正

运行结果

其他写法


1.求二叉树总的节点的个数

1.容易想到的方法

借助103.【C语言】数据结构之二叉树的三种递归遍历方式文章的遍历函数的思想

以前序遍历函数的思想为例

void PreOrder(BTNode* root)
{
//先判断是否为空树(叶节点的左节点和右节点均为空树)
if (root == NULL)
{
printf("NULL ");
return;
}
 
//按根-->左子树-->右子树的顺序遍历
printf("%d ",root->data);
PreOrder(root->left);
PreOrder(root->right);
}

设计TreeSize函数,设size存储二叉树的总的节点的个数,由于局部变量在函数返回时会发生销毁,显然应该使用全局变量size,在main函数外部写int size;(默认初始值为0)

代码

#include "Tree.h"
int size;
void TreeSize(BTNode* root)
{
if (root == NULL)//为NULL,则返回,不+1
{
return;
}

size++;//根节点+1
TreeSize(root->left);
TreeSize(root->right);
}

int main()
{
BTNode* root = CreateTree();
TreeSize(root);
printf("TreeSize==%d", size);
return 0;
} 

备注:CreateTree建立的是下面这棵二叉树

c1b93c8d50e7492e8f0316990818f57a.png
 

递归的思想和103.【C语言】数据结构之二叉树的三种递归遍历方式文章相同,不再赘述

运行结果

1810fb1a01884fa6b5c0e72fb6fd1746.png

缺陷

本方法有缺陷,当多次调用时必须手动为size置0

若像下面这样不置0


int main()
{
BTNode* root = CreateTree();
TreeSize(root);
printf("TreeSize==%d\n", size);
TreeSize(root);
printf("TreeSize==%d\n", size);
TreeSize(root);
printf("TreeSize==%d\n", size);
return 0;
} 

运行结果会出错

1788d73414a940f0ace0dd190a7efa12.png

每一次调用前必须手动置0,像下面这样


int main()
{
BTNode* root = CreateTree();
TreeSize(root);
printf("TreeSize==%d\n", size);

    size = 0;
TreeSize(root);
printf("TreeSize==%d\n", size);

    size = 0;
TreeSize(root);
printf("TreeSize==%d\n", size);
return 0;
} 

思考:能否在TreeSize函数内定义静态变量解决size的问题呢?

答:不可以,理由1:无论函数调用多少次,写在函数内的静态变量只会被初始化一次,即第二,三,四,...次调用不会初始化.理由2:在函数外部无法访问静态变量

其他写法

TreeSize多传一个参数

#include "Tree.h"
void TreeSize(BTNode* root,int* psize)
{
if (root == NULL)//为NULL,则返回,不+1
{
return;
}

(*psize)++;//根节点+1
TreeSize(root->left, psize);
TreeSize(root->right, psize);
}


int main()
{
BTNode* root = CreateTree();
int size1 = 0;
TreeSize(root, &size1);
printf("TreeSize==%d\n", size1);


int size2 = 0;
TreeSize(root, &size2);
printf("TreeSize==%d\n", size2);

int size3 = 0;
TreeSize(root, &size3);
printf("TreeSize==%d\n", size3);

return 0;
}
运行结果

3412e19c2ded489b9672f6cef3a9fbb2.png

2.最好的方法:分而治之

形象说法:找"下属"分担任务(递归),让"下属"帮忙计数,"下属"统计好个数交给"上司"(此方法不用定义size)

递推:根将任务交给左子树和右子树,左子树和右子树将任务分别交给它们的左子树和右子树,左子树和右子树将任务分别交给它们的左子树和右子树...一直到空树结束

代码

int TreeSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }

    return TreeSize(root->left) + 1 + TreeSize(root->right);//+1加的是自己本身
}

int main()
{
    BTNode* root = CreateTree();
    printf("TreeSize=%d\n", TreeSize(root));
    printf("TreeSize=%d\n", TreeSize(root));
    printf("TreeSize=%d\n", TreeSize(root));
    return 0;
}

运行结果

可见无论TreeSize被执行多少次,打印的结果都是一样的,从而避免了要将size置为0的问题

2.求二叉树第K层节点的个数

分析:比如求下图K=3层的节点个数,按递归思想分析

递推:关键点:要以不同的视角来看待第K层

求K层-->求根节点的左右子树的第K-1层-->求根节点的左右子树的第K-2层-->...-->求根节点的左右子树的第1层

由上述分析可知TreeLevel函数需要BTNode* root和int k两个参数,这里k必须大于0(assert(k>0);)

错误代码

int TreeLevel(BTNode* root, int k)
{
    assert(k>0);
    if (root == NULL)
    {
        return 0;
    }

    int lnum = TreeLevel(root->left, k - 1);
    int rnum = TreeLevel(root->right, k - 1);
    return lnum + rnum;
}

int main()
{
    BTNode* root = CreateTree();
    printf("TreeLevel=%d", TreeLevel(root, 3));
    return 0;
}
运行结果

运行结果显然是有问题的,怎么修正?

修正

错误原因:考虑其一没有考虑其二,if判断处一直返回0,没有返回1的情况,导致0+0+...+0==0

    if (root == NULL)
    {
        return 0;
    }

TreeLevel返回有两种情况:1.根节点为NULL 2.k==1

修改后

int TreeLevel(BTNode* root, int k)
{
    assert(k>0);
    if (root == NULL)
    {
        return 0;
    }

    if (k == 1)
    {
        return 1;
    }
    int lnum = TreeLevel(root->left, k - 1);
    int rnum = TreeLevel(root->right, k - 1);
    return lnum + rnum;
}
运行结果

结果正确

其他写法

不用变量存储,直接返回相加的值

int TreeLevel(BTNode* root, int k)
{
    assert(k>0);
    if (root == NULL)
    {
        return 0;
    }

    if (k == 1)
    {
        return 1;
    }
    return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}


原文地址:https://blog.csdn.net/2401_85828611/article/details/144118040

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!