数据结构C语言版复习攻略.docx

第一章：绪论一、基础知识
概念和术语(黑体字局部)。
另外，注意：
1、数据元素是数据的基本单位。P42、数据项是数据不可分割的最小单位。P5
3、数据结构及其形式定义。P5
四种基本结构：①集合②线性结构③树形结构④图(网)状结构4、数据结构的
逻辑结构(抽象的，与实现无关)
物理结构(存储结构) 顺序映像(顺序存储结构)位置“相邻”非顺序映像(链式存储结构)指针表示关系P6
5、数据类型P7
抽象数据类型(ADT) P7
ADT=(数据对象，数据关系，基本操作)
ADT细分为原子类型，固定聚合，可变聚合类型。P86、算法的概念P13
7、算法的五个特征
①有穷性②确定性③可行性④输入(0个或多个)⑤输出(1个或多个)8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量
其中正确性的四个层次(通常要求到达C层)。
9、算法的时间复杂度P15
常见有:0(1), 0(n), 0 (n2), 0(log2n)), 0(n log-2n), 0 (211)
语句频度，用归纳法计算。
10、算法的空间复杂度P17二、算法
起泡排序。P16另一种形式
void BubbleSort ( DataType a[], int n )I
for ( i=0; i<n-l; i++ )
for ( j=0; j<n-i-l; j++ )if ( a[j]>a[j+l])
a[j]<—>a[j+l];)
或void BubbleSort ( DataType a[], int n )
I
for ( i=l; i<n; i++ )
for ( j=0; j<n-i; j++ )if( a[j]>a[j+l])
a[j]<—>a[j+l];)
或 分析算法的时间复杂度时，log2n常简单记作log n

(18)特点
一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链 表。
(19)类型定义
typedef struct DuLNode {
DataType data;
struct DuLNode *prior, *next; } DuLNode, *DuLinkList;
//两个
prior
data -► next
指针

