《叉树的叶子结点和高度.ppt》由会员分享,可在线阅读,更多相关《叉树的叶子结点和高度.ppt(5页珍藏版)》请在金锄头文库上搜索。
1、数据结构(数据结构(C版)版)清华大学出版社清华大学出版社实验四实验四 实验题目:求二叉树叶子结点数和高度实验题目:求二叉树叶子结点数和高度 实验目的实验目的加深理解二叉树的定义和特性;加深理解二叉树的定义和特性;掌握二叉树的存储结构与实现;掌握二叉树的存储结构与实现;掌握二叉树的遍历操作及其应用掌握二叉树的遍历操作及其应用 实验内容:根据键盘输入的扩展二叉树实验内容:根据键盘输入的扩展二叉树的前序遍历序列建立相应的二叉树,并的前序遍历序列建立相应的二叉树,并计算该二叉树的叶子结点个数和高度。计算该二叉树的叶子结点个数和高度。数据结构(数据结构(C版)版)清华大学出版社清华大学出版社设计思想设
2、计思想存储结构:二叉链表存储结构:二叉链表基本思想:利用二叉树的遍历操作,设计递基本思想:利用二叉树的遍历操作,设计递归算法实现。归算法实现。递归模式:一整棵二叉树树的叶子结点数递归模式:一整棵二叉树树的叶子结点数 左左子树的叶子结点数子树的叶子结点数 右子树的叶子结点数右子树的叶子结点数递归出口递归出口求二叉树的高度:参见课件求二叉树的高度:参见课件数据结构(数据结构(C版)版)清华大学出版社清华大学出版社实验步骤实验步骤定义结点结构并声明二叉链表类定义结点结构并声明二叉链表类实现构造函数和析构函数,并用前序遍历操作验实现构造函数和析构函数,并用前序遍历操作验证一下二叉树的建立是否正确。在调
3、用遍历操作证一下二叉树的建立是否正确。在调用遍历操作时需要一个参数时需要一个参数根指针根指针root,而,而root一般定一般定义为私有成员,所以在二叉链表类中还需再声明义为私有成员,所以在二叉链表类中还需再声明一个公有函数一个公有函数用来返回根指针。用来返回根指针。在正确建立好二叉树后,实现求叶子结点数的算在正确建立好二叉树后,实现求叶子结点数的算法。法。在正确建立好二叉树后,实现求高度的算法。在正确建立好二叉树后,实现求高度的算法。数据结构(数据结构(C版)版)清华大学出版社清华大学出版社数据结构(数据结构(C版)版)清华大学出版社清华大学出版社附加附加实验题目:求二叉树中度为实验题目:求二叉树中度为1的结点个数的结点个数实验题目:输出二叉树中层数最大的所实验题目:输出二叉树中层数最大的所有结点有结点