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

} BiTNode, *BiTree;

可用栈类型Stack的相关定义： typedef struct {

struct BiTNode *ptr; // 二叉树结点的指针类型 int tag; // 0..1

} SElemType; // 栈的元素类型 Status InitStack(Stack &S); Status StackEmpty(Stack S);

Status Push(Stack &S, SElemType e); Status Pop(Stack &S, SElemType &e); Status GetTop(Stack S, SElemType &e); **********/

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

{

if(T==NULL)return ; Stack s; InitStack(s); SElemType e; e.ptr=T; e.tag=0; while(1){

while(e.ptr!=NULL){Push(s,e); e.ptr=e.ptr->lchild; }

while(StackEmpty(s)==FALSE){ Pop(s,e);

if(e.ptr->rchild!=NULL){ if(e.tag==0) {

e.tag=1;Push(s,e); e.ptr=e.ptr->rchild; e.tag=0;break; } }

visit(e.ptr->data);} if(StackEmpty(s))break; } } /**********

【题目】二叉树采用三叉链表的存储结构，试编写 不借助栈的非递归中序遍历算法。 三叉链表类型定义： typedef struct TriTNode { TElemType data;

struct TriTNode *parent, *lchild, *rchild; } TriTNode, *TriTree; **********/

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

TriTree p=PT, pr; while(NULL != p) {

if (p->lchild != NULL) { p = p->lchild; //寻找最左下结点 } else {

visit(p->data); //找到最左下结点并访问