（3）运算对象中的单变量均为叶子结点 树在计算机中用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域（即指针域）个数将随着树中该结点的度而定义。
如果在树中，每一个结点的子结点的个数不相同，因此在多重链中各结点的链域个数也不相同，会导致算法太复杂。因此，在树中，常采用定长结点来表示树中的每一个结点，即取树的度作为每个结点的链域的个数。这样，管理相对简化了，但会造成空间的浪费，因为有许多的结点存在空链域。 2．二叉树及其基本性质 1）二叉树的定义
二叉树的特点：
? 非空二叉树只有一个根结点
? 每一个结点最多只有两个子结点，且结点分左右。则一个结点最多可以有两棵子树，
分别称为左子树和右子树
在二叉树中，每一个结点的度最大为2，即二叉树的度为2。在二叉树中，任何的子树也均为二叉树。
在二叉树中，每一个结点的子树被分为左子树和右子树。在二叉树中，允许某一个结点只有左子树或只有右子树。如果一个结点既没有左子树，也没有右子树，则该结点为叶子结点。
2）二叉树的性质
性质1：在二叉树的第k层上，最多有2（k≥1）个结点。
m
性质2：深度为m的二叉树最多有2-1个结点。
性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。 性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。
3）满二叉树与完全二叉树
（1）满二叉树 满二叉树的特点：
除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树中，每一层上的结
k-1
点数都达到最大值，即在满二叉树上的第k层上有2个结点。如下即为一棵满二叉树。
A B D H I J E K L F M C G N O k-1
满二叉树
（2）完全二叉树
特点：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干个结点。
即如果从根结点开始，对二叉树的结点自上而下、自左而右用自然数进行连续编号，则
深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应，则是完全二叉树。
对于完全二叉树，叶子结点只能在层次最大的两层中出现；对于任何一个结点，若其右
A B D H P Q R 完全二叉树
C E J K L F M G N O I 分支下的子树结点的最大层次为p，则其分支下的子结点的最大层次为p或p+1。
完全二叉树具有的性质：
性质5：具有n个结点的完全二叉树的深度为[log2n]+1
性质6：设完全二叉树共有n个结点。如果从根结点开始，按层次（每一层从左到右）用自然数1、2??、n给结点编号，对于编号为k（k=1,2,??n）的结点有如下结论：
① 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)。
② 若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（当然也没有右子结点）
③ 若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。 3．二叉树的存储结构
二叉树的存储常采用链式存储结构。
存储二叉树中各元素的存储结点由两个部分组成：数据域和指针域。在二叉树中，由于每个结点可有两个子结点，则它的指针域有两个：一个用于存储该结点的左子结点的存储地址，即称为左指针域；一个用于存储指向该结点的右子结点的存储地址，称为右指针域。
存储结构如下：
Lchild Value Rchild i
L(i) V(i) R(i) 即二叉树的存储结构中每一个存储结点都有两个指针域，因此，二叉树的链式存储结构
也称为二叉树的链表。在二叉树在存储中，用一个头指针指向二叉树的根结点的存储地址。
如图所示的二叉树：
A B D H I J E K L F M C G N O P Q R 如果我们将该二叉树的所有结点顺序编号，顺序存放在存储空间里，则它们在内存空间中的存放方式是：
i L(i) V(i) R(i)
BT?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2 4 6 8 10 12 14 16 18 0 0 0 0 0 0 0 0 0 A B C D E F G H I J K L M N O P Q R 3 5 7 9 11 13 15 17 0 0 0 0 0 0 0 0 0 0 当然，对于满二叉树或完全二叉树而言，也可采用顺序存储的方式，但顺序存储的方式
不适合其他的二叉树。 4．二叉树的遍历
二叉树的遍历即是不重复地访问二叉树的所有结点。
在遍历二叉树时，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，二叉树的遍历又可分为三种：前序遍历、中序遍历和后序遍历。 1）前序遍历
前序遍历即先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。
操作的具体方式：
? 若二叉树为空，则结束返回。
? 否则：访问根结点?前序遍历左子树?前序遍历右子树
如上图所示的完全二叉树，它的前序遍历结果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O 2）中序遍历
中序遍历，即先遍历左子树，然后访问根结点，最后是遍历右子树。 具体的操作方式：
? 若二叉树为空，则结束返回。
? 否则：中序遍历左子树?访问根结点 ?中序遍历右子树
这里强调，在遍历左子树和右子树时，仍然要采用中序遍历的方法。
如上图所示的完全二叉树，它的中序遍历结果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O 3）后序遍历
后序遍历，即选遍历左子树，然后是遍历右子树，最后访问根结点。 具体的操作方式：
? 若二叉树为空，则结束返回。
? 否则：前序遍历左子树?前序遍历右子树?访问根结点
如上图所示的完全二叉树，它的后序遍历结果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A （七）查找技术
查找即是指在一个给定的数据结构中查找某个指定的元素。 1．顺序查找
顺序查找又称顺序搜索。一般是在线性表中查找指定的元素。 基本操作方法是：
从线性表的第一个元素开始，与被查元素进行比较，相等则查找成功，否则继续向后查找。如果所有的元素均查找完毕后都不相等，则该元素在指定的线性表中不存在。
顺序查找的最好情况：要查找的元素在线性表的第一个元素，则查找效率最高；如果要查找的元素在线性表的最后或根本不存在，则查找需要搜索所有的线性表元素，这种情况是最差情况。
对于线性表而言，顺序查找效率很低。但对于以下的线性表，也只能采用顺序查找的方法：
? 线性表为无序表，即表中的元素没有排列不是按大小顺序进行排列的，这类线性表
不管它的存储方式是顺序存储还是链式存储，都只能按顺序查找方式进行查找 ? 即使是有序线性表，如果采用链式存储，也只能采用顺序查找方式
例如，现有线性表：7、2、1、5、9、4，要在序列中查找元素6，查找的过程是： ? 整个线性表的长度为5
? 查找计次n=1，将元素6与序列的第一个7元素进行比较，不等，继续查找 ? n=2，将6与第二个元素2进行比较，不等，继续 ? n=3，将6与第三个元素1进行比较，不等，继续 ? n=4，将6与第四个元素5进行比较，不等，继续 ? n=5，将6与第五个元素9进行比较，不等，继续 ? n=6，将6与第六个元素4进行比较，不等，继续
? n=7，超出线性表的长度，查找结束，则该表中不存在要查找的元素。 2．二分查找
二分查找只适用于顺序存储的有序表。此处所述的有序表是指线性中的元素按值非递减排列（即由小到大，但允许相邻元素值相等）。
二分查找的方法如下：
将要查找的元素与有序序列的中间元素进行比较：
? 如果该元素比中间元素大，则继续在线性表的后半部分（中间项以后的部分）进行
查找
? 如果要查找的元素的值比中间元素的值小，则继续在线性表的前半部分（中间项以
前的部分）进行查找
这个查找过程一直按相同的顺序进行下去，一直到查找成功或子表长度为0（说明线性表中没有要查找的元素）
有序线性表的二分法查找，条件是必须这个有序线性表的存储方式是顺序存储的。它的查找效率比顺序查找要高得多，它的最坏情况的查找次数是log2n次，而顺序查找的最坏情况的查找次数是n次。
当然，二分查找的方法也支持顺序存储的递减序列的线性表。
有非递减有序线性表：1、2、4、5、7、9，要查找元素6。查找的方法是： ? 序列长度为n=6，中间元素的序号m=[(n+1)/2]=3
? 查找计次k=1，将元素6与中间元素即元素4进行比较，不等，6>4
? 查找计次k=2，查找继续在后半部分进行，后半部分子表的长度为3，计算中间元
素的序号：m=3+[(3+1)/2]=5，将元素与后半部分的中间项进行比较，即第5个元素中的7进行比较，不等，6<7 ? 查找计次k=3，继续查找在后半部分序列的前半部分子序列中查找，子表长度为1，
则中间项序号即为m=3+[(1+1)/2]=4，即与第4个元素5进行比较，不相等，继续查找的子表长度为0，则查找结束 （八）排序技术
排序即是将一个无序的序列整理成按值非递减顺序排列的有序序列。在这里，我们讨论的是顺序存储的线性表的排序操作。 1．交换类排序法
交换类排序法，即是借助于数据元素之间的互相交换进行排序的方法。 1）冒泡排序法
冒泡排序法即是利用相邻数据元素之间的交换逐步将线性表变成有序序列的操作方法。 操作过程如下：
? 从表头开始扫描线性表，在扫描过程中逐次比较相邻两个元素的大小，若相邻两个
元素中前一个元素的值比后一个元素的值大，将两个元素位置进行交换，当扫描完成一遍时，则序列中最大的元素被放置到序列的最后。
? 再继续对序列从头进行扫描，这一次扫描的长度是序列长度减1，因为最大的元素
已经就位了，采用与前相同的方法，两两之间进行比较，将次大数移到子序列的末尾。
? 按相同的方法继续扫描，每次扫描的子序列的长度均比上一次减1，直至子序列的