《6章讲义1.ppt

基本操作的函数原型说明 Status CreateBiTree(BiTree T); //按先序秩序输入二叉树中结点的值，构造 //二叉链表表示的二叉树 Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); //先序遍历二叉树T Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); //中序遍历二叉树T 基本操作的函数原型说明 Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); //后序遍历二叉树T Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); //层序遍历二叉树T visit是一个函数，可以是对结点的插入、删除和修改，可以是其他的操作，例如，最简单的Visit函数：输出结点数据的值。 Status PrintElement(TElemType e) {//输出元素e的值 printf(e);// return OK;; } 遍历的方法： 把二叉树上的复杂的结点关系变为一个线性结构关系，使得每个结点元素都有明确的唯一的一个直接前驱和一个直接后继。即使得二叉树上的结点能够排列在一个线性队列上，这样就便于对结点进行各种操作。 利用二叉树表示表达式： a+5+b*6-c/8 中序遍历过程中递归工作栈的状态 工作记录中包括两项：其一是递归调用的语句编号；其二为指向根结点的指针。 如果栈顶记录中的指针值非空，则说明二叉树的根结点存在，则应中序遍历这棵二叉树，即先遍历其左子树，将指向左子树根结点的指针压入栈顶； 如果栈顶记录中的指针值为空，则说明该二叉树不存在，应该退到这个空二叉树的上一层。如果此时是从左子树返回来的，则应立即访问栈顶指针所指的根结点。如果是从右子树返回的，则说明当前层访问完毕。 void InorderTraverse(BiTree T, void (*visit) (TelemType e)){ IniStack(S);p=T; while(p|| (!StackEmpty(S)){ //栈非空或还有右子树 if(p) {Push(S,p);p=p-lchild};//压入非空根结点 else{ Pop(S,p); if(!Visit(p-data)) return ERROR; p=p-rchild;//查看右子树 }//end else }//end while return OK; }//InorderTraverse 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 中（根）序的遍历算法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. void InorderTraverse (BiTree T,Status( *visit)(TElemType e)) { // 中序遍历二叉树 if (T) { if(InorderTraverse (T-lchild, visit)) // 遍历左子树 if(visit(T-data)) // 访问根结点 if(InorderTraverse (T-rchild, visit)) // 遍历右子树 return OK; return ERROR; } else return OK; }// InorderTraverse Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 后（根）序的遍历算法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2