二叉树（Binary Tree）是包含n个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。 1）有且仅有一个特定的称为根Root的结点。 2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集，其中每个集合本身又是一个棵树，并称为根的子树。 还有一些其他的概念： 1、跟节点：树的顶端节点 2、分支节点：至少有一个子节点的节点 3、度：节点所拥有的子树个数 4、边：一个节点到另一个节点之间的连接 5、路径：连接节点和其后代的节点之间的节点和边的序列 6、节点的层数：从根结点到该节点的所有节点个数 7、 节点的深度：从根节点到该节点边的个数 8、节点的高度：节点的高度是该节点和某个叶子之间存在的最长路径上的边的个数。 9、树的高度：根节点的高度

（1）在二叉树中，第 i层上至多有 2 i − 1 2^{i−1} 2i−1个节点（i≥1） （2）深度为k的二叉树至多有 2 k 2^{k} 2k−1个节点（k≥1） （3）对一棵二叉树，如果叶子节点的个数为n0，度为2的节点个数为n2，则n0=n2+1 （4）具有n个节点的完全二叉树的深度为⌊log2n⌋+1

对于完全二叉树而言，可以使用顺序存储结构。但是对于一般的二叉树来说，使用存储结构会有两个缺点，一，如果不是完全二叉树，则必须将其转化为完全二叉树，二是增加了很多虚节点，浪费资源空间。

这是最常用的一种二叉树存储结构。每个结点设置三个域，即值域，左指针域和右指针域，用data表示值域，lchild和rchild分别表示指向左右子树的指针域。如图所示。

在二叉树的操作中，二叉树的遍历是基本的操作，对于二叉树的遍历操作，主要分为： 前序遍历、中序遍历、后序遍历、层次遍历 实际上二叉树的遍历是一个递归的过程 前序遍历的递推公式： preOrder® = print r->preOrder(r->left)->preOrder(r->right) 中序遍历的递推公式： inOrder® = inOrder(r->left)->print r->inOrder(r->right) 后序遍历的递推公式： postOrder® = postOrder(r->left)->postOrder(r->right)->print r

1、前序遍历：根左右 思路：先访问根，然后遍历左子树，再遍历右子树 ABDHIEJCFKG

2、中序遍历：左根右 思路：先遍历左子树，再访问根，最后遍历右子树 HDIBEJAFKCG

3、后序遍历：左右根 思路：先遍历左子树，再遍历右子树，最后访问根 HIDJEBKFGCA

4、层次遍历 思路：从上到小，从左到右遍历 ABCDEFGHIJK