数据结构考研分类复习真题 第六章 答案 (五)[18]

void InOrder(BiTree bt)

{BiTree s[]p=bt; //s是元素为二叉树结点指针的栈容量足够大

int top=;

while(p || top>)

{while(p) {s[++top]=p; bt=p>lchild;} //中序遍历左子树

if(top>){p=s[top]; printf(p>data); p=p>rchild;} //退栈访问转右子树

} }

[题目分析] 二叉树用顺序方式存储其遍历方法与用二叉链表方式存储类似判空时在二叉链表方式下用结点指针是否等于null在顺序存储方式下 一是下标是否是虚结点二是下标值是否超过最大值（高为H的二叉树要有H个存储单元与实际结点个数关系不大）当然顺序存储方式下要告诉根结点的下标

void InOrder(int i) //对顺序存储的二叉树进行中序遍历i是根结点的下标

{if(i!=)

{InOrder(ar[i]Lc); //中序遍历左子树

printf(ar[i]data); //访问根结点

InOrder(ar[i]Rc); //中序遍历左子树

} } // 结束InOrder

[题目分析] 借助队列和栈最后弹出栈中元素实现对二叉树按自下至上自右至左的层次遍历

void InvertLevel(biTree bt) // 对二叉树按自下至上自右至左的进行层次遍历

{if(bt!=null)

{StackInit(s); //栈初始化栈中存放二叉树结点的指针

QueueInit(Q); //队列初始化队列中存放二叉树结点的指针

QueueIn(Qbt);

while(!QueueEmpty(Q)) //从上而下层次遍历

{p=QueueOut(Q); push(sp); //出队 入栈

if(p>lchild) QueueIn(Qp>lchild); //若左子女不空则入队列

if(p>rchild) QueueIn(Qp>rchild);} //若右子女不空则入队列

while(!StackEmpty(s)) {p=pop(s); printf(p>data);} //自下而上从右到左的层次遍历

}//if(bt!=null)

} //结束InvertLevel

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []