实验七 二叉树的链式存储结构、性质 实验目的 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 项目中，找出定义二叉树结点类型的相关语句，理解二叉树结点的定义方法。

4.在 content.cpp 文件中的main( ) 函数的 return 0; 语句处设置断点，调试程序，观察此二叉树在内存中的存储结构，加深理解：

5.在BiTree项目的基础上，使用递归编写 计算二叉树叶子结点个数的函数： int N0(BTNode *root);

与计算二叉树双分支结点个数的函数： int N2(BTNode *root);

验证二叉树的下列性质： 非空二叉树上的叶子结点个数等于双分支结点个数加1： n0 = n2 + 1

//计算二叉树叶子结点个数的函数

}

//计算二叉树双分支结点个数的函数

}