数据结构篇_编程思想板块_第四章串的模式匹配

• 编程思想板块最主要的内容是数据结构经典题目及解答题目所需的编程思想，愿对您能有所帮助

四、 树

1）二叉树的遍历

1. 中序遍历（前序的栈用来保存右子树的地址）：

①　沿着根的左孩子，依次入栈，直到左孩子为空

②　栈顶元素出栈并访问，若其右孩子为空，继续执行

③　若其右孩子不空，将右子树转执行①

1. 后序遍历：

①　从根节点开始，将其入栈，后沿着左子树一直往下搜索到没有左孩子的结点

②　再对其右结点一直往下入栈，直至前述操作进行不下去

③　综上所述，若栈顶元素想出栈访问，要么右子数为空，要么右子数刚被访问完（此时左子树早被访问完了），这样就保证了正确的访问顺序

④　实际上，访问一个结点时，栈中结点恰好是该结点的所有祖先，从栈底到栈顶结点再加上该结点，刚好构成从根节点到该结点的一条路径。如在”求根到某结点的路径“、”求两个结点的最近公共祖先“等算法设计都可以用这一思想

1. 层次遍历：

①　先将根结点入队，然后出队，访问出队结点

②　若其有左子树，则将左子树根节点入队，若其有右子树，则将右子树根节点入队

③　重复①②操作，直至队列为空

2）二叉线索树

1. 建立双向线索链表：

①　添加一个头结点，令其lchild域指针指向二叉树根结点，其rchild域指针指向中序遍历时访问的最后一个结点

②　令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域指针均指向头结点

1. 先序线索二叉树找前驱/后序线索二叉树找后继需知双亲时可设置为三叉链表（增加一个指针回指向双亲）

2. 先序线索化中，注意容易出现爱的魔力转圈圈的问题（设立两个指针，当P指针一直线索化左子树线索至左子树为空的结点z后此时pre指针指向z结点的双亲结点x，此时应把z结点的前驱线索为x，即把z左指针指向x，当处理完结点后我们依照代码会继续遍历z的左子树，但此时z的左指针已经指向了x，故往回走了。处理方法为加一个if(z->ltag==0)这种情况下才可以继续遍历左子树）

3. 后序线索二叉树（其遍历仍需要栈的支持）找结点后继分三种情况：

①　若结点为根，则后继为空

②　若结点是其双亲的右孩子/其双亲的左孩子且其双亲没有右子树，则其后继为双亲

③　若结点是其双亲的左孩子且其双亲有右子树，则其后继为双亲的右子树上按后序遍历出的第一个结点

3）二叉排序树

1. 删除操作：

①　若被删除的结点是叶子结点，则直接删除

②　若被删除结点z有一棵左子树/右子树，则让z的子树成为z父结点的子树，替代z的位置

③　若被删除结点z有左、右两棵子树，则令z的直接后继（或直接前驱（左子树中最大的值（最右下的结点，因为中序遍历二叉排序树可得到一个递增的序列，故左子树中最右下的结点为最小的结点）））替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换为①/②种情况

4）哈夫曼编码（尤其重要）

1. 构成哈夫曼树后：

①　编码需从叶子结点出发走一条从叶子到根的路径

(1) 因为如果从根开始编码,由于叶子不唯一,那么走的时候向左走或者向右走也就无法不确定,处理起来不容易;而如果是从叶子到根，那么每次如果是左孩子就编码为0,右孩子就编码为1,最后逆序输出即可

②　译码需要从根出发走一条从根到叶于的路径

(1) 此时对于每个结点而言,需要是每个结点的权值(这个是必须知道的,因为在建造哈夫曼树时总是选取两个权值小的)、双亲(在编码时需要根据双亲来判断是左孩子还是右孩子)、左孩子、右孩子(左右孩子也是必须的,不然咋构成一棵树,而且还得用于判断左右孩子…)和结点的信息(也是必须的)

5）树堆的删除和插入

1. 删除：分三种情况：

①　若为叶子结点直接删除

②　若为分支结点则比较左儿子和右儿子优先级，把小的那一个旋转上去把要删除的结点旋转下来

③　重复②直到删除结点成为叶子结点为止，后直接删除即可

1. 插入：插入结点首先在最右下角，然后依次旋转上去直到满足小/大根堆性质

6）答题（画图）格式

7）二叉树经典题目的编程思想

1. 已知一棵二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个结点的最近的公共祖先结点的值。

算法思想：

2. 编写后序遍历二叉树的非递归算法

代码：

3. 假设二叉树采用二叉链表存储结构，设计一一个非递归算法求二叉树的高度

算法思想：

采用层次遍历的算法，设置变量level记录当前结点所在的层数，设置变量last指向当前层的最右结点，每次层次遍历出队时与last指针比较，若两者相等，则层数加1,并让last

