二叉树操作1.txt

实现二叉树的前序非递归遍历和比较两棵二叉树是否相似的算法。

6.37③ 试直接利用栈的基本操作写出先序遍历的非递归 
形式的算法(提示:不必按3.3.2节介绍的从递归到非递归 
的方法而直接写出非递归算法)。 
要求实现下列函数： 
void PreOrder(BiTree bt, void (*visit)(TElemType)); 
/* 使用栈，非递归先序遍历二叉树bt，    */ 
/* 对每个结点的元素域data调用函数visit */ 
二叉链表类型定义： 
typedef struct BiTNode { 
    TElemType data; 
    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); 
{Stack S; 
InitStack(S); 
BiTree p; 
if(!bt) return ; 
p=bt; 
while(p||!StackEmpty(S))  /*非空或者不是叶子*/ 
  {if(p) 
   {visit(p->data); 
    Push(S,p); 
    p=p->lchild;} 
   else 
   {Pop(S,p); 
    p=p->rchild; 
   } 
  } 
  return ; 
}