二叉树的理解

二叉树的理解

什么是二叉树：是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不相交的，分别称为根节点的左子树和右子树的二叉树组成。

二叉树的三种情况：   没有节点   两个节点  一个节点    

特殊二叉树：

                   斜树          左斜树  右斜树 

                  满二叉树       除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。

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

 

非完全二叉树：其实上面的没有满足完全二叉树的例子就可以称为非完全二叉树。

 

二叉树的性质：

          

 顺序储存：

顺序存储一般只用于完全二叉树

顺序存储就是用数组来存储的，虽然不如指针域那么直观，但是存储的方法挺好理解的。根节点存储在下标 i = 1 的位置；

左子节点存储在下标i * 2 = 2的位置，右子节点存储在i * 2 + 1 =3的位置。

顺序表资源

TwoTree.rar-Unity3D文档类资源-CSDN下载

链表储存：基于指针的链式存储，每个树的节点都是由数据域和两个指针域组成的。数据域用来存储数据，指针域用来存储左右两个子节点。缺点浪费空间

链表不懂的可以看这个资源

BinaryTreelinked.rar-Unity3D文档类资源-CSDN下载