(20)基本形态
空表：用后向指针判断L->next == L,或者用前向指针判断L->prior == L。
非空表。
(21)与单链表和循环链表的联系
最大不同：前驱容易求得，可以向前遍历。
判断表尾的方法与循环链表相同：p二L。
插入和删除时需要修改两个方向的指针。
(22)插入和删除需要修改两个方向的指针。例如：(见下表)
表错误!文档中没有指定样式的文字。.2双向循环链表的插入和删除顺序表与单链表的比拟
P之后插入s
P之前插入s
删除p之后继s
删除P
s->next p->next;
p->next = s; s->prior = p; s->next->prior =s;
s->prior p->prior;
p->prior = s; s->next = p; s->prior->next = s;
s = p->next;
p->next=
s->next;
p->next->prior =
P；
p->prior->next p->next;
p->next->prior=
p->prior;
表错误!文档中没有指定样式的文字。.3顺序表和单链表的比拟
顺序表
单链表
以地址相邻表示关系
用指针表示关系
随机访问，取元素0(1)
顺序访问，取元素0(n)
插入、删除需要移动元素0(n)
插入、删除不用移动元素0(n)(用于查找 位置)
总结：需要反复插入、删除，宜采用链表；反复提取，很少插入、删除，宜采用顺序表。
第三章、栈和队列
栈栈，栈顶，栈底,空栈，后进先出(LIFO),入栈(Push),出栈(Pop)。
顺序栈：栈的顺序存储结构；链栈：栈的链式存储结构。
链栈
存储结构
用不带头结点的单链表实现。
类型定义 同单链表。
基本形态
1°.栈空条件：S == NULL
2°.栈非空
S
A
3。,栈满（一般不出现） 基本算法
4°.入栈 Push (&s, x)bool Push ( LinkList &s, DataType x )
(
//新建结点
p = (LinkList) malloc (sizeof(LNode));
if ( !p ) return false; // 失败
p->data = x;
//插入栈顶
p->next = s;
s = p;
return true;}
5°.出栈 Pop (&s, &x)前提：栈非空。
bool Pop ( LinkList &s, DataType &x )(
if ( s==NULL ) return false; // 栈空 //删除栈顶元素
P = s;
s = s->next;
x = p->data;
free ( p );
return true;)
6°.栈顶元素前提：栈非空。
bool Top ( LinkList &s, DataType &x )
if ( s二二NULL ) return false; // 栈空 x = s->data;
return true;}
顺序栈存储结构
类似于顺序表，插入和删除操作固定于表尾。
类型定义简单说，“数组+长度” ‘0
const int MAXSIZE =栈的最大容量；typedef struct {
DataType elera[MAXSIZE];
int top;} SqStack;
基本形态
7°.栈空条件 s. top == 0;
8°.栈满条件 s. top = MAXSIZE
9°.栈不空、不满基本算法
10°.入栈 Push (&s, x)前提：栈不满
bool Push ( SqStack& s, DataType x ) (
if ( s. top == MAXSIZE ) return false; // 栈满
s. elem[top] = x;// 或者 s. elem[top++]= x;
top++;// 代替这两行
return true;}
11 °•出栈 Pop (&s, &x)前提：栈非空
bool Pop ( SqStack &s, DataType &x ) (
if ( s. top-0 ) return false;
top—;// 可用 x=s. elem[-top];
x = s. elem[top];// 代替这两行
return true;)
7不准确的说法，只为便于理解和记忆，不要在正式场合引用。
12。 .栈顶元素前提：栈非空
5. elem[top-l]即是。
队列队列，队头，队尾，空队列，先进先出（FIFO）。
链队列：队列的链式存储结构。
循环队列：队列的顺序存储结构之一。
链队列存储结构
简而言之，“单链表+尾指针” %类型定义
课本P61otypedef struct {Q.front
LinkList front;八一
..Q.rear J
LinkList rear;} LinkQueue;Q.front ・卜画中 a? | ・卜...->| an |/\
,,Q.rear -基本形态
队列空：Q. front二二Q. rear。
非空队列。
基本算法
13。 .入队列课本P62。插入队尾，注意保持Q. rear指向队尾。
14°.出队列课本P62。删除队头元素，
特别注意：如果队列中只有一个元素，那么队头也同时是队尾，删除队头元素后也需要修改 队尾指针。
循环队列存储结构
简单说，“数组+头、尾位置”工类型定义
const int MAXSIZE =队列最大容量；typedef struct {
DataType elem[MAXSIZE];
int front, rear; //队头、队尾位置} SqQucuc;
8不准确的说法，只为便于理解和记忆，不要在正式场合引用。
9不准确的说法，只为便于理解和记忆，不要在正式场合引用。
基本形态通常少用一个元素区分队列空和队列满，也可以加一标志。约定front指向队头元素的位
置，rear指向队尾的下一个位置，队列内容为［front, rear) o
15。.队列空条件：Q. front == Q. rear。
不能出队列。
16°.队列满条件：(Q. rear+l)%MAXSIZE == Q. front (少用一个元素时)。
不能入队列。
17°.队列不空也不满
18°.加一标志区分队列空和队列满的情况可以用满所有空间。队列空和队列满时都有Q.front=Q.rear,再用标志区分。
队列空：Q. front-Q. rear and Q. tag==0；队列满：Q. front==Q. rear and Q. tag==l 0基本算法
19°.入队列前提：队列不满。
bool EnQueue ( SqQueue &Q, DataType x ) (
if ( (Q. rear+l)%MAXSIZE==Q. front ) return false; // 队列满 //入队列
Q. elem [Q. rear]= x;
Q. rear = (Q. rear+l)%MAXSIZE;
return true;}
20°.出队列前提：队列非空。
bool DeQueue ( SqQueue &Q, DataType &x ) (
if ( Q. front==Q. rear ) return false; // 队列空
//出队列
x = Q. elem [Q. front];
Q. front = (Q. front+l)%MAXSIZE;
return true;
21。.队列中元素个数结论：(Q. rear-Q. front+MAXSTZE) %MAXSTZE<>
注：Q. rcar-Q. front可能小于0,需要加上MAXSIZE。
int QueueLength ( SqQueue Q )
return (Q. rear-Q. front+NfAXSIZE)%MAXSIZE;
22°.用标志区分队列空和满 用标志区分队列空和满时，队列初始化、入队列、出队列和队列长度的算法如下: void InitQueue ( SqQueue &Q ) {
Q. front = Q. rear = 0; Q. tag = 0;}
bool EnQueue ( SqQueue &Q, DataType x ) {
if ( Q. front==Q. rear and Q. tag==l ) return false;
Q. elem[ Q. rear ] = x;
Q. rear = (Q. rear+l)%MAXSIZE;
if ( Q. tag==0 ) Q. tag = 1;// 队列非空
return true;bool DeQueue ( SqQueue &Q, DataType &x ) {
if ( Q. front-Q. rear and Q. tag-0 ) return false;
x = Q. elem[ Q. front ];
Q. front = (Q.front+l)%MAXS!ZE;
if ( Q. front==Q. rear ) Q. tag = 0;// 队列空
return true;)
int QueueLength ( SqQueue Q )
if ( Q. front==Q. rear and Q. tag==l )
return MAXSIZE;// 队列满
else
return (Q. rear-Q. front+MAXSIZE)%MAXS!ZE; // 队列不满(包含队列空的情况) }栈和队列比拟
都是线形结构，栈的操作LIFO （后进先出），队列操作FIFO （先进先出）。
简化的栈和队列结构在算法中使用栈和队列时可以采用简化的形式。
表错误!文档中没有指定样式的文字。.4简化的栈和队列结构简化栈
结构
“S 口 + top”
初始化
top = 0;
入栈
s[top++]= X；

简化栈
结构
“S 口 + top”
初始化
top = 0;
入栈
s[top++]= X；

简化队列
结构
"q口 + front + rear”
初始化
front=rear=0;
入队列
q[rear]二 x;

说明：只要栈（队列）的容量足够大，算法中可以省去检查栈（队列）满的情况。 栈和队列的应用

rear = (rear+1)%MAXSIZE;
出栈
X = s[—top];
出队列
x = q[front];
front = (front+1)%MAXSIZE;
栈顶
s [top-1]
队列头
q[front]
栈空
top == 0
队列空
front == rear

23°.表达式求值 参见课本P53o
24°.括号匹配例：检查表达式中的括号是否正确匹配。如｛ （ ） [ ] ｝正确，（[）]｝那么错误。 分析：每个左括号都“期待”对应的右括号，匹配成功那么可以消去。
思路：遇到左括号那么入栈，遇到右括号那么与栈顶括号相比拟，如果匹配那么消去，否那么匹配失败。当然，如果栈中没有括号可以匹配,

失败。当然，如果栈中没有括号可以匹配,
或者最后栈中还有未匹配的左括号，也都是匹
配错误。
//检查输入的表达式中括号是否匹配
bool MatchBrackets () ( I
const int MAXSIZE = 1024;
char s [MAXSIZE];
int top;
//栈初始化
top = 0;
//检查括号是否匹配
ch = getchar ();
while ( ch!=E0F ) {
switch ( ch ) {
case\ t ,'「：
s [top++] = ch;
break;
case ')’:
if ( top==0 or s [-top]!='(' 左括号失配
case:
if ( top==0 or s [-top][，
case:
if ( top==0 or s [-top]!=, {， )
ch = getchar0;
)
if ( top-0 ) return true;
else return false;

配错误。
//检查输入的表达式中括号是否匹配
bool MatchBrackets () ( I
const int MAXSIZE = 1024;
char s [MAXSIZE];
int top;
//栈初始化
top = 0;
//检查括号是否匹配
ch = getchar ();
while ( ch!=E0F ) {
switch ( ch ) {
case\ t ,'「：
s [top++] = ch;
break;
case ')’:
if ( top==0 or s [-top]!='(' 左括号失配
case:
if ( top==0 or s [-top][，
case:
if ( top==0 or s [-top]!=, {， )
ch = getchar0;
)
if ( top-0 ) return true;
else return false;
//栈的最大容量 //简化的栈结构 //栈顶
//所有左括号入栈
）return false; //栈空或右括号与栈顶
）return false;
）return false;
//取下一个字符
//正好匹配
//栈中尚有未匹配的左括号

25°.递归程序的非递归化将递归程序转化为非递归程序时常使用栈来实现。
26。.作业排队如操作系统中的作业调度中的作业排队，打印机的打印作业也排成队歹
27°.按层次遍历二叉树void LevelOrder ( BinTree bt, VisitFunc visit )
(
const int MAXSIZE=1024;//队列容量(足够大即可)
BinTree q [MAXSIZE]://简化的队列结构
int front, rear; // 队头、队尾
if ( ! bt ) return ;
//初始化队列，根结点入队列
front = rear = 0;
q [rear] = bt;
rear = (rear+1)%MAXSIZE;
〃队列不空，那么取出队头访问并将其左右孩子入队列 while ( front!=rear ) {
p = q [front];
front = (front+l)%MAXSIZE;
if ( P ) {visit ( p->data ); 〃访问结点 q [rear] = p->lchild;
rear = (rear+1)%MAXSIZE;
q [rear] = p->rchild;
rear = (rear+l)%MAXSIZE;}
基础知识和算法

}
基础知识和算法
第四章串

Assign (s, t), Create (s, cs)
Equal (s, t), Length (s)
Concat (s, t)
Substr (s, pos, len) Index (s, t)
Replace (s, t, v)
概念 串，空串，空格串，串的长度；子串，子串在主串中的位置，主串；串相等。 串的基本操作
表错误!文档中没有指定样式的文字。.5串的基本操作Assign(s, t)将变量t赋值给s, Create(s, cs)根据字串创 建变量s。
判断串相等,求串长度。如Length( "")=0。
串连接。如 Concat ( “ab"，“ cd")= " abed”。
取子串，pos为开始位置，len为子串长度。
求子串t在主串s中的位置。如Index(aabcw, ,,ab,,)=bIndex( “a be"，“ be" )二3。
把串s中的字串t替换成Vo如Replace (把aa“，" aaM ,a"）二 " aa\
Delete （s, pos, len） 删除串 s 的一局部。
注：完成习题集。
串的存储结构表错误!文档中没有指定样式的文字。.6串的存储结构
定长顺序串最大长度固定，超过最大长度那么作截断处理堆分配存储表示串的长度几乎没有限制
块链存储表示块内存储空间连续，块间不连续树和二叉树
基础知识和算法树及有关概念
树，根，子树；结点，结点的度，叶子（终端结点），分支结点（非终端结点），内部结点, 树的度；孩子，双亲，兄弟，祖先，子孙，堂兄弟；层次（根所在层为第1层），深度，高 度；有序树，无序树，二叉树是有序树；森林。
二叉树二叉树（二叉树与度为2的树不同，二叉树的度可能是0, 1, 2）；左孩子，右孩子。
二叉树的五种基本形态。
二叉树的性质
28°.二叉树的第i层上至多有2M个结点。
29°.深度为k的二叉树至多有2k-l个结点。
满二叉树：深度为k,有2卜-1个结点。
完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结 点在对应满二叉树中的编号正好是从1到no
30°.叶子结点no,度为2的结点为n2,那么n°=n2+lo考虑结点个数：n = no + ni + n2
考虑分支个数：n-1 = 2n2 + ni可得no = m+1
例：1）二叉树有n个叶子，没有度为1的结点，共有一个结点。2）完全二叉树的第3 层有2个叶子，那么共有一个结点。
分析：1）度为2的结点有n-1个，所以共2nT个结点。2）注意考虑到符合条件的二叉 树的深度可能是3或4,所以有5、10或11个结点。
31°.n个结点的完全二叉树深度为［log。
32。 . n个结点的完全二叉树，结点按层次编号有：i的双亲是如果i=1时为根（无双亲）；
i的左孩子是2i,如果2i>n,那么无左孩子；
i的右孩子是2i + 1,如果2i + Dn那么无右孩子。
二叉树的存储结构
33。 .顺序存储结构用数组、编号i的结点存放在［iT］处。适合于存储完全二叉树。
10本书中约定根结点在第1层，也有约定根在第o层的，那么计算公式会有所不同。
34°.链式存储结构二叉链表：
typedef struct BTNode {
DataType data;
struct BTNode *lchild, *rchild;)BTNode, *BinTree;
三叉链表：
typedef struct BTNode {
DataType data;
struct BTNode *lchild, *rchild, *parent;} BTNode, *BinTree;
Ichild
data
rchild

Ichild
data
parent
rchild

例：用二叉链表存储n个结点的二叉树(n>0),共有(3)个空指针域；采用三叉链表存储, 共有(立)个空指针域。答案：(a) n+1 (b) n+2.提示：只有根结点没有双亲。
2这里太简炼了，只是为了便于记忆。
3不准确的说法，只为便「理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。

二叉树而五种基本形态
①空树：bt=NULL ②左右子树均空：bt->lchild==NULL and bt->rchild==NULL
③右子树为空：bt->rchild==NULL ④左子树为空：bt->lchild==NULL⑤左右子树均非空。
前两种常作为递归结束条件，后三者常需要递归。
遍历二叉树
35°.常见有四种遍历方式按层次遍历，先序遍历，中序遍历，后序遍历。
按层次遍历：“从上至下，从左至右“，利用队列。
先序遍历:DLR；中序遍历：LDR；后序遍历LRD。
例：写出a+b*(c-d)-e/f的前缀、中缀和后缀表达式。
画出二叉树，分别进行前序、中序、后序遍历即可得到。
前缀表达式：- + a*b-cd/ef 中缀表达式：a + b*c-d-e / f 后缀表达式：abcd-* + ef/-
36°.先序遍历算法void Preorder ( BinTree bt ) (
if ( bt ) {
visit ( bt.->data );void BubbleSort ( DataType a[], int n ) {
for ( i=0; i<n-l; i++ ) {
change = fasle;
for ( j=0; j<n-i-l; j++ )
if ( a[j]>a[j+l] ) {a[j]<—>a[j+l];
change = true;
)
if ( !change ) break;
}}
说明：
a)考试中要求写算法时，可用类C,也可用C程序。
b)尽量书写算法说明，言简意赅。
c)技巧：用“边界值验证法”检查下标越界错误。
如上第一个：第二个循环条件假设写作j<n-i,那么当i=0时a[j+l]会越界。
d)时间复杂度为。(产)，第3个在最好情况下(待排记录有序)，时间复杂度为0(n)。
第二章、线性表一、基础知识和算法
1、线性表及其特点线性表是n个数据元素的有限序列。
线性结构的特点：①“第一个”②“最后一个”③前驱④后继。22、顺序表一线性表的顺序存储结构
(1)特点：a)逻辑.上相邻的元素在物理位置上相邻。b)随机访问。
(2)类型定义简而言之，“数组+长度”)
const int MAXSIZE =线性表最大长度；typedef struct {
DataType elem[MAXSIZE];
int length;} SqList;
注：a) SqList为类型名，可换用其他写法。
b) DataType是数据元素的类型，根据需要确定。
c) MAXSIZE根据需要确定。如const int MAXSIZE=64;
d)课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以
e)课本上的SqList类型定义中listsize表示己经分配的空间大小(容纳数据元素的个数)。当插入元素而遇到 L. length=二L. 1 istsize 时，用 realloc (L. elem, L. listsize+增
Preorder ( bt->lchild );
Preorder ( bt->rchiId );
}}
37°.中序遍历算法void Inorder ( BinTree bt )
(
if ( bt ) {
Inorder ( bt->lchild );
visit ( bt->data );
Inorder ( bt->rchild );
)}
38°.后序遍历void Postorder ( BinTree bt )
(
if ( bt ) {
Postorder ( bt->lchild );
Postorder ( bt->rchild );
visit ( bt-〉data );
))
39°.按层次遍历思路：利用一个队列，首先将根(头指针)入队列，以后假设队列不空那么取队头元素p,如果 P不空，那么访问之，然后将其左右子树入队列，如此循环直到队列为空。
void LcvelOrdcr ( BinTree bt )(
//队列初始化为空
InitQueue ( Q );
//根入队列
EnQueue ( Q, bt );
//队列不空那么继续遍历
while ( ! QueueEmpty(Q) ) {
DeQueue ( Q, p );
if ( p!=NULL ) {
visit ( p->data );
//左、右子树入队列
EnQueue ( Q, p->lchild );
EnQueue ( Q, p->rchild );
)
)) 假设队列表示为“数组q[] +头尾front, rear"有: void LevelOrder ( BinTree bt ) (
const int MAXSIZE = 1024;
BinTree q[MAXSIZE]; int front, rear; //队列初始化为空 front = rear = 0;
//根入队列
qfrear] = bt; rear = ( rear+1 ) % MAXSIZE;
//队列不空那么循环
while ( front != rear ) {
p = q[front]; front = ( front+1 ) % MAXSIZE;
if ( p ) {
visit ( p->data );
//左、右子树入队列
q[rear] = p->lchild; rear = ( rear+1 ) % MAXSIZE;
q[rcar] = p->rchild; rear = ( rcar+1 ) % MAXSIZE;
)
)}
40°.非递归遍历二叉树一般借助栈实现。设想一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。 (a)中序非递归遍历
指针P从根开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访 问结点，然后移动到右子树上去。
void InOrder ( BinTree bt, VisitFunc visit ) (
InitStack ( S );
p = bt;while ( p | ! StackEmpty(S) ) { if ( P ) (
Push ( S, p ); p = p->lchild;
} else {
Pop ( S, p );
visit ( p ) ;//中序访问结点的位置
p = p->rchild;
)
)}
(b)先序非递归遍历按照中序遍历的顺序，将访问结点的位置放在第一次指向该结点时。
void Preorder ( BinTree bt, VisitFunc visit )
InitStack ( S );
p = bt;
while ( p | ! StackEmpty(S) ) {
if ( P ) {
visit ( p );//先序访问结点的位置
Push ( S, p ); p = p->lchild; } else {Pop ( S, p ); p = p->rchild;
)
))
或者，由于访问过的结点便可以弃之不用，只要能访问其左右子树即可，写出如下算法。 void Preorder ( BinTree bt, VisitFunc visit ) (
InitStack ( S );
Push ( S, bt );
while ( ! StackEmpty(S) ) {
Pop ( S, p );if ( P ) ( visit ( p );
Push ( S, p->rchild );//先进栈，后访问，所以
Push ( S, p->lchild );// 这里先让右子树进栈
) ))
(c)后序非递归遍历后序遍历时，分别从左子树和右子树共两次返同根结点，只有从右子树返回时才访问根结 点，所以增加一个栈标记到达结点的次序。
void PostOrder ( BinTree bt, VisitFunc visit ) (
InitStack ( S ), InitStack ( tag );
p = bt;while ( p | ! StackEmpty(S) ) { if ( P ) {
Push ( S, p ), Push ( tag, 1) ;// 第一次入栈
p = p->lchild;
} else {
Pop ( S, p ), Pop ( tag, f );
if ( f==l ) {//从左子树返回，二次入栈，然后p转右子树
Push ( S, p ), Push ( tag, 2 ); p = p->rchild;
} else {//从右子树返回(二次出栈)，访问根结点，P转上层
visit ( p );P=NULL;//必须的，使下一步继续退栈
)
)
))
注：后序非递归遍历的过程中，栈中保存的是当前结点的所有祖先。这是和先序及中序遍 历不同的。在某些和祖先有关的算法中，此算法很有价值。
41°.三叉链表的遍历算法下面以中序遍历为例。
//中序遍历三叉链表存储的二叉树 void Inorder ( BinTree bt, VisitFunc visit )(
if ( bt==NULL ) return; //空树，以下考虑非空树
//找到遍历的起点
p = bt;// Note: p!二null here
while ( p->lchild ) p = p->lchild;
//开始遍历
while ( p ) {
//访问结点
visit ( p );
// p转下一个结点
if ( p->rchild ) {//右子树不空，下一个在右子树
p = p->rchild;
while ( p->lchild ) p = p->lchild; //转右子树的最左下结点
} else {//右子树为空，下一个在上层
f = p->parent;while ( p == f->rchild ) { // 假设p是右子树那么一直上溯 p = f; f = f->parent;
)
)
)} 遍历二叉树的应用
42。.写出遍历序列(前、中、后序)
43°.根据遍历序列画出二叉树(a)前序和中序序列，唯一确定二叉树。
例：前序：ABDEGCFH,中序：DBGEAFHC,画出二叉树。
分析：前序序列的第一个是根，这是解题的突破口。
步骤：①前序序列的第一个是根 ②在中序序列中标出根，分成左右子树 ③在前序序列中 标出左右子树(根据结点个数即可)④分别对左右子树的前序和中序序列重复以上步骤直 至完成。
(b)后序和中序序列，唯一确定二又树。
例：后序：DGEBHFCA,中序：DBGEAI1IC,画出二叉树。
分析：后序序列的最后一个是根，这是解题的突破口。
步骤：①后序序列的最后一个是根②在中序序列中标出根，分成左右子树③在后序序列 中标出左右子树(根据结点个数即可)④分别对左右子树的后序和中序序列重复以上步骤 直至完成。
(c)前序和后序序列，不存在度为1的结点时能唯一确定二叉树。
例：前序：ABDEC,后序：DEBCA,画出二叉树。又前序AB,后序BA那么不能唯一确定二叉树。 注：对于不存在度为1的结点的二叉树，首先确定根结点，然后总可以将其余结点序列划 分成左右子树，以此类推即可确定二叉树。
说明：画出二叉树后可以进行遍历以便验证。
440.编写算法思路：按五种形态(①一⑤)分析，适度简化。
例：求二叉树结点的个数。
分析：①0；②1；③L+1;④1+R;⑤1+L+Ro简化:②1+L=o+R=o③1+L+Rr④1+L=o+R⑤1+L+R可合并成⑤一种情况。
int NodeCount ( BinTree bt )(
if ( bt==O ) return 0;
else return 1 + NodeCount(bt->lchild) + NodeCount(bt->rchild);)
例：求二叉树叶子结点的个数。
分析：①0；②1；③L；④R;⑤L+R。简化：③④⑤可合并成⑤。
int LeafCount ( BinTree bt )(
if ( bt=0 ) return 0;
else if ( bt->lchild==0 and bt->rchild==0 ) return 1;
else return LeafCount (bt->lchiId) + LeafCount (bt->rchiId);}
例：求二叉树的深度。
分析：①0；②1；③1+L;④1+R;⑤l+max(L,R)。简化：②③④⑤可合并成⑤。
int Depth ( BinTree bt )(
if ( bt==O ) return 0;
else return 1 + max(Depth(bt->lchild), Depth(bt->rchild));)
线索二叉树
45°.线索n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需 附加一个标志，区分是子树还是线索。
Ichild
Itag
data
rtag
rchild
K 0/1071
Ichild有左子树，那么指向左子树，标志Itag == 0；没有左子树，可作为前驱线索，标志Itag二二10
rchild有右子树，那么指向右子树,标志rtag == 0；没有右子树，可作为后继线索，标志rtag = lo
46°.线索化二叉树利用空指H作为线索指向前驱或后继。左边空指针可以作为前驱线索，右边空指针可以作 为后继线索，可以全线索化或局部线索化。
表错误!文档中没有指定样式的文字。.7线索化二叉树的类型前驱、后继线索