《非递归处理栈》ppt课件

《《非递归处理栈》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、非递归处理—栈1.先根：PreOrder(Bnodep)abc1Visit(a)1HoufengWang,ICLofPKU右子树进栈2Push(right(a))C=right(a)abc2HoufengWang,ICLofPKU左子树进栈a3Push(left(a))C=right(a)b=left(a)cb3HoufengWang,ICLofPKU栈顶元素出栈，重复！abc4Top&PopC=right(a)b作为新的子树的根，重复上述步骤4HoufengWang,ICLofPKUPreOrder(BNodet){BNodea;pus

2、h(t);Do{a=top(paseq);//取栈paseq的栈顶元素pop(paseq);//出栈if(a!=NULL){visit(a);push(rightchild(a));//右孩子进栈push(lightchild(a));//左孩子进栈}//if(a!=NULL)}while(isEmptyStack_seq(paseq))//栈空，结束。}//PreOrder(BNodet5HoufengWang,ICLofPKU中根（对称序）PreOrder(Bnodep)abc1Push(right(a))C=right(a)3Pus

3、h(left(a))C=right(a)aC=left(a)4Top&PopC=right(a)a2Push(a)C=right(a)a6HoufengWang,ICLofPKU如何保证根节点出栈后不再进？特是标记：栈内每个元素有两个域：structsnode{BNodeelement;chartag;}typedefstructsnodeDataType7HoufengWang,ICLofPKUInOrder(BNodet){DataTypea;a.element=t;a.element.tag=1;push(t);Do{a=top(p

4、aseq);//取栈paseq的栈顶元素pop(paseq);//出栈if(a.element!=NULL){If(a.tag!=1)visit(a.element);else{(右孩子andtag=1)进栈(根andtag=0)进栈(左孩子andtag=1)进栈}}//(a.element!=NULL)}while(isEmptyStack_seq(paseq))//栈空，结束。}//InOrder(BNodet)8HoufengWang,ICLofPKU后根周游算法方法：见教材，两种算法（后者以递归方式进栈）基本思想：Step1:根进

5、栈，Step2:栈顶元素出栈，且：分解①退栈元素的Tag=0，则输出，否则：②退栈的元素再进栈（Tag=0）退栈的元素左子节点进栈（Tag=1）退栈的元素右子节点进栈（Tag=1）Step2:重复Step2,直至栈空根进栈(Tag=1)Step19HoufengWang,ICLofPKU后根周游算法如何写算法？？(练习！！！)与教材上的算法比较10HoufengWang,ICLofPKU树、树林转换为二叉树将树或树林转换成对应的二叉树可以按以下步骤进行：(1)在所有相邻的兄弟结点之间加一条线；(2)对每个非终端结点，只保留它到其最左子女的

6、连线，删去它与其它子女之间的连线；(3)以根结点为轴心，将整棵树顺时针旋转一定角度（如45度），使其结构层次分明。11HoufengWang,ICLofPKU5.16给出的例子显示了这一转换过程。12HoufengWang,ICLofPKU树的长子兄弟表示方法structCSNode;/*树中结点结构*/typedefstructCSNode*PCSNode;/*结点的指针类型*/structCSNode/*结点结构定义*/{DataTypeinfo;/*结点中的元素*/PCSNodelchild;/*结点的最左子女的指针*/PCSNod

7、ersibling;/*结点的右兄弟的指针*/};将PCSNodersibling改为：PCSNoderchild;typedefstructCSNode*CSTree;/*树类型定义*/13HoufengWang,ICLofPKUabcdefghij14HoufengWang,ICLofPKU设树林F是有序的序列，F=T1，T2，…，Tn，对应于F的二叉树B(F)的定义如下：(1)若n=0，则B(F)为空；(2)若n＞0，则B(F)的根是T1的根w1，B(F)的左子树是B(T11，T12，…，T1m)，其中T11，T12，…，T1m是T

8、1的子树；B(F)的右子树是B(T2，…，Tn)形式化描述15HoufengWang,ICLofPKU树对应到二叉树其根结点的右子树总是为空的。如图5.17。16HoufengWang,ICL