《完全二叉树总结点数与叶结点数关系分析》由会员分享，可在线阅读，更多相关《完全二叉树总结点数与叶结点数关系分析（8页珍藏版）》请在金锄头文库上搜索。
1、 完全二叉树总结点数 与叶结点数关系分析班级：软件一班 姓名：徐政钧 学号：130120010002对一棵具有n个结点的二叉树按层序编号， 如果编号为i（1in）的结点与同样深度的满二 叉树中编号为i的结点在二叉树中位值完全相同， 则这棵二叉树就称为完全二叉树。完全二叉树定义完全二叉树性质：如果对一棵有n个结点的完全二叉树的结点按层 序编号，则对任一结点i(1in)，有：(1) 如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2(2) 如果2in，则结点i无左孩子；如果2in，则其左孩子是2i(3) 如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1思路1
2、思路2思路1：先用归纳的方法找出完全二叉树中度为1的结点个数n1与总结 点数N的关系，下面给出结点数N=1、2、3、4的完全二叉树 ，如下图N=1 n1=0N=2 n1=1N=3 n1=0N=4 n1=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） 由（2）（3）得 n0=n2+1 -（4） 由（2）（4）得 N=n0+n1+（n0-1）-（5） 最终由（1
3、）（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：将完全二叉树的结点按层序（从上到下， 从左到右）从1开始编号，则N个结点的完全 二叉树中，最后一个结点的编号为N，根据完 全二叉树的性质，编号为N的结点的父节点编 号为【N/2】，如图所示:叶结点个数为总结点个数减去分支结点个数， 而最后结点的父节点是最后一个分支结点，所 以叶结点个数n0=N- 【N/2】返回谢谢观看谢谢观看
