数据结构二叉树的基本介绍

————————————本文旨在讨论与学习计算机知识，欢迎交流———————————— 上一章，我们讲解了树结构的综述导论，那么，现在我们来深入了解一下树结构中最常用研究的结构——二叉树结构（上一章的扩展——孩子兄弟表示法就是利用的二叉树的原理）。 以上是关于普通二叉树的基本概念，我们可以结合上一章树的概念记忆。特别的，我们需要注意：二叉树是度不超过二的树，其子树也是二叉树。 下面，我们来了解一下有关二叉树的两个重要概念：满二叉树与完全二叉树。

1、满二叉树

满二叉树是指除了叶子结点外的每一个节点的度都是二且深度相同的树。

2、完全二叉树

完全二叉树是指度不为二的节点只存在与倒数二、三行且叶子结点只存在于倒数一、二行的树。

介绍完满二叉树与完全二叉树的基本概念之后，我们下面要剖析它们的重要性质：

性质1：在二叉树的第i层上的结点最多为2 个。(i ≥ 1)

性质2：深度为k的二叉树至多有2 -1个结点。(i ≥ 1)

性质3：在一棵二叉树中，叶结点的数目比度为2的结点数目多一个。

原理：

加的1为根节点，其解释为：度为1的节点1+度为2的节点2+根节点。

性质4：

性质5：如果有一棵n个结点的完全二叉树，其结点编号按照层次序（从上到下，从左到右），则除根结点外，满足[i/2 , i, 2i, 2i+1]（父，自身，左孩子，右孩子）的规则。

二叉树的存储：

通常，我们摒弃顺序存储（除了少量特殊的二叉树），因为这种存储方式非常浪费空间，我们更多使用链式存储来存储数据。而对于树，链式二叉树我们也有树头，树头作为起点更新和查找树上元素，不过当前我们仍不能自由快速的查询元素，直到我们学到二叉搜索树的时候我们会再次介绍树的搜索与遍历操作。 希望能对你有所帮助！