父亲或父结点）。
结点层次：树中的每个结点相对树的根结点都有一定的层次，我们定义： ? 树的根结点为第1层。
? 树中的其它结点都比它的父结点多一层。 树的深度（或高度）：树中结点的最大层次称为树的深度（或高度）。
第1层 A 第2层 B C D 第3层 E F G H
第4层 I 图5.1.2 树的层次
单目运算符：运算符只有一个运算对象，如 NOT； 双目运算符：运算符有二个运算对象，如 +，*； 双目运算符：运算符有三个运算对象，如 f(x,y,z)；
1.6.2二叉树定义及性质 1. 二叉树定义
一棵二叉树是有限元素的集合，它可以为空，当二叉树非空时，其中有一个称为二叉树根结点的元素，并且剩余的元素（如果存在）被分成两个不相交的子集，每个子集又是一棵二叉树，这两个子集被称为根的左子树和右子树。二叉树的每个元素被称为一个结点。
A B C
D E F
G
图5.2.1 一棵二叉树
2. 二叉树的定义与树的定义的区别 ? 二叉树存在着空树；但树不能为空。
? 二叉树中的每一个结点只可能有0个，1个或2个孩子，也就是说，二叉树不存在度大
于2的结点；而树中的每个结点可以有多个子树。
? 二叉树的子树有左右之分，两者不能颠倒；但树的子树一般是无序的。 3. 满二叉树的定义
若二叉树中所有分枝结点的度数都为2，且叶子结点都在同一层上，则称这类二叉树为满二叉树。
A B D E F C G
一棵满二叉树是除了最深一层上有叶子结点外，其它层次上都是分枝结点。如图5.2.2所示。
4. 完全二叉树的定义
完全二叉树是指这样二叉树，除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
如果对满二叉树从上至下，从左至右地从1开始编号，如图5.2.3所示，如有一棵包含有n个结点的二叉树与这样一棵满二叉树对比，结果是每个结点都可以与满二叉树中编号为1至n的结点一一对应，则称这类二叉树为顺序二叉树，如图5.2.4所示。
8 9 10 11 12 13 14 15 4 5 6 7 2 3 1 图5.2.3 一棵从上至下，从左至右地从1开始编号的满二叉树 1 1 2 3 2 3 4 5 6 7 4 5 6 7 8 9 10 11 12 8 9 12 图5.2.4 一棵完全二叉树 图5.2.5 一棵非完全二叉树
满二叉树一定是完全二叉树，反之不然。 5. 退化二叉树的定义
如果一棵非空的二叉树只有一个叶子，且其余结点均只有一个孩子，则称这棵二叉树为退化的二叉树。如图5.2.8所示。
A 12
B 47 D 52 28 (a) (b) I
图5.2.8 退化的二叉树
二叉树的性质 1) 性质1
k-1
在二叉树的第 k 层上最多有2个结点（k≥1）。
2) 性质2
m
深度为m的二叉树至多有2-1个结点。 可以由性质1推出上述结论。显然，深度为h的二叉树的最大结点应为各层最大结点之和即为：
i?1?h（第i层上的最大结点数）=
i?1?h2=2-1
i-1h
3) 性质3
包括n（n>0）个元素的二叉树的边数为n-1。
证明：二叉树中每个元素（除根结点外）有且仅有一个双亲结点。而孩子结点与双亲结点之间有且仅有一条边，因此包含n个元素的二叉树的边数是n-1。
4) 性质4
对于任何一棵二叉树，若其终端结点数为n0，其度为2的结点数为n2，则有： n0=n2+1。 证明：设二叉树的度为1的结点数为n1，又由于二叉树中所有结点的度数都小于或等于2，所以其结点总数n应为：
n=n0+n1+n2 (5.1)
除根结点外其余结点都有一个枝进入，则二叉树中的分枝总数b为：
b=n-1 (5.2)
又由于度为1的结点发出一个枝，度为2的结点发出两个枝，所以有：
b=n1+2n2 (5.3) 从5.2式和5.3式得到n-1= n1+2n2，整理得
n=2n2+n1+1 (5.4)
由5.1式和5.4式整理后可得n0=n2+1，所以得证。 5) 性质5
若一棵满二叉树有n个结点，则其深度h应为：h=?log2n?+1 6) 性质6
一棵有n个结点的完全二叉树，如从左至右、从上至下的，对每个结点从1开始编号，对于其中任意编号为i的结点（1≤i≤n）有：
(1) 若i?1,则i的父亲是?i/2?；若i=1，则i是根结点，无父亲。 (2) 若2i≤n，则i的左孩子是2i；若2i>n，则i无左孩子。
(3) 若2i+1≤n，则i的右孩子是2i+1；若2i+1>n，则i无右孩子。 ?i/2? 152
i 17 85 i+1
2i 25 2i+1 7 77 2i+2
图5.2.9 顺序二叉树父子关系
1.6.3 二叉树的链式存储结构
由于二叉树的每个结点的最大度数为2，因此，统一给出二叉树的每个结点的模式，不管二叉树中结点的度数为0，为1还是为2，我们定义二叉树中的结点类型，如图5.3.7所示。
指向左孩子指针 结点信息值 指向右孩子指针
图5.3.7 二叉树链式结点结构
如二叉树的某个结点有左右孩子，则左右指针不空，如果二叉树的某个结点只有左或右孩子，则其右或左指针就为空，如果某个结点是叶子结点，则其左右指针都为空。
对于满二叉树或完全二叉树，可以按层序进行顺序存储，节省在存储空间。 1. 二叉树的前序、中序和后序遍历
所谓遍历，是指按一定的规律和秩序访问树中的每一个结点，且仅仅只访问一次，在访问每个结点时，可以修改它的内容，打印信息或做其它的工作。
为此，必须先对二叉树的各个结点按某种规律排序。若我们用L代表左孩子，R代表右孩子，D代表根结点，则二叉树有以下六种排序方法：
DLR（根左右），LDR（左根右），LRD（左右根） DRL（根右左），RDL（右根左），RDL（右根左）
为了简化，我们规定排序只能先左后右, 则只剩下三种排序方法： DLR（根左右），LDR（左根右），LRD（左右根）
如果再以根结点在排序中的位置来称呼这三种排序（遍历）方法，则有， ? DLR（根左右）称为前根排序（前序） ? LDR（左根右）称为中根排序（中序） ? LRD（左右根）称为后根排序（后序）
A 根 B C
D E F G 左子树 右子树 I J 图5.4.1 一棵二叉树
L M 图5.4.2 二叉树递归结构
在讨论二叉树的遍历时，一定要明白二叉树的递归性。遍历时，“根”不是唯一的，整棵二叉树有一个唯一的根，而每个子树（左了树和右子树）也有各自的一个根，即多级子树对应多个“根”；每遍历到某个“根”的孩子时，如果孩子本身又是一棵子树时，又需要将这棵孩子子树按遍历规则重新当作一棵树来遍历。
1) 前根排序（DLR）规则 首先访问二叉树的根结点，然后按前根遍历的规则访问其左子树，如果所有的左子树都已遍历，则按前根遍历的规则遍历右子树。按前根排序的规定，图5.4.1所示二叉树遍历结
果为：ABDIECFJGLM。
按照前序遍历规则：
首先访问根结点，然后遍历左子树，最后遍历右子树。 2) 中根排序（LDR）规则
首先按中根遍历的规则访问二叉树的左子树，如果左子树都已遍历，则访问左子树的根结点，然后，按中根遍历的规则访问二叉树的右子树。图5.4.1所示二叉树中根遍历结果为：DIBEAJFCLGM。
按照中序遍历规则：
首先遍历左子树，然后访问根结点，最后遍历右子树。 3) 后根排序（LRD）规则
首先按后根遍历的规则访问二叉树的左子树，如果左子树都已遍历，则按后根遍历的规则访问二叉树的右子树，然后，访问二叉树的根结点。图5.4.1所示二叉树后根遍历结果为：IDEBJFLMGCA。
按照后序遍历规则：
首先遍历左子树，然后访问根结点，最后遍历右子树。
1.7 查找技术
查找(Searching)是确定在数据元素集合（查找表）中是否存在一个数据元素关键字等于给定值关键字的过程。
查找的过程实际上是将给定值与记录集合中各记录的关键字相比较，从而确定给定值在记录集合中是否存在，以及存在时它在记录集合中的位置。
如果在记录集合中能找到与给定值相等的关键字，此时我们称该查找是成功，否则称该查找是失败的。 1.7.1 顺序查找
顺序查找的方法是，从顺序表的一端开始，用给定值的关键字逐个顺序地与表中各记录的关键字相比较，若在表中找到某个记录的关键字与给定值的关键字值相等，表明查找成功;若找遍了表中的所有记录，也未找到与给定值的关键字值相等的关键字，表明查找失败。当得到查找成功或失败的结论时，查找结束。
可见，顺序查找适用于表中数据元素无序或链表结构的情况。 时间复杂度:O(n/2) 1.7.2 二分法查找
二分查找又称为折半查找（Binary Search），是一种效率较高的有序顺序表上的查找方法。
设置三个变量low，high和mid，它们分别指向表的当前待查范围的下界、上界和中间位置。初始时，令low=1，high=n1，设待查数据元素的关键字为SearchKey。
(l)令mid=[low+hiqh]/2。（[]表示下限取整） (2)比较SearchKey与mid位置的值的大小，
若mid位置的值=SearchKey，则查找成功，结束查找;
若mid位置的值 若mid位置的值>SearchKey，表明关键字为SearchKey的记录只可能存在于记录mid的前半部，修改查找范围，令high=mid-1，变量low的值保持不变。 (3)比较当前变量low与high的值，若low≤high，重复执行第(1)和(2)步，若low>high，表明整个表已查找完毕，表中不存在关键字为SearchKey的记录，查找失败。