后序遍历的非递归算法doc.docx
- 文档编号:16707012
- 上传时间:2023-07-16
- 格式:DOCX
- 页数:23
- 大小:200.10KB
后序遍历的非递归算法doc.docx
《后序遍历的非递归算法doc.docx》由会员分享,可在线阅读,更多相关《后序遍历的非递归算法doc.docx(23页珍藏版)》请在冰点文库上搜索。
后序遍历的非递归算法doc
第六章树二叉树
后序遍历的非递归算法。
在对二叉树进行后序遍历的过程中,当指针p指向某一个结点时,不能马上对它进行访问,而要先遍历它的左子树,因而要将此结点的地址进栈保存。
当其左子树遍历完毕之后,再次搜索到该结点时(该结点的地址通过退栈得到),还不能对它进行访问,还需要遍
历它的右子树,所以,再一次将此结点的地址进栈保存。
为了区别同一结点的两次进栈,引入一个标志变量nae,有0表示该结点暂不访问1表示该结点可以访问
标志flag的值随同进栈结点的地址一起进栈和出栈。
因此,算法中设置两个空间足够的堆栈,其中,STACKlCM]存放进栈结点的地址,STACK2[M]存放相应的标志n昭的值,两个堆栈使用同一栈顶指针top,top的初值为—1。
具体算法如下:
#defineH100/•定义二叉树中结点最大数目。
/
voidPOSTOiRDER(BTREET)
{
/*T为二叉树根结点所在链结点的地址。
/
BTREESTACKl[H],p=T;intSTACK2[M],flag,top=—1;if(T!
=NULL)
d0{
while(p!
=NULL){
STACK/[++top]=p;/•当前p所指结点的地址进栈•/
STACK2[top]=0;/,标志0进栈•/
p=p->lchild;/•将p移到其左孩子结点x/
}
p=STACKl[top);flag=STACK2[top--];if(flag==0){STACKl[++top]=p;/,当前p所指结点的地址进栈。
/
STACK2[toP]=1;/•标志1进栈•/
p=p->rchild;/x将p移到其右孩子结点o/
}
else{
VISIT(p);/x访问当前p所指的结点x/
p=NULL;
}
}while(p!
=NULLtttop!
=-1);
}不难分析,上述算法的时间复杂度同样为O(n)
7.6.3二叉树的线索化算法
对--X树的线索化,就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程,因此,二叉树的线索化过程只能
在对二叉树的遍历过程中进行。
下面给出二叉树的中序线索化的递归算法。
算法中设有指针pre,用来指向中序遍历过
程中当前访问的结点的直接前驱结点,pre的初值为头结点的指针;T初始时指向头结点,
但在算法执行过程中,T总是指向当前访问的结点。
voldlNTHREAD(TBTREET){
TBTREEpre;
if(T!
=Null){
INTHREAD(T—>lchild);
if(T—>rchild==NULL)
T—>rbit=O;
if(T—>lchild==NUll);
T—>lchild=pre;
T—>lbit=0;
}
if(pre—>rbitc==0)
pre—>rchild=T;
pre=T;
inthread(T->rchild);
}}
平均查找长度(AverageSearchLength):
确定一个元素在树中的位置所需要进行的比较次数的期望值。
二叉树的内路径长度(InternalPathLength):
从二叉树根结点到某结点所经过的分支数目定义为该结点的路径长度。
二叉树中所有结点的路径长度之和定义为该二叉树的内路径长度IPL。
图7。
25(h)给出
的二叉排序树的内路径长度为
IPL:
1X2+2X2+3X1+4X2=17
二叉树的外路径长度(ExternalPathLength):
为了分析查找失败时的查找长度,在二叉树
中出现空子树时,增加新的空叶结点来代表这些空子树,从而得到一棵扩充后的二叉树。
为
了与扩充前的二叉树相区别,这些新增添的空的叶结点用小方块代表,称之为外部结点,树
中原有的结点为内部结点。
图7.27给出了一棵扩充后的二叉树,其外路径长度EPL是二叉树中所有外部结点的
路径长度之和,即
习题
7.1判断题(在你认为正确的题后的括号中打",否则打X)。
(1)在树型结构中,每一个结点最多只有一个前驱结点,但可以有多个后继结点。
()
(2)在树型结构中,每—个结点不能没有前驱结点。
()
(3)在度为k的树中,至少有一个度为k的结点。
()
(4)在度为k的树中,每个结点最多有k—1个兄弟结点。
()
(5)度为2的树是二叉树。
()
(6)二叉树的度一定为2。
()
(7)在非空完全二叉树中,只有最下面一层的结点为叶结点。
()
(8)在完全-y.树中,没有左孩子的结点一定是叶结点。
()
(9)在完全二叉树中,没有右孩子的结点一定是叶结点。
()
(10)在结点数目一定的前提下,各种形态的二叉树中,完全二叉树具有最小深度。
()
(11)满二叉树一定是完全二叉树。
()
(12)满二叉树中的每个结点的度不是0就是2。
()
(13)在所有深度相同的二叉树中,满二叉树具有最大结点数目。
()
(14)具有n个结点的非空二叉树一定有n—1个分支。
()
(15)n个结点的二叉树采用二叉链表结构,链表中有n—1个存放NULL的指针域。
()
(16)“退化二叉树”不宜采用顺序存储结构的主要原因是空间浪费较大。
()
(17)由二叉树的前序序列和中序序列可以惟一地确定一棵二叉树。
()
(18)由二叉树的中序序列和后序序列可以惟一地确定一棵二叉树。
()
(19)由二叉树的前序序列和后序序列可以惟一地确定一棵二叉树。
()
(20)实现二叉树的按层次遍历算法时需要用到队列结构。
()
(21)实现二叉树的遍历算法时不需要用到堆栈结构。
()
(22)线索二叉树对应的二叉链表中不存在空的指针域。
()
(23)二叉排序树中的任何一棵子树也是二叉排序树。
()
(24)一个序列对应的二叉排序树是惟一的。
()
(25)按照“逐点插入法”建立的二叉排序树的深度与结点的插入顺序无关。
()
(26)在二叉排序树中进行查找的效率与二叉排序树的深度有关。
()
(27)在二叉排序树中查找一个结点,查找长度不会超过二叉树的深度。
()
(28)给定一组权值,构造出来的哈夫曼树是惟一的。
()
(29)哈夫曼树中不存在度为1的结点。
()
(30)在哈夫曼树中,权值相同的叶结点都在同一层上。
()
7.2单项选择题。
(1)树型结构最适合用来描述——。
A•有序的数据元素B•无序的数据元素
C.数据元素之间具有层次关系的数据D.数据元素之间没有关系的数据
(2)对于一棵具有n个结点、度为4的树而言,——。
A.树的深度最多是n-4B.树的深度最多是n-3
C.第i层上最多有4x(i-1)个结点D.最少在某一层上正好有4个结点
(3)“二叉树为空”意味着二叉树————。
A•由一些未赋值的空结点组成B.根结点无子树
巳不存在D.没有结点
(4)按照二叉树的定义,具有3个结点的二叉树有——种形态(不考虑数据信息的组合情况)。
A.2B.3C.4D.5
(5)若一棵度为7的树有8个度为1的结点,有7个度为2的结点,有6个度为3的结点,有5个度为4的结点,有4个度为5的结点,有3个度为6的结点,有2个度为7的结点,则该树一共有——个叶结点。
A.35B.28C.77D.78
(6)若一棵二叉树有10个度为2的结点,则该二叉树的叶结点的个数是——。
A.9B.11C.12D.不确定
(7)若一棵满二叉树有2047个结点,则该二叉树中叶结点的个数为——。
A.512B.1024C.2048D.4096
(8)深度为h的满二叉树的第i层有一一个结点。
(i A.2(i)—1B.2(i)-1C.2(h)—1D.2(h)-1 (9)深度为h的完全二叉树的第i层有——个结点。 (i A.2(i-1)B.2(i)-1C.2(h-1)D.2(h)-1 (10)具有n个结点的非空完全二叉树的深度为——。 A.n-1B.nC.Llog2(n)』D.Llog2(n)』+1 (11)具有2000个结点的非空二叉树的最小深度为——。 A.9B.10C.11D.12 (12)若某完全二叉树的深度为h,则该完全二叉树中至少有一一个结点。 A.2(h)B.2(h)-1c.2(h)+1D.2(h—1) (13)若二叉树的前序序列与后序序列的次序正好相反,则该二叉树一定是——的二叉树。 A•空或仅有一个结点B•其分支结点无左子树 C.其分支结点无右子树D.其分支结点的度都为1 (14)任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置— A•都会发生改变B•不会发生改变 C.有可能会发生改变D•部分会发生改变 (15)对于一个数据元素序列,按照逐点插入方法建立一棵二叉排序树,该二叉排序树的形状取决于——。 A.该序列的存储结构B.序列中数据元素的取值范围 C,数据元素的输人次序D•使用的计算机的软、硬件条件 (16)对一棵二叉排序树进行——遍历,可以得到该二叉树的所有结点按值从小到大排列 的序列。 A.前序B.中序C.后序D.按层次 (17)除了前序遍历(DLR)、中序遍历(LDR)与后序遍历(LRD)夕卜,二叉树的遍历方法还可以有DRL、RDL和RLD三种。 对于一棵二叉排序树,采用——遍历方法可以得到该二叉排序树的所有结点按值从大到小排列的序列。 A.LDRB.LRDC.RLDD.RDL (18)在二叉排序树中进行查找的效率与——有关。 A。 二叉排序树的深度B.二叉排序树的结点的个数 C.被查找结点的度D.二叉排序树的存储结构 (19)在具有n个结点的二叉排序树中查找一个结点的过程的时间复杂度约为——。 A.O (1)B.O(n)C.O(nz)D.O(10gan) (20)下列名词术语中,与数据的存储结构有关系的仅是——。 A.完全二叉树B.满二叉树C.线索二叉树D.二叉排序树 (21)平衡二叉树中任意结点的平衡因子只能是——之一。 A.0,1,2B.0,1C.-1,+1D.0,-1,+17. 3填空题。 (1)任何非空树中有且仅有一个结点没有前驱结点,该结点就是树的——。 (2)树的层次定义为——。 (3)度为k的树中第i层最多有一一个结点(i>1)。 (4)深度为h的k叉树最多有——个结点。 (5)非空二叉树一共有——种基本形态。 (6)非空二叉树中第i层最多有——个结点。 (7)深度为h的二叉树最多有————个结点。 (8)具有n个结点的完全二叉树的深度h二——。 (9)若二叉树有NO个叶结点,n2个度为2的结点,贝UNO与n2的关系是一一。 (10)若具有n个结点的非空zX•树有NO个叶结点,则该二叉树有一一个度为2的结点, ——个度为1的结点。 (11)对具有n个结点的完全二叉树按照层次从上到下,每一层从左到右的次序对所有结点进行编号,编号为i的结点的双亲结点的编号为——,左孩子的编号为——,右孩子的编号为——。 (12)若具有n个结点的二叉树采用二叉链表存储结构,则该链表中有——个指针域,其 中有个指针域用于链接孩子结点,I-个指针域空闲存放着NULL。 (13)二叉树的遍历方式通常有——、——、——和四种。 (14)已知二叉树的前序遍历序列为ABDCEFG,中序遍历序列为DBCAFEG,其后序遍 历序列为——。 (15)已知某完全二叉树采用顺序存储结构,结点的存放次序为A,B,C,D,E,F,G,H, I,J,该完全二叉树的后序序列为——。 (16)在某二叉树中,若结点A有左孩子Y和右孩子X,则在结点的前序序列、中序序列和后序序列中,结点——一定在结点——的前面。 (17)利用中序线索二叉树进行中序遍历可以不用设置——结构。 (18)对二叉排序树进行——,可以得到由该二叉树中结点组成的按值有序排列的序列。 (19)采用逐点插入法建立序列(54,28,16,34,73,62,95,6O,26,43)的二叉排序树后,查找数据元素62共进行——次元素间的比较。 (20)具有N0个叶结点的哈夫曼树共有一一个结点。 7.4若结点A有三个兄弟(包括A本身),并且B是A的双亲结点。 问结点B的度是多少? 7.5若一棵树有n1个度为1的结点,n2个度为2的结点nm个度为m的结点,试 问: 该树一共有多少个叶结点(即度为0的结点个数no)? 请写出推导过程。 7.6一棵深度为h的满m叉树具有如下性质: 第h层上的结点都是叶结点,其余各层上每个结点 都有m棵非空子树。 问: (1)第k层有多少个结点? (1 (2)整棵树有多少个结点? (3)若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,编号为i的结点的双亲结点的编号是什么? 编号为i的结点的第j个孩子结点(若存在的话)的编号是什么? 7.7一棵度为2的树与一棵二叉树有什么区别? 7.8请分别画出具有3个结点的树和具有3个结点的二叉树的所有形态。 7.9请分别列出如图7.42所示的二叉树的所有叶结点与分支结点,并分别指出各结点的度数以及所在的层次数。 7.10若一棵具有n个结点的二叉树采用二叉链表存储结构。 试问: 该二叉链表中共有 多少个空指针域? 写出推导过程。 7.11已知某算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,请写出 其前缀形式(利用二叉树的遍历序列)。 7.12已知某二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,请写出 后序序列。 7.13已知某」X树的中序遍历序列为CBGEAFHD,后序遍历序列为CGEBHFDA,请画出该二叉树的前序线索二叉树的二叉链表结构的表示。 7.14已知按前序遍历二叉树的结果为ABC。 试问,有几种不同的二叉树可以得到这 一遍历结果? 7.15请按照算法,SORTTREE画出对应于序列{15,20,15,7,9,18,61的二叉排序树。 7.16给定一组权值W={14,15,7,3,20,4},请构造出相应的哈夫曼树,并计算其带权的路径长度WPL。 7.17试证明具有n2个叶结点的哈夫曼树的分支总数为2(N0-1)。 7.18二叉树的深度采用自然语言形式可以描述为: 若二叉树为空,则其深度为0,否 则其深度等于左子树与右子树的最大深度加1。 若二叉树采用二叉链表存储结构,请写出求 该二叉树的深度的递归算法。 7.19已知二叉树采用二叉链表存储结构,根结点的地址为T。 请写出二叉树前序遍历 的非递归算法。 7.20已知两棵二叉树都采用二叉链表存储结构,根结点的地址分别为T1和T2。 请写 一算法,判断两棵二叉树是否相似(即具有相同的形态),并给出相应信息。 7.21已知两棵二叉树都采用二叉链表存储结构,根结点的地址分别为T1和T2。 请写一算法,判断两棵二叉树是否是相同的二叉树,并给出相应信息。 7.22已知二叉树采用二叉链表存储结构,根结点的地址为T。 请写一算法,释放该二 叉树中所有结点占用的空间。 7.23已知二叉树采用二叉链表存储结构,根结点的地址为T。 请写一非递归算法统计出 该二叉树共有多少个度为1的结点? 要求: 算法中用到的堆栈采用链式存储结构。 7.24已知非空二叉树采用二叉链表存储结构,根结点地址为T。 请写出非递归算法,该 算法打印数据信息为item的结点的所有祖先结点。 假设数据信息为item的结点不多于一个。 7.25已知二叉树采用二叉链表存储结构,根结点的地址为T。 请写一算法,将该二叉链 表结构转换为顺序存储结构。 7.26已知某具有n个结点的二叉树的前序序列与中序序列分别存放于数组PREOD[n)与 INOD[n]中,并且各结点的数据值均不相同。 试写一非递归算法生成该二叉树的二叉链表结 构。 7.27已知二叉树采用二叉链表存储结构,根结点地址为了。 试写一算法,判断该二叉树是否为完全二叉树,并给出相应信息。 7.28已知二叉树采用二叉链表存储结构,根结点地址为丁。 试写一算法,删去并释放数据值为key的叶结点。 7.29已知二叉排序树采用二叉链表存储结构,根结点的地址为T。 试写一算法,删去数 据值小于或等于key的结点。 7.30已知二叉树采用二叉链表存储结构,根结点的地址为T。 试写一算法,算法功能是 按层次从上到下,每层从右到左的顺序依次列出二叉树所有结点的数据信息。 7.31已知二叉树采用二叉链表存储结构,根结点的地址为T。 试写一算法,打印该二叉 树所有左子树的根结点的数据信息。 7.32已知二叉树采用二叉链表存储结构,根结点的地址为T。 试写一算法,交换二叉树 所有左、右子树的位置,即将结点的左子树变成结点的右子树,右子树变成左子树。 7.33已知二叉树采用二叉链表存储结构,根结点的地址为丁。 请写一算法,输出从根结点到某个指定结点的路径上各结点的值。 7.34已知二叉树采用二叉链表存储结构,根结点的地址为T,请写一算法,判断该二叉 树是否是二叉排序树。 7.35将图7.43所示的树林转换为一棵二叉树。 7.36分别写出如图7.44所示的树的前序遍历序列与后序遍历序列。 7.37已知某树林转化为二叉树后所对应的顺序存储结构为请画出该树林。 历年考题 1•在具有n个叶子结点的严格二叉树中,结点总数为() A.2n+1B.2nC.2n-1D.2n-2 2.除根结点外,树上每个结点() A.可有任意多个孩子、任意多个双亲 B.可有任意多个孩子、一个双亲 C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲 3.具有100个结点的二叉树中,若用二叉链表存储,其指针域部分用来指向结点的左、右 孩子,其余( )个指针域为空。 A.50 B.99C.100 D.101 4.右构造一棵具有 n个结点的二叉排序树, 最坏的情况下其深度不会超过( ) A.n/2 B.nC.(n+1)/2 D.n+1 5.下列树U',经剪技运算DELETE(U',x,2)后为() 6•—棵有16结点的完全二叉树,对它按层编号,则对编号为7的结点X,它的双亲结点及 右孩子结点的编号分别为() A•2,14B•2,15C•3,14D.3,15 7•下列陈述中正确的是() A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树,并且有左右之分 结点N的左子 8、任一棵树均可唯一地转换成与它对应的二叉树。 由树转换成的二叉树中 女是N在原树里对应结点的__A__,而N的右子女是原树里对应结点的__B. 在下列二叉树中,图一为__C_树,图二为_D__树,图三为__E__树。 D E H /\ /\ / \ BG B P D L /\/\ / \/\ /\ CAEH MS C EJK / /\ F RT 9、前序遍历序列与中序遍历序列相同的二叉树为⑴,前序遍历序列与后序遍历序列相 同的二叉树为 (2)。 (1)A、根结点无左子树的二叉树 B、根结点无右子树的二叉树 C、只有根结点的二叉树或非叶子结点只有左子树的二叉树 D、只有根结点的二叉树或非叶子结点只有右子树的二叉树 (2)A、非叶子结点只有左子树的二叉树 B、只有根结点的二叉树 C、根结点无右子树的二叉树 D、非叶子结点只有右子树的二叉树 10、假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF, 则其前序遍历序列为(10)。 (10)A、ABCDEFGHIJB、ABDEGHJCFIC、ABDEGHJFICD、ABDEGJHCFI 11、设某种二叉树有如下特点;结点的子树数目不是2个,则是0个。 这样的一棵二叉树 中有m(m>O)个子树为0的结点时,该二叉树上的结点总数为(34)。 (34)A.2m+lB.2m-1C.2(m—1)D.2(m+1) 12、已知一棵二叉树的前序序列和中序序列分别为ABDEGCF! 和DBGEACHJF则该二叉树的后序序列为—A_,层次序列为—B_。 设有n个结点进行排序,不稳定排序是—C_;? 快速排序的最大比较次数是—D_o 设有100个结点,用二分法查找时,最大比较次数是—E_o? 供选择的答案 AB: ①GEDHFBCA ②DGEBHFCA ③ABCDEFGH ④ACBFEDHG C: ①直接插入排序 ②冒泡排序 ③Shell排序 ④归并排序 D: ①nlog2n ②n2 ③n2/2 ④n E: ①25 ②50 ③10 ④7 AD: ①有0个或1个 ②有0个或多个 ③有且只有1个 ④有1个或1个以上 B: ①互不相交 ②允许相交 ③允许叶结点相交 ④允许树枝结点相交 C: ①权②维数 ③次数 ④序 D: ①丰满树②查找树 ③平衡树 ④完全树 14、二叉树_ _A_。 在完全的二叉树中, 若一个结点没有— B_,则它必 树都能唯一地转换成与它对应的二叉树。 由树转换成的二叉树里, 一个结点 ,定是叶结点。 每棵 N的左子女是N在原树里对应结点的—C_,而N勺右子女是它在原树里对应结点的—D_。 二叉排序树的平 均检索长度为—E_o 供选择的答案: 15、每一棵树都能唯一地转换为它所对应的二叉树,树的这种二叉树表示对树的运算带来很大的好处。 遍历(周游)是树形结构的一种重要运算,二叉树的基本组成部分是: 根(N)、 左子树(L)和右子树(R)o因而二叉树的遍历次序有六种。 最常用的是三种: 前序法(即按A次序),后序法(即按—B—次序)和中序法(也称对称序法,即按—C__次 序)。 这三种方法相互这间有关联。 若已知一棵二叉树的前序序列是BEFCGD,中序序列是 FEBGCHJD则它的后序序列必是—D_,而且可得该二叉树所表示的树的先根次序序列是 B。 供选择的答案 A〜C: ① R L N ②RNL ③ L RN ④ L
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遍历 递归 算法 doc