指向下一层的最右结点，直到遍历完成。level的值即为二叉树的高度（求某层的结点个数、每层的结点个数（具体代码在平板浏览器收藏）、树的最大宽度等，都采用与此题类似的思想）

4. 设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组Al..n]和11..n]中，试编写算法建立该二叉树的二叉链表

算法思想：

由先序序列和中序序列可以唯一确定一棵二叉树。 算法的实现步骤如下

①　根据先序序列确定树的根结点

②　根据根结点在中序序列中划分出二叉树的左、右子树包含哪些结点，然后根据左、右子树结点在先序序列中的次序确定子树的根结点，即回到步骤1)

③　如此重复上述步骤，直到每棵子树仅有一一个结点 (该子树的根结点)为止

5. 二叉树按二叉链表形式存储，写-一个判别给定二叉树是否是完全二叉树的算法

算法思想：

采用层次遍历算法，将所有结点加入队列(包括空结点)。遇到空结点时，查看其后是否有非空结点。若有，则二叉树不是完全二叉树，即判断是否为右！=NULL&&左==NULL，即判断下一个结点是否为空

6. 已知二叉树以二叉链表存储，编写算法完成:对于树中每个元素值为x的结点，删去以它为根的子树，并释放相应的空间

算法思想：

①　删除以元素值x为根的子树，只要能删除其左、右子树，就可以释放值为x的根结点，因此宜采用后序遍历

②　删除值为x的结点，意味着应将其父结点的左(右)子女指针置空，用层次遍历易于找到某结点的父结点。本题要求删除树中每个元素值为x的结点的子树，因此要遍历完整棵二叉树

7. 在二叉树中查找值为x的结点，试编写算法(用C语言)打印值为x的结点的所有祖先，假设值为x的结点不多于一个

算法思想：

采用非递归后序遍历，最后访问根结点，访问到值为x的结点时，栈中所有元素均为该结点的祖先，依次出栈打印即可

8. 设一棵二叉树的结点结构为(LLINK, INFO, RLINK)，ROOT为指向该二叉树根结点的指针，P和q分别为指向该二叉树中任意两个结点的指针，试编写算法ANCESTOR (ROOT,P,q,r),找到p和q的最近公共祖先结点r

算法思想：

后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。本题要找p和q的最近公共

祖先结点r,不失一般性，设p在q的左边。算法思想:采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。后序遍历必然先遍历到结点p,栈中元素均为P的祖先。先将栈复制到另-辅助栈中。继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配(即相等)的元素就是结点p和q的最近公共祖先。

9. 假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树b的宽度(即具有结点数最多的那一层的结点个数)

算法思想：

采用层次遍历的方法求出所有结点的层次，并将所有结点和对应的层次放在一一个队列中。 然后通过扫描队列求出各层的结点总数，最大的层结点总数即为二叉树的宽度

注：本题队列中的结点，在出队后仍需要保留在队列中，以便求二叉树的宽度，所以设置

的队列采用非环形队列，否则在出队后可能被其他结点覆盖，无法再求二叉树的宽度

10. 设有一棵满二叉树(所有结点值均不同)，已知其先序序列为pre,设计一个算法求其后序序列post

算法思想：

11. 试设计判断两棵二叉树是否相似的算法。所谓二叉树T和T2相似，指的是T和T2都是空的二叉树或都只有一一个根结点;或T的左子树和T2的左子树是相似的，且T的右子树和T2的右子树是相似的

算法思想：

12. 写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法

算法思想：

在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点p左、右子女均无，设其中序左线索指向某祖先结点f (p是f右子树中按中序遍历的第一个结点)，若f有左子女，则其左子女是结点P在后序下的前驱;若f无左子女，则顺其前驱找双亲的双亲，一直找到双亲有左子女(这时左子女是P的前驱)。还有一种情况，若p是中序遍历的第一个结点，则结点p在中序和后序下均无前驱

13. 请设计-一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出

算法思想：

表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策

略得到所需的表达式。表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，.需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层(对应根结点)和操作数(对应叶结点)不需要添加括号。

故将二叉树的中序遍历递归算法稍加改造即可得本题的答案。除根结点和叶结点外，遍历到其他结点时在遍历其左子树之前加上左括号，遍历完右子树后加上右括号即可

14. 已知一棵树的层次序列及每个结点的度，编写算法构造此树的孩子-兄弟链表

算法思想：

本题与树的层次序列有关。可设立一个辅助数组pointer[]存储新建树的各结点的地址，再根据层次序列与每个结点的度，逐个链接结点

15. 试编写一个算法,判断给定的二叉树是否是二叉排序树（经典）

算法思想：

对二叉排序树来说，其中序遍历序列为-一个递增有序序列。因此，对给定的二叉树进行中序谝历.若始终能保持前一一个值比后一个值小，则说明该二叉树是一棵二叉排序树

16. 利用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法（经典）

算法思想：

设置二叉树的平衡标记balance,标记返回二叉树bt是否为平衡二叉树，若为平衡二叉树，

