二叉树是一种十分重要的树型结构。它的特点是，树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于２。二叉树的子树有左右之分，而且，子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清是左子树还是右子树。
（一）定义
<br>
二叉树是结点的有限集合，这个集合或是空的，或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。<BR> 图2列出了二叉树的五种基本形态。
<br>
<P align=center><IMG height=103 src="file:///C:/Documents%20and%20Settings/Administrator/桌面/新建文件夹/新建文件夹/Binary%20Tress二叉树的遍历☆%20☆%20温州中学信息学奥赛基地%20☆%20☆.files/0321-2.gif" width=472>
<br>
图 2
<br>
(a)为空二叉树；(b)只有一个结点的二叉树；(c)只有左子树的二叉树；(d)只有右子树的二叉树；(e)左右完全的二叉树。
<br>
（二）满二叉树
<br>
一棵深度为K的满二叉树，是有2^K-1个结点的深度为K的二叉树。2^K-1个结点是二叉树所能具有的最大结点个数。图3所示为一棵深度为４的满二叉树。
<br>
<P align=center><IMG height=180 src="file:///C:/Documents%20and%20Settings/Administrator/桌面/新建文件夹/新建文件夹/Binary%20Tress二叉树的遍历☆%20☆%20温州中学信息学奥赛基地%20☆%20☆.files/0321-3.gif" width=509>
<br>
<br>
<BR> <BR> 图 3 图 4
<br>
（三）完全二叉树
<br>
对满二叉树，从第一层的结点(即根)开始，由下而上，由左及右，按顺序结点编号，便得到满二叉树的一个顺序表示。据此编号，完全二叉树定义如下：一棵具有ｎ个结点，深度为K的二叉树，当且仅当所有结点对应于深度为K的满二叉树中编号由１至ｎ的那些结点时，该二叉树便是完全二叉树。图4是一棵完全二叉树。
<br>
（四）二叉树的存储
<br>
二叉树一般采用双重链表作为其存储结构，表中每个结点都有三个域：数据域DATA、左指针域LCHILD和右指针域RCHILD。其中指针域LCHILD和RCHILD分别指向其左孩子和右孩子。如图5所示。
<br>
<P align=center><BR><IMG height=92 src="file:///C:/Documents%20and%20Settings/Administrator/桌面/新建文件夹/新建文件夹/Binary%20Tress二叉树的遍历☆%20☆%20温州中学信息学奥赛基地%20☆%20☆.files/0321-4.gif" width=428>
<br>
<BR> 图5 二叉树结点的结构形式
<br>
三、二叉树的遍历
<br>
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
<br>
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。
<br>
（一）先根次序遍历的递归定义
<br>
若二叉树为空，则返回；否则，依次执行以下操作：<BR> ⒈访问根结点；<BR> ⒉按先根次序遍历左子树；<BR> ⒊按先根次序遍历右子树；<BR> ⒋返回。
<br>
例1 图6为表示表达式 （ａ＋ｂ×（ｃ－ｄ））－ｅ/ｆ的二叉树。
<br>
<P align=center><IMG height=255 src="file:///C:/Documents%20and%20Settings/Administrator/桌面/新建文件夹/新建文件夹/Binary%20Tress二叉树的遍历☆%20☆%20温州中学信息学奥赛基地%20☆%20☆.files/0321-5.gif" width=232>
<br>
<br>
图 6
<br>
先序遍历此树时，首先访问根结点，得到字符"－"。继而访问结点"－"的左子树，按递归定义，先访问子树的根结点，得到字符"＋"。类推访问结点"＋"的左子树，此时只有叶子。得到叶子"ａ"后，访问叶子"ａ"父结点的右子树，得到右子树的根结点字符"×"。再访问结点"×"的左子树，得到叶子字?quot;ｂ"后，访问字符"ｂ"父结点的右子树，得到右子树根结点字符"－"，……。先序遍历完整棵树，得到序列为： －＋ａ×ｂ－ｃｄ/ ｅｆ<BR> 这就是表达式的前缀表示或称波兰表示。
<br>
（二）中根次序遍历的递归定义
<br>
若二叉树为空，则返回；否则，作如下操作：<BR> ⒈按中根次序遍历左子树；<BR> ⒉访问根结点；<BR> ⒊按中根次序遍历右子树；<BR> ⒋返回。
<br>
中序遍历图6二叉树保胝唬冉岬阕址?quot;－"入栈，按定义访问根结点的左子树，遇到子树的根结点字符"＋"入栈，访问结点"＋"的左子树，到达叶子字符"ａ"，则字符"ａ"为第一个访问的结点。接着，将栈顶字符出栈，访问子树根结点字符"＋"。继而访问其右子树，方法同上，子树根结点"×"入栈，……。这样，中序遍历完整棵树后，得到的序列为： ａ＋ｂ×ｃ－ｄ－ｅ/ ｆ<BR>这就是表达式的中缀表示。
<br>
（三）后根次序遍历的递归定义
<br>
若二叉树为空，则返回；否则，作如下操作：<BR> ⒈按后根次序遍历左子树；<BR> ⒉按后根次序遍历右子树；<BR> ⒊访问根结点；<BR> ⒋返回。<BR> 对图6二叉树，后序遍历后得到的序列为： ａｂｃｄ－×＋ｅｆ/ －<BR> 这就是表达式的后缀表示或称表达式的逆波兰表示。逆波兰表示的表达式的优点在于它得到的是不加括号的表示式，但从表示式中确能确定表达式的运算先后顺序。故在源程序如下编译表达式值的处理等方面的应用中经常用到。 <BR>
