作者:百变精灵99 | 来源:互联网 | 2023-07-01 13:27
实验七二叉树的链式存储结构、性质实验目的1.了解二叉树的链式存储结构。2.了解二叉树的相关性质。实验环境Windows7以上版本的操作系统,VisualStudio2019以上版本
实验七 二叉树的链式存储结构、性质
实验目的
1.了解二叉树的链式存储结构。
2.了解二叉树的相关性质。
实验环境
Windows 7以上版本的操作系统,Visual Studio 2019以上版本的编程环境。
实验内容和步骤
1.已知一棵完全二叉树的第6层(设根为第1层)有8个叶子结点,则该完全二叉树的结点个数最多是多少?最少是多少?
第6层有8个叶子,因此可知,最少时就是第6层有而且只有8个叶子结点,此时到第5层为满二叉树,最多就是第6层除了8个叶子外,都是度为2的结点,该层度为2结点个数为2^(6-1) – 8 = 24,也就是说除了到第6层是满二叉树外,还有7层,而且第7层有24*2 = 48个结点
最少:(2^5 – 1)+ 8= 31 + 8 = 39
最多:(2^6 – 1) + 48= 63 + 48 = 111**
2.根据下图所示的二叉树,画出其链式存储结构图。
3.在课件目录提供的BiTree 项目中,找出定义二叉树结点类型的相关语句,理解二叉树结点的定义方法。
typedef struct node {
ElemType data; //数据域
struct node *left;
struct node *right; //结点的左右子树指针
} BTNode; //二叉树结点类型
4.在 content.cpp 文件中的main( ) 函数的 return 0; 语句处设置断点,调试程序,观察此二叉树在内存中的存储结构,加深理解:
5.在BiTree项目的基础上,使用递归编写
计算二叉树叶子结点个数的函数:
int N0(BTNode *root);
与计算二叉树双分支结点个数的函数:
int N2(BTNode *root);
验证二叉树的下列性质:
非空二叉树上的叶子结点个数等于双分支结点个数加1:
n0 = n2 + 1
//计算二叉树叶子结点个数的函数
int N0(BTNode* root)
{ int count = 0;
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL)
return 1;
else {
count=N0(root->left) + N0(root->right);
return count;
}
}
//计算二叉树双分支结点个数的函数
int N2(BTNode* root)
{
if (root == NULL) return 0;
int r;//r是用来记录根节点是否为双分支
if (root->left != NULL && root->right != NULL)
r=1;
else r = 0;
return r + N2(root->left) + N2(root->right);//根+左子树+右子树
}