2016最新广工anyview数据结构答案

if (p->rchild != NULL) {

p =p->rchild; //若有右子树，转到该子树，继续寻找最左下结点 } else {

pr = p; //否则返回其父亲 p = p->parent;

while (p != NULL && (p->lchild != pr || NULL == p->rchild)) { //若其不是从左子树回溯来的，或左结点的父亲并没有右孩子 if (p->lchild == pr) { //若最左结点的父亲并没有右孩子 visit(p->data); //直接访问父亲（不用转到右孩子） }

pr = p; //父亲已被访问，故返回上一级 p = p->parent; //该while

循环沿双亲链一直查找，若无右孩子则访问，直至找到第一个有右孩子的结点为止（但不访问该结点，留给下步if语句访问） }

if (NULL != p) { //访问父亲，并转到右孩子（经上步while处理，可以确定此时p有右孩子） visit(p->data); p = p->rchild; } } } } } /**********

【题目】假设在三叉链表的结点中增设一个标志域 (mark取值0,1或2)以区分在遍历过程中到达该结点 时应继续向左或向右或访问该结点。试以此存储结 构编写不用栈辅助的二叉树非递归后序遍历算法。 带标志域的三叉链表类型定义：

typedef struct TriTNode { TElemType data;

struct TriTNode *lchild, *rchild, *parent; int mark; // 标志域 } TriTNode, *TriTree; **********/

void PostOrder(TriTree T, void (*visit)(TElemType)) /* 不使用栈，非递归后序遍历二叉树T， */ /* 对每个结点的元素域data调用函数visit */ {

// 0向左，1自身，2向右 TriTree p= T, pr; while(true){

while(p!=NULL&&p->mark!=1){ if(p->rchild!=NULL) //若有右孩子

p->mark=2; else p->mark=1; pr=p; p=p->lchild; }

p=pr; pr=pr->parent; if(p->mark==2) {p->mark=1; p=p->rchild;} else{ visit(p->data); p->mark=1; }

if(p->data==T->data) break; }