二叉树（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 − 1 2^{k−1} 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、层次遍历 思路：从上到小，从左到右遍历 ABCDEFJHIJK
已知一棵二叉树bai前序遍和中序遍历分du别为ABDEGCFH和DBGEACHF，则该二叉树的zhi后序遍历dao是DGEBHFCA。
前序遍历的第一个节点为根节点，由前序遍历可知，A为根节点。中序遍历的根节点前面的节点均为左子树的节点，所以左子树上的节点为DBGE。去掉根节点和左子树节点，右子数节点为CHF。前序遍历的第二个节点为B，由2知B为左子树节点，所以B为左子树的根节点。
由前序遍历，DEG在B节点下面，由中序遍历，D是B的左节点，GE是B的右节点。由前序遍历，E是G的根节点，由中序遍历，G是E的左子节点。由前序遍历，C是二叉树的右根节点，由中序遍历，C不含左子节点，HF为C的右子节点。由前序遍历，F为H的根节点，由中序遍历，H为F的左子节点。
在二叉树中，求后序遍历，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。则该二叉树的后序遍历是DGEBHFCA。
已知一棵二叉树，前序遍历的节点顺序是：ABDEGHCFI，中序遍历的节点顺序是：DBGEHAFCI，其后序遍历的顺序是：DGHEBFICA
