你的位置: 诗词网   >   问答   >   小学   >   数学   >   满二叉树的叶结点个数为N,则它的结点总数...

   问题:

满二叉树的叶结点个数为N,则它的结点总数为给一下具体的说明吧

问题描述:

满二叉树的叶结点个数为N,则它的结点总数为

给一下具体的说明吧

田新东回答:

  你明天参加信息学比赛?2*N-1.

  这相当于常识.

  2.两个重要的概念:

  (1)完全二叉树——只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树;

  (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,.

  3.二叉树的性质

  (1)在二叉树中,第i层的结点总数不超过2^(i-1);

  (2)深度为h的二叉树最多有2h-1个结点(h>=1),最少有h个结点;

  (3)对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,

  则N0=N2+1;

  (4)具有n个结点的完全二叉树的深度为int(log2n)+1

  (1)先序遍历

  访问根;按先序遍历左子树;按先序遍历右子树

  (2)中序遍历

  按中序遍历左子树;访问根;按中序遍历右子树

  (3)后序遍历

  按后序遍历左子树;按后序遍历右子树;访问根