完全二叉树总结点数与叶结点数关系分析.pptx

《完全二叉树总结点数与叶结点数关系分析.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、完全二叉树总结点数与叶结点数关系分析班级：软件一班姓名：徐政钧学号：130120010002对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位值完全相同，则这棵二叉树就称为完全二叉树。完全二叉树定义完全二叉树性质：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2(2)如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i(3)如果2i+1>n，则结点i无右孩子；如

2、果2i+1n，则其右孩子是2i+1思路1思路2思路1：先用归纳的方法找出完全二叉树中度为1的结点个数n1与总结点数N的关系，下面给出结点数N=1、2、3、4的完全二叉树，如下图N=1n1=0N=2n1=1N=3n1=0N=4n1=1通过观察不难发现，度为1的结点个数n1=0，1，0，1……n为奇数时，n1=0，n为偶数时，n1=1；------------（1）总结点个数可以表示为N=n0+n1+n2；------------（2）结点总数=二叉树分支数+1；二叉树分支数=0*no+1*n1+2*n2故N=1*n1+2*n2+1-----------

3、-----------------（3）由（2）（3）得n0=n2+1--------------------（4）由（2）（4）得N=n0+n1+（n0-1）----------（5）最终由（1）（5）得当N为奇数时，N=2n0-1，n0=（N+1）/2当N为偶数时，N=2n0，n0=N/2返回思路2：将完全二叉树的结点按层序（从上到下，从左到右）从1开始编号，则N个结点的完全二叉树中，最后一个结点的编号为N，根据完全二叉树的性质，编号为N的结点的父节点编号为【N/2】，如图所示:N为偶数N为奇数思路2：将完全二叉树的结点按层序（从上到下，从左到右）

4、从1开始编号，则N个结点的完全二叉树中，最后一个结点的编号为N，根据完全二叉树的性质，编号为N的结点的父节点编号为【N/2】，如图所示:叶结点个数为总结点个数减去分支结点个数，而最后结点的父节点是最后一个分支结点，所以叶结点个数n0=N-【N/2】返回谢谢观看