则返回1,否则返回0; h为二叉树bt的高度。采用后序遍历的递归算法:

①　若bt为空，则高度为0, balance=l

②　若bt仅有根结点，则高度为1, balance=1.

③　否则，对bt的左、右子树执行递归运算，返回左、右子树的高度和平衡标记，bt的高度为最高子树的高度加1。若左、右子树的高度差大于1,则balance=0;若左、右子

树的高度差小于等于1,且左、右子树都平衡时，balance=1, 否则balance=0

17. 设计一个算法，从大到小输出二叉排序树中所有值不小于k的关键字（记代码）

算法思想：

由二叉排序树的性质可知，右子树中所有的结点值均大于根结点值，左子树中所有的结点值

均小于根结点值。为了从大到小输出，先遍历右子树，再访问根结点，后遍历左子树

18. 编写一个递归算法，在一棵有n个结点的、随机建立起来的二叉排序树上查找第k(1≤k≤n)小的元案，并返回指向该结点的指针。要求算法的平均时间复杂度为O(log2n).二叉排序树的每个结点中除data, lchild, rchild等数据成员外，增加一个count成员，保存以该结点为根的子树上的结点个数

算法思想：

设二叉排序树的根结点为*t，根据结点存储的信息，有以下几种情况:

①　t->lchild 为空时，情况如下:

（1) 若t->rchild非空且k==1, 则*t即为第k小的元素，查找成功

（2) 若t->rchild非空且k!=1,则第k小的元素必在*t的右子树

②　若t->lchild非空时，情况如下:

（1) t->lchild->count==k-1, *t即为第k小的元素，查找成功

（2) t->lchild->count>k-1, 第k小的元素必在t的左子树，继续到t的左子树中查找

（3) t->lchild->count<k-1,第k小的元素必在右子树，继续搜索右子树，寻找第k-(t->1child-> count+1) 小的元素

对左右子树的搜索采用相同的规则，递归实现

19. 设有6个有序表A,B,C,D,E,F,分别含有10, 35, 40, 50, 60和200个数据元素，各表中的元素按升序排列。要求通过5次两两合并，将6个表最终合并为1个升序表，并使最坏情况下比较的总次数达到最小。根据你的合并过程，描述n (n≥2)个不等长升序表的合并策咯，并说明理由

各表的合并策略是：

对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借助于哈夫曼树的构造思想，依次选择最短的两个表进行合并，此时可以获得最坏情况下的最佳合并效率

20. 若任意一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集(字符个数>=2)的不等长编码，每个字符的编码均为二进制的0、1 序列，最长为L位，且具有前缀特性。请回答下列问题:

1)基于你所设计的数据结构，简述从0/1串到字符串的译码过程

2)简述判定某字符集的不等长编码是否具有前缀特性的过程

答：

1)从左至右依次扫描0/1串中的各位。从根开始，根据串中当前位沿当前结点的左子指针或

右子指针下移，直到移动到叶结点时为止。输出叶结点中保存的字符。然后从根开始重复这个过程，直到扫描到0/1串结束，译码完成

1. 二叉树既可用于保存各字符的编码，又可用于检测编码是否具有前缀特性。判定编码是

否具有前缀特性的过程，也是构建二叉树的过程。初始时，二叉树中仅含有根结点，其左子指针和右子指针均为空。

依次读入每个编码C，建立/寻找从根开始对应于该编码的一条路径，过程如下:

①　对每个编码，从左至右扫描C的各位，根据C的当前位(0或1)沿结点的指针(左子指针或右子指针)向下移动。当遇到空指针时，创建新结点，让空指针指向该新结点并继续移动。沿指针移动的过程中，可能遇到三种情况:

(1) 若遇到了叶结点(非根),则表明不具有前缀特性，返回

(2) 若在处理C的所有位的过程中，均没有创建新结点，则表明不具有前缀特性，返回

(3) 若在处理C的最后一个编码位时创建了新结点，则继续验证下一个编码

(4) 若所有编码均通过验证，则编码具有前缀特性

8）树

1.

2. （学会这样推公式以及如何书写步骤)

9）哈弗曼树

1. 设哈夫曼树中共有 99 个结点，则该树中有 ____ 个叶子结点；若采用二叉链表作为存储结构，则该树中有___个空指针域

①　对于不同表示法下的空指针域个数：孩子兄弟表示法和双孩子表示法其实空指针域数都是叶子结点数的两倍，但是不同的是双孩子表示法的空指针域都是叶子结点的，而孩子兄弟表示法的空指针域一部分是叶子结点的，另一部分是其他右孩子结点的空指针域

②　本题解释：哈夫曼树是指带权路径最小的二叉树 它的非叶子结点只是权重的值 并无其他 它真正有存储意义的应该只是那些个叶子结点 所以哈夫曼树转二叉链表的话应该只是用叶子结点来构建二叉链表 所以存在51个空指针域