的后序遍历算法(提示：为分辨后序遍历时两次进栈的 不同返回点，需在指针进栈时同时将一个标志进栈）。 二叉链表类型定义： typedef struct BiTNode { TElemType data;
struct BiTNode *lchild,*rchild; } 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 */ {
SElemType Q; Stack S; InitStack(S);
BiTree p = T,q = T; while(p != NULL) {
if((p->lchild==NULL)&&(p->rchild==NULL)) { //结点没有左右子树，tag标记1 Q.ptr = p; Q.tag = 1; Push(S, Q); }
if((p->lchild!=NULL)||(p->rchild!=NULL)) {
while(p!=NULL)
{//相当于根结点，标记tag为1，入栈 Q.ptr = p; Q.tag = 1; Push(S, Q);
if(p->rchild!=NULL)
{//右结点入栈，tag暂时为0 Q.ptr = p->rchild;
Q.tag = 0; Push(S,Q); }
p = p->lchild; }
}
if(StackEmpty(S)!=TRUE) {
do{ //直接对栈顶出栈，判断tag是否为1， //是则 输出p->data,继续出栈 //否则结束循环，执行后面语句 Pop(S, Q);
if(p==q) {p = NULL;break;} if(Q.tag==0) {
p = Q.ptr; break; }
p = Q.ptr; visit(p->data); }while(Q.tag==1); }
while(StackEmpty(S)!=TRUE&&
((p->lchild!=NULL&&p->rchild==NULL)||(p->lchild==NULL&&p->rchild!=NULL)))
{//当P指向的树是只有左或右子树是，用下面方法入栈 if(p->lchild!=NULL) { //P只有左子树 时 Q.ptr = p; Q.tag = 1; Push(S,Q); p = p->lchild; } else
{ //P只有右子树 时 Q.ptr = p; Q.tag = 1; Push(S,Q); p = p->rchild; } } } }
/**27********
【题目】二叉树采用三叉链表的存储结构，试编写 不借助栈的非递归中序遍历算法。 三叉链表类型定义： typedef struct TriTNode { TElemType data;
struct TriTNode *parent, *lchild, *rchild; } TriTNode, *TriTree; **********/
void InOrder(TriTree PT, void (*visit)(TElemType)) /* 不使用栈，非递归中序遍历二叉树PT， */ /* 对每个结点的元素域data调用函数visit */ {
TriTree p,pr; if(PT!=NULL) {
p = PT;
while(p!=NULL)
{ if(p->lchild==NULL) visit(p->data); //输出有右子树的结点 if(p->lchild) p = p->lchild; else
if(p->rchild) p = p->rchild; else {
do{
pr = p; p = p->parent;
if(p->rchild!=pr) //如果pr是p的右子树则不输出 visit(p->data);
}while(p!=NULL&&(p->rchild==pr||NULL==p->rchild)); if(p!=NULL) p = p->rchild; } } } }
/***29*******
【题目】假设在三叉链表的结点中增设一个标志域 (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 */ {
TriTree p,pr; if(T!=NULL) {
p = T;
while(p!=NULL) {
if(p->lchild) p = p->lchild; else
if(p->rchild) p = p->rchild; else { do{
pr = p;
visit(pr->data);
p = p->parent;
}while(p!=NULL&&(p->rchild==pr||NULL==p->rchild)); if(p!=NULL) p = p->rchild; } } } }
/**33********
【题目】编写递归算法，将二叉树中所有结点的 左、右子树相互交换。 二叉链表类型定义： typedef struct BiTNode { TElemType data;
struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/
void ExchangeSubTree(BiTree &T)
/* 将二叉树中所有结点的左、右子树相互交换 */ {
BiTree temp = NULL;
if(T==NULL) return ;
else if(T->lchild!=NULL||T->rchild!=NULL) {
temp = T->lchild;
T->lchild = T->rchild; T->rchild = temp;
}
ExchangeSubTree(T->lchild);
ExchangeSubTree(T->rchild); }
/****37**************************
void DepthxH(BiTree T,TElemType x , BiTree &A){ if(T==NULL)return ; if(T->data == x) { A = T; return ;}
DepthxH(T->lchild,x , A); DepthxH(T->rchild,x , A); }
int DepthxF(BiTree T){
int dl,dr;
if(T == NULL) return 0; else {
dl = DepthxF(T->lchild); dr = DepthxF(T->rchild); return 1+(dl>dr?dl:dr); } }
/**********
【题目】编写递归算法：求二叉树中以元素值 为x的结点为根的子树的深度。 二叉链表类型定义： typedef struct BiTNode {