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

二叉链表类型定义： typedef struct BiTNode { TElemType data;

struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/

int Leaves(BiTree T)

/* 计算二叉树T中叶子结点的数目 */ { int i=0;

if(T==NULL)return 0;

if(T->lchild==NULL&&T->rchild==NULL) return 1; i+=Leaves(T->lchild); i+=Leaves(T->rchild); return i;

} /**********

【题目】试利用栈及其基本操作写出二叉树T的非递归 的先序遍历算法。 二叉链表类型定义： typedef struct BiTNode { TElemType data;

struct BiTNode *lchild,*rchild; } BiTNode, *BiTree;

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

typedef BiTree 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 PreOrder(BiTree T, void (*visit)(TElemType)) /* 使用栈，非递归先序遍历二叉树T， */ /* 对每个结点的元素域data调用函数visit */ {

Stack S; InitStack(S); BiTree p=T;

TElemType temp= T->data; //首元素赋给temp，由于算法问题防止循环两遍 Push(S,p); while(true){ if(p){

visit(p->data);

if(p->rchild!=NULL) Push(S,p->rchild); //栈特点：后进先出，故遍历左结点时一路把右结点压入栈

p=p->lchild; } else

Pop(S,p); //遍历完左结点，弹出对应右结点，继续遍历 if(temp==p->data) break; //结束条件 } } /**********

【题目】试利用栈及其基本操作写出二叉树T的非递归 的后序遍历算法(提示：为分辨后序遍历时两次进栈的 不同返回点，需在指针进栈时同时将一个标志进栈）。 二叉链表类型定义： typedef struct BiTNode { TElemType data;

struct BiTNode *lchild,*rchild;