栈的应用和串图

1、例例1 1数制转换数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2除基取余法void conversion( ) InitStack(s); scanf (“%d”,N); while(N) while(! StackEmpty(S) printf(“%d”,e); / conversi

2、onpush(S,N%8);N=N/8;Pop(S,e);例例2 表达式求值表达式求值大家考虑一下：4+2310/5的求值运算过程两个相继出现的运算符的优先关系为了用栈来实现计算表达式，我们定义两个栈，一个是OPTR，用以寄存运算符，一个是OPND，用以寄存操作数或运算结果。其基本思想如下：（1）首先置操作数栈为空栈，表达式起始符为“#”为栈的栈底元素；（2）依次读入表达式的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈顶 的元素比较优先级后再做相应的操作，直到表达式求值结束（即：OPTR的栈顶元素和当前读入的字符均为“#” ）OperandType EvaluateExpres

3、sion()/算术表达式求值的算符优先算法，设OPTR和OPND分别是运算符栈和运算数栈，OP为运算符集合InitStack(OPTR); Push(OPTR,”#”);InitStack(OPND);c=getchar();While(c!=#|GetTop(OPTR)!=) if(!In(c,OP)Push(OPND,c); c=getchar();/不是运算符则进入 栈switch(Precede(GetTop(OPTR),c) case : 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a);Push(OPND, Operat

4、e(a, theta, b); break; /switch/whileRerurn GetTop(OPND);/ EvaluateExpression现在以3（72）演示一下。 选择题选择题1. 对于栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 3. 一个栈的输入序列为1,2,3n，若输出序列的第一个元素是n，输出第i（1=i1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。树还有其他的表示形式:：1以嵌套集合的形式表示；2以广义表的形式表示；3 以凹入法表示（类似书的编目）K L

5、 ME F G H I J B C DAA(a)(b)(c)基本术语基本术语结点：结点： 包含一个数据元素及若干指向其子树根的分支。结点的度结点的度 ：结点拥有的子树数，即结点的分支数。终端结点（叶子）：终端结点（叶子）： 度为0的结点。非终端结点非终端结点 ： 度不为0的结点。结点的层次结点的层次 ： 树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度：树的度： 树中所有结点度的最大值。树的深度：树的深度： 树中结点的最大层次。有序树、无序树有序树、无序树 ： 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。森林：森林： 是m（m0）棵互不相

6、交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子、双亲孩子、双亲 ： 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。子孙子孙： 以某结点为根的子树中的所有结点都被称为是该结点的子孙。祖先祖先： 从根结点到该结点路径上的所有结点。兄弟兄弟： 同一个双亲的孩子之间互为兄弟。堂兄弟堂兄弟： 双亲在同一层的结点互为堂兄弟。问题1：图中结点个数和分支之间的关系？问题2：图中某个结点的度数和从它引出引出的分支之间的关系？假设B为上图所表的树中分支（直线段）的个数，ni 表示度为i的结点的个数，n为结点总数，显然有n=B+1, n=n0+n1+n2nk,B=n0*

7、0+n1*1+n2*2+nk*k,例如：. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A5 B6 C7 D8Dn=B+1, n=n0+n1+n2nk,B=n0*0+n1*1+n2*2+nk*k,B= n0*0+1*4+2*2+3*1+4*1=15,n=B+1=16, 而n=n0+4+2+1+1=n0+8=16,n0=8 6.2.1 二叉树的定义和基本运算二叉树的定义和基本运算1. 定义定义定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。 二叉树也可以用递归的形式定义。即：二叉树是n（n0）

8、个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。G HD E FB CA例如：二叉树的二叉树的5种形态：种形态：(a)(b)(c)(d)(e)二叉树的第二叉树的第1层只有一个根结点，所以，层只有一个根结点，所以，i=1时，时，2i-1=21-1=20=1成立。成立。 假设对所有的假设对所有的j，1ji成立，即第成立，即第j层上最多有层上最多有2j-1个结点成立。个结点成立。若若j=i-1，则第，则第j层上最多有层上最多有2j-1=2i-2个结点。由于在二叉树中，个结点

9、。由于在二叉树中，每个结点的度最大为每个结点的度最大为2，所以可以推导出第，所以可以推导出第i层最多的结点个数层最多的结点个数就是第就是第i-1层最多结点个数的层最多结点个数的2倍，即倍，即2i-2*2=2i-1。2二叉树的性质二叉树的性质 二叉树具有下列二叉树具有下列5个重要的性质。个重要的性质。 【性质【性质1】 在二叉树的第在二叉树的第i层上最多有层上最多有2i-1个结点（个结点（i1）。）。【性质性质2】 深度为深度为K的二叉树最多有的二叉树最多有2K-1个结点（个结点（K1）。）。 qqaaSnn1*1由性质由性质1可以得出，可以得出，1至至K层各层最多的结点个数分别为：层各层最多的

10、结点个数分别为：20,21,22,23,.,2K-1。这是一个以。这是一个以2为比值的等比数列，前为比值的等比数列，前n项之和的计项之和的计算公式为：算公式为： 其中其中 a1为第一项，为第一项，an为第为第n项，项，q为比值。可以得为比值。可以得到，该数列前到，该数列前K项之和为：项之和为：12212*1202KK【性质【性质3】 对于任意一棵二叉树对于任意一棵二叉树BT，如果度为，如果度为0的结点个数为的结点个数为n0，度为度为2的结点个数为的结点个数为n2，则，则n0=n2+1。证明：假设度为证明：假设度为1的结点个数为的结点个数为n1，结点总数为，结点总数为n，B为二叉树中的为二叉树中

11、的分支数。分支数。因为在二叉树中，所有结点的度均小于或等于因为在二叉树中，所有结点的度均小于或等于2，所以结点总数，所以结点总数为：为： n=n0+n1+n2 （1）再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数个从上向下的分支指向，所以，总的结点个数n与分支数与分支数B之间的关之间的关系为：系为：n=B+1。又因为在二叉树中，度为又因为在二叉树中，度为1的结点产生的结点产生1个分支，度为个分支，度为2的结点产生的结点产生2个分支，所以分支数个分支，所以分支数B可以表示为：可以表示为：

12、B=n1+2n2。 将此式代入上式，得：将此式代入上式，得： n=n1+2n2+1 （2） 用（用（1）式减去（）式减去（2）式，并经过调整后得到：）式，并经过调整后得到：n0=n2+1。满二叉树：满二叉树： 如果一个深度为如果一个深度为K的二叉树拥有的二叉树拥有2K-1个结点，则将它称为满二叉树。个结点，则将它称为满二叉树。 8 9 10 11 12 13 14 154 5 6 72 31 完全二叉树：有一棵深度为完全二叉树：有一棵深度为h，具有，具有n个结点的二个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分

13、别进行编号，且该二按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为叉树中的每个结点分别与满二叉树中编号为1n的结点的结点位置一一对应，则称这棵二叉树为位置一一对应，则称这棵二叉树为完全二叉树完全二叉树。不是完全二叉树不是完全二叉树 【性质性质4】 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。其中，。其中， log2n 的结果是不大于的结果是不大于log2n的最大整的最大整数。数。 证明：假设具有证明：假设具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为K，则根据性质则根据性质2可以得出：可以得出： 2K-1-1

14、n2K-1 将不等式两端加将不等式两端加1得到：得到： 2K-1n2K 将不等式中的三项同取以将不等式中的三项同取以2为底的对数，并经过化简为底的对数，并经过化简后得到：后得到： K-1log2nn，则结点，则结点i没有左孩子；否则其左孩子结没有左孩子；否则其左孩子结点的编号为点的编号为2i。 （3）如果）如果2i+1n，则结点，则结点i没有右孩子；否则其右孩没有右孩子；否则其右孩子结点的编号为子结点的编号为2i+1。 下面我们利用数学归纳法证明这个性质。下面我们利用数学归纳法证明这个性质。 我们首先证明（我们首先证明（2）和（）和（3）。）。 当当i=1时，若时，若n3，则根的左、右孩子的编

15、号分别是，则根的左、右孩子的编号分别是2，3；若；若n3，则根没有右孩子；若，则根没有右孩子；若nn，且且2(i+1)=n时，结点时，结点i+1只有左孩子，而没有右孩子；当只有左孩子，而没有右孩子；当2(i+1)n，结点，结点i+1既没有左孩子也没有右孩子。既没有左孩子也没有右孩子。 以上证明得到（以上证明得到（2）和（）和（3）成立。）成立。 下面利用上面的结论证明（下面利用上面的结论证明（1）。）。 对于任意一个结点对于任意一个结点i，若，若2in，则左孩子的编号为，则左孩子的编号为2i，反过来结点反过来结点2i的双亲就是的双亲就是i，而，而 2i/2 =i；若；若2i+1n，则右，则右孩

16、子的编号为孩子的编号为2i+1，反过来结点，反过来结点2i+1的双亲就是的双亲就是i，而，而 (2i+1)/2 =i，由此可以得出（，由此可以得出（1）成立。）成立。 6.2.3 二叉树的存储结构二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。链式存储结构。1. 1. 顺序存储结构顺序存储结构 这种存储结构适用于完全二叉树。其存储形式为：这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存

17、的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。储结构。84 5 6 72 313 32 2 链式存储结构链式存储结构 在顺序存储结构中，利用编号表示元素的位置及元在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。应该考虑使用链式存储结构。 常见的二叉树结点结构如下所示：常见的二叉树结点结构如下

18、所示： 其中，其中，lchild和和rchild是分别指向该结点左孩子和右孩是分别指向该结点左孩子和右孩子的指针，子的指针，data是数据元素的内容。在是数据元素的内容。在C语言中的类型定语言中的类型定义为：义为： typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchlid; BiTNode,*BiTree;G HD E FB CA G H D E F B CABT一棵二叉树及相应的链式存储结构一棵二叉树及相应的链式存储结构 这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个

19、结点添加一个指向双亲结点的指针域，其结点结构如下所示。注：在具体的应用中采用什么存储结构，除根据二叉树的形态之注：在具体的应用中采用什么存储结构，除根据二叉树的形态之外还应考虑需进行何种操作。外还应考虑需进行何种操作。5. 在下述结论中，正确的是（ ）只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D8若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 9在一棵三叉树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个

20、，则度为0的结点数为（ ）个A4 B5 C6 D7 DBC11具有10个叶结点的二叉树中有（ ）个度为2的结点，A8 B9 C10 Dll12一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）A 250 B 500 C254 D505 E以上答案都不对 16. 有关二叉树下列说法正确正确的是（ ）A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为217二叉树的第I层上最多含有结点数为（ ）A2I B 2I-1-1 C 2 I-1 D2I -1BEBC18. 一个具有1025个结点的二叉树的高h为（ ）A11 B10 C11至

21、1025之间 D10至1024之间19一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1 20对于有n 个结点的二叉树, 其高度为（ ）Anlog2n Blog2n Clog2n+1 D不确定21. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）Alog2n+1 Blog2n+1 Clog2n Dlog2n-122深度为h的满m叉树的第k层有（ ）个结点。(1=k=h) Amk-1 Bmk-1 Cmh-1 Dmh-1CBDAA23在一棵高度为k的满二叉树中，结点总数为（ ）A2k-1 B2k C2k-1 Dlog2k+124高度为 K的二叉树最大的结点数为（ ）。A2k B2k-1 C2k -1 D2k-1-125. 一棵树高为K的完全二叉树至少有（ ）个结点A2k 1 B. 2k-1 1 C. 2k-1 D. 2k26. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ ）A4 B5 C6 D7CCCC二、填空题二、填空题1二叉树由_(1)_，_(2)_，_(3)_三个基本单元组成。6具有256个结点的完全二叉树的深度为_。 7已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点。8