[数据结构]二叉树概念

树的概念：

树是一种非线性的数据结构，它是由n(n>=0)个有限节点组成一个具有有限关系的集合。把它叫做树，是因为它看起来像一颗倒挂的树，也就是它是根朝上，而叶朝下的。

1.有一个特殊的节点，称为根节点，根结点没有前驱节点 2.除根节点外，其余部分被分成M(M>0)个互不相交的集合T1、T2...Tm，其中每一个集合Ti(10 ， i 位置节点的双亲序号： (i-1)/2 ； i=0 ， i 为根节点编号，无双亲节点

2. 若 2i+1=n 否则无左孩子

3. 若 2i+2=n 否则无右孩子

二叉树的存储结构：

二叉树一般可以使用两种结构存储：一种顺序结构，一种链式结构。

1.顺序存储：

顺序结构存储就是使用 数组来存储 ，一般使用数组 只适合表示完全二叉树 ，因为不是完全二叉树会有空

间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。 二叉树顺 序存储在物理上是一个数组，在逻辑上是一颗二叉树。

 链式存储：

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是

链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所

在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程

学到高阶数据结构如红黑树等会用到三叉链。