二叉树

                     

贡献者: 有机物

   每个节点最多含有两个子树的树被称为二叉树.

   二叉树的特点:

  1. 每个结点只有两棵子树,分别为左子树和右子树;
  2. 二叉树的左右子树如果位置发生了改变,含义也会发生改变

   不包含任意结点的二叉树称为空树或零树,如果左子树非空,则它的根称为整棵树的根的左孩子,右子树也类似.在一棵二叉树中,如果一个结点仅有一个孩子,则它是左孩子还是右孩子是有关系的.而在有序树中,则是一样的.

   二叉树的性质:

   在第 $i$ 层上最多有 $2 ^ {i - 1}$ 个节点.$(i\geq1)$

   二叉树中深度为 $k$,那么最多有 $2 ^ {k - 1}$ 个节点.$(k\geq1)$,(根节点的深度为 $k_0 = 0$).

   满二叉树:

   国内定义:满二叉树是指每层上的所有结点都有两个子结点的二叉树,最后一层的结点(叶结点)是满的,因此满二叉树形如一个三角形.一个层数为 $k$ 的满二叉树总结点数为 $2^k - 1$.$(k\geq1)$.

   国外定义:如果二叉树的每个节点要么是叶结点,要么正好拥有两个子结点,那么就是一棵满二叉树.

图
图 1:示例图

   如上图在国内就不是一棵满二叉树,而在国外就是一棵满二叉树.

   完全二叉树:

   在一颗二叉树中,若除最后一层外的其余层都是满的,并且最后一层要么是满的,要么结点从左到右依次排列.


致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利