学生作业 制作一个网站,西峡微网站开发,万户网络合肥,内蒙古城乡建设部网站首页目录
1.求二叉树总的节点的个数
1.容易想到的方法
代码
缺陷
思考:能否在TreeSize函数内定义静态变量解决size的问题呢?
其他写法
运行结果
2.最好的方法:分而治之
代码
运行结果
2.求二叉树第K层节点的个数
错误代码
运行结果
修正
运行结果
其他写法 1.求二…目录
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;//根节点1TreeSize(root-left);TreeSize(root-right);
}int main()
{BTNode* root CreateTree();TreeSize(root);printf(TreeSize%d, size);return 0;
}
备注:CreateTree建立的是下面这棵二叉树 递归的思想和103.【C语言】数据结构之二叉树的三种递归遍历方式文章相同,不再赘述
运行结果 缺陷
本方法有缺陷,当多次调用时必须手动为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;
}
运行结果会出错 每一次调用前必须手动置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);//根节点1TreeSize(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;
}
运行结果 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层节点的个数
分析:比如求下图K3层的节点个数,按递归思想分析 递推:关键点:要以不同的视角来看待第K层
求K层--求根节点的左右子树的第K-1层--求根节点的左右子树的第K-2层--...--求根节点的左右子树的第1层 由上述分析可知TreeLevel函数需要BTNode* root和int k两个参数,这里k必须大于0(assert(k0);)
错误代码
int TreeLevel(BTNode* root, int k)
{assert(k0);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的情况,导致00...00 if (root NULL){return 0;}
TreeLevel返回有两种情况:1.根节点为NULL 2.k1
修改后
int TreeLevel(BTNode* root, int k)
{assert(k0);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(k0);if (root NULL){return 0;}if (k 1){return 1;}return TreeLevel(root-left, k - 1) TreeLevel(root-right, k - 1);
}
