二叉树与线性表概念

线性表

一、建立单链表

假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘\n’为输入结束标记。动态地建立单链表的常用方法有如下两种：

1、头插法建表

该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。

2、尾插法建表

头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

• 如果我们在链表的开始结点之前附加一个结点，并称它为头结点(dummy head node)，那么会带来以下两个优点：

a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；

b、无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。

二、查找运算

1、按序号查找

在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。

设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，

2、按值查找

按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。

三、插入运算

插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai

之间

的逻辑关系的变化。

四、删除运算

线性表实现方法的比较

• 实现不同

– 顺序表方法简单，各种高级语言中都有数组类型，容易实现；链表的操作是

基于指针的，相对来讲复杂些。

• 存储空间的占用和分配不同

– 从存储的角度考虑，顺序表的存储空间是静态分配的，在程序执行之前必须

明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大

造成浪费，过小造成溢出。而链表是动态分配存储空间的，不用事先估计存

储规模。可见对线性表的长度或存储规模难以估计时，采用链表。

• 线性表运算的实现不同

– 按序号访问数据元素，使用顺序表优于链表。

– 插入删除操作，使用链表优于顺序表。

双向链表(Doubly Linked Lists):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。

和单链表(Single Linked Lists)类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。

设指针p指向某一结点，则双向链表结构的对称性可用下式描述：

(p—>prior)—>next=p=(p—>next)—>prior

即结点*p的存储位置既存放在其前趋结点*(p—>prior)的直接后继指针域中，也存放在它的后继结点*(p—>next)的直接前趋指针域中。

双向链表的删除

双向链表的插入

静态链表与动态链表

静态链表的操作和动态链表相似，只是以整型游标代替动态指针。设以Sa表示静态链表，通常可把Sa[0]理解为“头结点”，第1个元素的位置由Sa[0].next指出,用全局整型变量av指出可利用空间的下标。

初始时将整个静态链表看作一个“空表”，操作中用GetNode()和FreeNode()函数模拟C中的malloc()和free()函数。

堆栈和队列

栈是后进先出（LIFO后进先出）列表，即有序列表中插入和删除在上面进行。

对象：一个具有零或多个元素的有限有序列表。

-操作数的顺序是中序和后序相同。

-运算符优先级较高的出现在优先级较低的前面。

〖Example〗An infix中序 expression: ab c d e

A prefix先序 expression: ab c d e

A postfix后续 expression: a b c d e 

〖Example〗 6 2  3  4 2  = 8

〖Example〗a b c d = a b c * + d –

〖Example〗 a  ( b  c ) d = a b c + * d /

观察时发现不是在堆栈，它的优先级是最高的；但当它在栈中，它的优先级是最低的。定义在栈中的优先级和对符号的优先顺序，并且每一次使用相应的优先级进行比较。 Note: a – b – c将被转换为b –c –.然而, 2^2^3 (

不是 2 2 ^ 3 ^由于幂自右向左联系。

223)必须转换为2 2 3 ^^, 而

队列是先进先出（FIFO）列表，即有序列表中插入发生在一端而删除发生在另一端。 对象：一个具有零或多个元素的有限有序列表。

完全二叉树(Complete Binary Tree)

1、若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

2、完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

3、一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

在树中，该节点的子女的个数称为节点的度。