自考数据结构重点（珍藏版）

由天下分享时间：2024/12/2 18:43:52 加入收藏我要投稿点赞

更多优质自考资料尽在百度贴吧自考乐园俱乐部

（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

① 一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指

针为空。

② 具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指

针域为空。

带双亲指针的二叉链表: 经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。

二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。

12. 所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：（1）访问结点本身(N)，（2）遍历该结点的左子树(L)，（3）遍历该结点的右子树(R)。以上三种操作有三种执行次序：NLR、LNR、LRN 三种遍历的命名，根据访问结点操作发生位置命名：

① NLR：前序遍历(亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历——访问结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

13. 遍历算法:

1．中序遍历的递归算法定义：(1)遍历左子树； (2)访问根结点； (3)遍历右子树。 2．先序遍历的递归算法定义：(1)访问根结点； (2)遍历左子树； (3)遍历右子树。 3．后序遍历得递归算法定义：(1)遍历左子树； (2)遍历右子树； (3)访问根结点。 14.遍历序列：

遍历二叉树的执行踪迹：三种递归遍历算法的搜索路线相同（如下图虚线所示）。

遍历序列

（1）中序序列：中序遍历二叉树时，对结点的访问次序为中序序列

【例】中序遍历上图所示的二叉树时，得到的中序序列为：D B A E C F

（2）先序序列：先序遍历二叉树时，对结点的访问次序为先序序列

【例】先序遍历上图所示的二叉树时，得到的先序序列为：A B D C E F

（3）后序序列：后序遍历二叉树时，对结点的访问次序为后序序列

【例】后序遍历上图所示的二叉树时，得到的后序序列为：D B E F C A

具体线路为：从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。

在搜索路线中，若访问结点均是第一次经过结点（图中标为1）时进行的，则是前序遍历；若访问结点均是在第二次（图中标为2）(或第三次（图中标为3）)经过结点时进行的，则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。

════════════════════════════════════════════════════════════════════

自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....

俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部

更多优质自考资料尽在百度贴吧自考乐园俱乐部

（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

15.二叉树的建立：建立上图所示二叉树，其输入的先序序列是：ABD∮∮CE∮∮F∮∮。

算法：void CreateBinTree (BinTree *T)

{ //构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身 char ch；

if((ch=getchar())=='') *T=NULL； //读人空格，将相应指针置空 else{ //读人非空格

*T=(BinTNode *)malloc(sizeof(BinTNode))； //生成结点 (*T)->data=ch；

CreateBinTree(&(*T)->lchild)； //构造左子树 CreateBinTree(&(*T)->rchild)； //构造右子树 } }

16.线索二叉树：n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为\线索\）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。线索链表解决了二叉链表找左、右孩子困难的问题，出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题。利用的是n个结点的二叉链表中含有n+1个空指针域，因此可以利用这些空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针。线索链表的结点结构：

其中:ltag和rtag是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。

自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....

俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部

更多优质自考资料尽在百度贴吧自考乐园俱乐部

（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

图中的实线表示指针，虚线表示线索。

结点C的左线索为空，表示C是中序序列的开始结点，无前趋；结点E的右线索为空，表示E是中序序列的终端结点，无后继。

线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。

17.二叉树的线索化: 将二叉树变为线索二叉树的过程称为线索化。按某种次序将二叉树线索化的实质是：按该次序遍历二叉树，在遍历过程中用线索取代空指针。下图中序序列为：C B D A F H G I E

和中序遍历算法一样，递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树，算法的时间复杂度亦为O(n)。 18.

线索二叉树的运算: 查找某结点*p在指定次序下的前趋和后继结点

在中序线索二叉树中，查找结点*p的中序后继结点：

① 若*p的右子树空(即p->rtag为Thread)，则p->rchild为右线索，直接指向*p的中序后继。

② 若*p的右子树非空(即p->rtag为Link)，则*p的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止，该结点是*p的右子树中\最左下\的结点，即*P的中序后继结点。

在中序线索二叉树中，查找结点*p的中序前趋结点:

① 若*p的左子树为空，则p->1child为左线索，直接指向*p的中序前趋结点；

② 若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。该结点是*p的左子树中\最右下\的结点，它是*p的左子树中最后一个中序遍历到的结点，即*p的中序前趋结点。 19.在后序线索二叉树中，查找指定结点*p的后序前趋结点

在后序线索二叉树中，查找指定结点*p的后序前趋结点的具体规律是： ① 若*p的左子树为空，则p->lchild是前趋线索，指示其后序前趋结点。

【例】在下图所示的后序线索二叉树中，H的后序前趋是B，F的后序前趋是C。

② 若*p的左子树非空，则p->lchild不是前趋线索。由于后序遍历时，根是在遍历其左右子树之后被访问的，故*p的后序前趋必是两子树中最后一个遍历结点。当*p的右子树非空时，*p的右孩子必是其后序前趋【例】在上图所示的后序线索二叉树中，A的后序前趋是E；当*p无右子树时，*p的后序前趋必是其左孩子

【例】在上图所示的后序线索二叉树中，E的后序前趋是F

（4）在后序线索二叉树中，查找指定结点*p的后序后继结点

自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....

俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部

更多优质自考资料尽在百度贴吧自考乐园俱乐部

（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

具体的规律：

① 若*p是根，则*p是该二叉树后序遍历过程中最后一个访问到的结点。*p的后序后继为空 ② 若*p是其双亲的右孩子，则*p的后序后继结点就是其双亲结点【例】上图所示的后序线索二叉树中，E的后序后继是A。

③ 若*p是其双亲的左孩子，但*P无右兄弟，*p的后序后继结点是其双亲结点【例】上图所示的后序线索二叉树中，F的后序后继是E。

④ 若*p是其双亲的左孩子，但*p有右兄弟，则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点，它是该子树中\最左下的叶结点\

【例】上图所示的后序线索二叉树中，B的后序后继是双亲A的右子树中最左下的叶结点H 注意：F是孩子树中\最左下\结点，但它不是叶子。

由上述讨论中可知：在后序线索树中，仅从*p出发就能找到其后序前趋结点；要找*p的后序后继结点，仅当*p的右子树为空时，才能直接由*p的右线索p->rchild得到。否则必须知道*p的双亲结点才能找到其后序后继。因此，如果线索二叉树中的结点没有指向其双亲结点的指针，就可能要从根开始进行后序遍历才能找到结点*P的后序后继。由此，线索对查找指定结点的后序后继并无多大帮助。 20. 遍历线索二叉树:

遍历某种次序的线索二叉树，只要从该次序下的开始结点开发，反复找到结点在该次序下的后继，直至终端结点。遍历中序线索二叉树算法：

void TraverseInorderThrTree(BinThrTree p) { //遍历中序线索二叉树 if(p){//树非空

while(p->ltag==Link)

p=p->lchild； //从根往下找最左下结点，即中序序列的开始结点 do{

printf(\％c\，p->data)； //访问结点 p=InorderSuccessor(p)； //找*p的中序后继 }while(p) }//endif

}//TraverselnorderThrTree 分析：

① 中序序列的终端结点的右线索为空，所以do语句的终止条件是p==NULL。

② 该算法的时间复杂性为O(n)。因为是非递归算法，常数因子上小于递归的遍历算法。因此，若对一棵二叉树要经常遍历，或查找结点在指定次序下的前趋和后继，则应采用线索链表作为存储结构为宜。

③ 以上介绍的线索二叉树是一种全线索树（即左右线索均要建立）。许多应用中只要建立左右线索中的一种。 ④ 若在线索链表中增加一个头结点，令头结点的左指针指向根，右指针指向其遍历序列的开始或终端结点会更方便。

21. 将树转换为二叉树：树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然

地就能将树转换成相应的二叉树：①在所有兄弟结点之间加一连线； ②对每个结点，除了保留与其长子的连线外，

去掉该结点与其它孩子的连线。