《非递归处理栈》PPT课件.ppt

Houfeng Wang, ICL of PKU,1,非递归处理 栈,1. 先根：PreOrder(Bnode p),Houfeng Wang, ICL of PKU,2,右子树进栈,Houfeng Wang, ICL of PKU,3,左子树进栈,a,c,b,Houfeng Wang, ICL of PKU,4,栈顶元素出栈，重复！,b 作为新的子树的根，重复上述步骤,Houfeng Wang, ICL of PKU,5,PreOrder(BNode t) BNode a; push(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(BNode t,Houfeng Wang, ICL of PKU,6,中根（对称序） PreOrder(Bnode p),Houfeng Wang, ICL of PKU,7,如何保证根节点出栈后不再进？,特是标记：栈内每个元素有两个域： struct snode BNode element; char tag; typedef struct snode DataType,Houfeng Wang, ICL of PKU,8,InOrder(BNode t) DataType a; a.element=t; a.element.tag=1; push(t); Do a=top(paseq); / 取栈paseq 的栈顶元素 pop(paseq); /出栈 if(a.element!=NULL) If(a.tag!=1) visit(a.element); else (右孩子 and tag=1) 进栈 ( 根 and tag=0) 进栈 (左孩子 and tag=1) 进栈 / (a.element!=NULL) while( isEmptyStack_seq(paseq) /栈空，结束。 / InOrder(BNode t),Houfeng Wang, ICL of PKU,9,后根周游算法,方法：见教材，两种算法（后者以递归方式进栈） 基本思想： Step1:根进栈， Step2:栈顶元素出栈，且：分解 退栈元素的 Tag=0，则输出，否则： 退栈的元素再进栈（Tag=0） 退栈的元素左子节点进栈（Tag=1） 退栈的元素右子节点进栈（Tag=1） Step2:重复 Step2,直至栈空,Houfeng Wang, ICL of PKU,10,后根周游算法,如何写算法？(练习！) 与教材上的算法比较,Houfeng Wang, ICL of PKU,11,树、树林转换为二叉树,将树或树林转换成对应的二叉树可以按以下步骤进行： (1) 在所有相邻的兄弟结点之间加一条线； (2) 对每个非终端结点，只保留它到其最左子女的连线，删去它与其它子女之间的连线； (3) 以根结点为轴心，将整棵树顺时针旋转一定角度（如45度），使其结构层次分明。,Houfeng Wang, ICL of PKU,12,5.16给出的例子显示了这一转换过程。,Houfeng Wang, ICL of PKU,13,树的长子兄弟表示方法,struct CSNode; /* 树中结点结构 */ typedef struct CSNode *PCSNode; /* 结点的指针类型 */ struct CSNode /* 结点结构定义 */ DataType info; /* 结点中的元素 */ PCSNode lchild; /* 结点的最左子女的指针 */ PCSNode rsibling; /* 结点的右兄弟的指针 */ ; 将PCSNode rsibling 改为： PCSNode rchild; typedef struct CSNode *CSTree; /* 树类型定义 */,Houfeng Wang, ICL of PKU,14,Houfeng Wang, ICL of PKU,15,设树林 F 是有序的序列，F = T1，T2，Tn，对应于 F 的二叉树 B(F) 的定义如下： (1) 若n = 0，则B(F)为空； (2) 若n0，则B(F)的根是T1的根w1，B(F)的左子树是B(T11，T12，T1m)，其中T11，T12，T1m是T1的子树；B(F)的右子树是B(T2，Tn ),形式化描述,Houfeng Wang, ICL of PKU,16,树对应到二叉树其根结点的右子树总是为空的。如图5.17。,Houfeng Wang, ICL of PKU,17,二叉树转换为树或树林,将二叉树转换成树或树林可以按以下步骤进行： (1) 若某结点是其父母的左子女，则把该结点的右子女，的右子女的右子女，都与该结点的父母用虚线连起来； (2) 去掉原二叉树中所有父母到右子女的连线； (3) 整理由(1)、(2)两步所得到的树或树林，使之结构层次分明，并将虚线改为实线。,Houfeng Wang, ICL of PKU,18,图5.18所示的例子显示了这一转换过程。,Houfeng Wang, ICL of PKU,19,设B是一棵二叉树，r是B的根，L是r的左子树，R是r的右子树，则对应于B的树林F(B)的定义是： (1) 若B为空，则F(B)是空的树林； (2) 若B不为空，则F(B)是一棵树T1加上树林F(R)，其中树T1的根为r，r的子树为F(L)。,形式化描述,Houfeng Wang, ICL of PKU,20,二叉树的存储表示与应用,Houfeng Wang, ICL of PKU,21,顺序表示,将完全二叉树上序号为i (1in)的结点存储在数组下标为i - 1的元素中（如下图）。,Houfeng Wang, ICL of PKU,22,一般二叉树以及对它改造后的完全二叉树和其顺序存储表示。,Houfeng Wang, ICL of PKU,23,Houfeng Wang, ICL of PKU,24,采用顺序存储表示的二叉树结构定义： struct SeqBTree DataType nodelistMAXNODE; int n; ; typedef struct SeqBTree *PSeqBTree;,Houfeng Wang, ICL of PKU,25,二叉树上一些基本运算的实现主要过程可以直接用一个表达式或语句来代替函数调用。假设t是PseqBTree类型的变量，p是二叉树中的结点在数组中的存储下标，类型为int，则以下函数的返回相应结点在数组中的存储下标值，类型也为int： root_seq(t) 0 （即结点为 t- nodelist0） parent_seq( t, p) (p 1)/2 （即结点为 t- nodelist(p 1)/2） leftChild_seq(t, p) 2p + 1 （即结点为 t- nodelist2p + 1） rightChild_seq(t, p) 2(p+1) （即结点为 t- nodelist2(p+1) 看完全二叉树的定义。,Houfeng Wang, ICL of PKU,26,5.4.2链接表示,每个链结点的实际结构可形象地描述为：,Houfeng Wang, ICL of PKU,27,Houfeng Wang, ICL of PKU,28,在二叉树的二叉链表中，每个链结点的结构： struct BinTreeNode ; typedef struct BinTreeNode *PBinTreeNode; struct BinTreeNode DataType info; /* 数据域 */ PBinTreeNode llink; /* 指向左子女 */ PBinTreeNode rlink; /* 指向右子女 */ ;,Houfeng Wang, ICL of PKU,29,typedef struct BinTreeNode *BinTree; 表示树（根）,Houfeng Wang, ICL of PKU,30,二叉树类型BinTree与指向结点的指针类型PBinTreeNode实际上是同一类型，只是概念不同而已。 在实际应用中，将二叉树作为参数传递时，常传递的是二叉树根结点指针的地址，因此，为了说明方便，常引入二叉树类型的指针类型： typedef BinTree *PBinTree; 假设t是BinTree 类型的变量，则t就是一个指向二叉树根结点的指针，它既指明根的位置又标识一棵二叉树。,Houfeng Wang, ICL of PKU,31,在这种表示法中，二叉树上的一些基本运算的实现也非常简单，可以直接用一个表达式或语句来代替函数调用。 假设t是BinTree类型的变量，p是二叉树中结点的存储位置，类型为PBinTreeNode，与树中处理方法类似，以下函数的返回值类型也设计为PBinTreeNode。 root_btree(t) t leftChild_btree (p) p-llink rightChild_btree (p) p-rlink,Houfeng Wang, ICL of PKU,32,Houfeng Wang, ICL of PKU,33,二叉树另一种常用的链式表示方式是三叉链表表示，即树中的每个结点除有数据域和左、右指针域外，还有一个指向父结点的指针域。,Houfeng Wang, ICL of PKU,34,5.4.3 二叉树的生成,Houfeng Wang, ICL of PKU,35,先将二叉树扩充成为扩充的二叉树，然后按先根次序周游的顺序输入结点的信息,生成一个双链存储的二叉树的过程。 例：前面图所示的二叉树，经过扩充，再按先根次序周游得到的序列为： ABDCEGFHI 其中为外部结点，用于表示向下结束。,Houfeng Wang, ICL of PKU,36,根据先根序列创建二叉树,PBinTree create_BTree( void ) /* 创建完整的二叉树 */ PBinTree pbtree; pbtree = (PBinTree)malloc(sizeof(BinTree); if (pbtree!=NULL) *pbtree = createRest_BTree( ); /* 递归创建从根开始的二叉树 */ return pbtree; ,Houfeng Wang, ICL of PKU,37,PBinTreeNode createRest_BTree() / 递归创建从根开始的二叉树 PBinTreeNode pbnode; char ch; scanf(“%c“, ,Houfeng Wang, ICL of PK