1.树是什么？
之所以被称之为树，是因为其结构神似一棵倒挂着的树。
而一棵树是由零到多个节点所构成的，而我们使用父子关系形容相连节点之间的关系。例如下图中的“3”和“4”节点，“3”节点被称为“4”节点的父节点，而“4”节点被称为“3”节点的子节点。也就是说，在相连的两个节点之间，处于上方的节点被称为处于下方的节点的父节点，而处于下方的节点被称为上方节点的子节点。
一个节点含有的子节点的个数被称为该节点的度。
没有父节点的节点被称为根节点。一棵树最多只有一个根节点，而在逻辑结构图中则表示为最上方的节点，也就是“3”节点是这棵树的根节点。并且，子树之间不能相交。除了根节点，其他节点有且仅有一个父节点。
下面我们联系上图介绍一些关于树的重要的基本概念：
?一个节点的子节点个数被称为该节点的度。如图中的“6”节点的度为2。
度为0的节点被称为叶子节点。如图中的“2”，“8”，“9”，“1"都是叶子节点。
一棵树的最大层次被称之为该树的高度或者深度。例如上图的树的高度为4。
?了解完了树的基本概念，我们来进一步理解二叉树是什么。
?2.二叉树入门
2.1二叉树的概念
二叉树是一种特殊的树。
其结构特点为一颗二叉树由根节点与其称为左子树、右子树的二叉树构成。
并且，二叉树可以为空。
?从结构特点出发，我们知道：二叉树的所有节点的度都不大于2。
一棵二叉树可能有几种存在情况：
?而二叉树中，存在特殊的情况：
2.2特殊的二叉树
满二叉树
若一棵树的每一层的节点数都达到最大值，则称该二叉树为满二叉树。
完全二叉树
将一棵树从上到下，从左到右从1开始给每个节点编号，若其编号为i的节点与一颗满二叉树中编号为i的节点所处的位置相同，则该二叉树称为完全二叉树。
要理解完全二叉树，我们通过画图进行解释：
我们先将一棵树从上到下，从左到右从1开始给每个节点编号
?接着，我们画出一个高度为3的满二叉树。
?很明显，我们所画的树编号为5的节点与满二叉树中编号为5的节点的位置并不相同，根据定义，只要有一个节点不能与满二叉树对应，该二叉树就不是完全二叉树。
但是如果5的节点的位置改变：
可以看到，新的二叉树的所有节点的编号都能与满二叉树的编号相同，那么新的二叉树就是一棵完全二叉树。
此外，二叉树还有一些需要我们了解的基本性质：
2.3二叉树的基本性质
1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(n-1)个结点。
2.若规定根节点的层数为1，则深度为h的二叉树最多节点数为2^h-1。
3.对任何一棵二叉树而言，度为0的节点数量（设为n0） 等于 度为2的节点数量（设为n2） + 1。即n0=n2+1。
4.对于具有n个节点的满二叉树，若规定根节点的层数为1，则其高度h=log(2)(n+1)? (log(2)(n+1)指log以2为底以n+1为对数)。
2.4二叉树的储存结构
最后，我们来了解二叉树是如何储存的。
二叉树一般有两种储存方式：顺序结构和链式结构。
二叉树的顺序存储
顺序储存指的是用数组来表示二叉树，但是一般只有完全二叉树才会采用数组的方式来存储，因为非完全二叉树会存在空间上的浪费。
二叉树的链式存储
链式存储是指用链表来表示二叉树。 表示的方法分为三叉链表和二叉链表，这里我们介绍二叉链表。在二叉链表中，每个节点由三个部分组成：该节点左子节点的地址、该节点右子节点的地址以及保存的数据。
?用结构体表示每个节点：
typedef int TreeDataType;
struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
TreeDataType a;
};