Question

二叉树计算节点

一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为__
告诉下我怎么计算的,谢谢了!

Answer 1

　　二叉树计算节点方法：
　　(1)在二叉树的第k 层上，最多有2k-1(k≥1)个结点，
　　(2)深度为m的二叉树最多有2m-1 个结点，
　　(3)度为0 的结点(即叶子结点)总是比度为2 的结点多一个，
　　(4)具有n 个结点的二叉树，其深度至少为[log2n]+1,其中[log2n] 表示取log2n 的整数部分，
　　(5)具有n 个结点的完全二叉树的深度为[log2n]+1，
　　(6)设完全二叉树共有n 个结点。如果从根结点开始，按层序(每 一层从左到右)用自然数1，2，….n 给结点进行编号(k=1,2….n)， 有以下结论:
　　①若k=1，则该结点为根结点，它没有父结点;若k>1，则该结点的 父结点编号为INT(k/2);
　　②若2k≤n，则编号为k 的结点的左子结点编号为2k;否则该结点 无左子结点(也无右子结点);
　　③若2k+1≤n，则编号为k 的结点的右子结点编号为2k+1;否则该 结点无右子结点。

Answer 2

总结点=度为0的结点个数(叶子结点)+度为1的结点个数+度为2的结点个数;
叶子结点的个数总是比度为2的结点个数多1个;
此题 度为2的结点个数为70-1=69;
总结点=70+69+80=219

Answer 3

度为2的结点数比叶子少一个，叶子用n表示，度为一的结点用n1表示，度为二的结点用n2表示
即
总结点数=n+n1+n2
=n+n1+n-1
=219

Answer 4

N=n1+n2+n0(度为1的节点用n1表示)
N=n1+2n2+1
n2=n0-1
70-1=69
N=80+69+70=219

Answer 5

叶子结点即度为0的节点，度为0的结点总比度为2的结点多一个 70-1＝69即度为2的结点，总结点是度为0.1.2分别相加70+69+80＝219