二叉树的递归、非递归的先序、中序、后序遍历以及层次遍历和求叶子节点数

}

}

return OK; }

//非递归中序遍历二叉树

Status InOrderTraverse(BiTree T) {

//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit,也就是printf()函数

SqStack S; InitStack(S); BiTree p; p = T; /**/

while(p || !StackEmpty(S)) { if(p) {

Push(S,p);

p = p->lchild; //根指针进栈，遍历左子树 } else

{ //根指针退栈，访问根结点，遍历右子树 Pop(S,p);

printf(\ p = p->rchild; }

}//while

/*和上面的while开始的操作完全等同，可以视为方法二： Push(S,p);

while (!StackEmpty(S)) {

while (GetTop(S,p) && p) {

Push(S,p->lchild); }

Pop(S,p);

if (!StackEmpty(S)) {

Pop(S,p);

printf(\ Push(S,p->rchild);

}

} */

return OK;

} //InOrderTraverse /**/

//非递归后序遍历二叉树 ：

Status LastOrderTraverse(BiTree T) {

//后序遍历时，分别从左子树和右子树共两次返回根结点，

//只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。 SqStack s,tag;//定义两个栈，一个是存储二叉树结点的栈，一个是存储标志位的栈

//stack2 tag ;

BiTree f,m,n,P=T; //m，n是标志位。f是中间变量，用于检测标志位是m还是n的

m=(BiTNode*)malloc(sizeof(BiTNode)); //注意：此处必须先创建结点，然后再赋值

m->data=1;

m->lchild=NULL; m->rchild=NULL;

n=(BiTNode*)malloc(sizeof(BiTNode));//注意：此处必须先创建结点，然后再赋值

n->data=2;

n->lchild=NULL; n->rchild=NULL;

InitStack(s);//此栈用来存放结点

InitStack(tag);//此栈用来存放标志位，从左子树返回根节点时为1，从右子树返回根节点时为2

while (P ||!StackEmpty(s)) { if (P) {

Push(s,P);

Push(tag,m);//第一次入栈操作 P=P->lchild; } else {

Pop(s,P); Pop(tag,f); if (f==m)

{

// 从左子树返回，二次入栈，然后p转右子树 Push(s,P);

Push( tag, n);//第二次入栈 P=P->rchild; } else {

// 从右子树返回(二次出栈)，访问根结点，p转上层 printf(\

P=NULL; // 必须的，使下一步继续退栈 } } }

return OK; }

//初始化一个带头结点的队列 Status InitQueue(LinkQueue &Q) {

Q.front=(QNode*)malloc(sizeof(QNode)); if (!Q.front)

exit(OVERFLOW); Q.rear=Q.front;

Q.front->next=NULL; return OK; }

//入队列

Status EnQueue(LinkQueue &Q,BiTree e) {

QueuePtr s=(QueuePtr)malloc(sizeof(QNode)); if (!s)

exit(OVERFLOW); s->Queuedata=e; s->next=NULL; Q.rear->next=s; Q.rear=s; return OK; }

//出队

int DelQueue(LinkQueue &Q, BiTree &e) {

char data1; QueuePtr s;

s=Q.front->next;//注意：该队列为带头结点，所以刚开始出队列时，应该去front的next

e=s->Queuedata;//获取对头记录的数据域，类型为BiTree data1=e->data;//获取BiTree类型的数据域，类型为char Q.front->next=s->next;

if(Q.rear==s)//队列中只有一个元素 Q.rear=Q.front; free(s);

return TRUE; }

//队列的判断空操作

Status QueueEmpty(LinkQueue Q) {

//队列带头结点，所以需要判断Q.front->next if (Q.front->next==NULL) return OK;

else return ERROR;

}

//按层次遍历

Status HierarchyBiTree(BiTree bt) {

LinkQueue Q; // 保存当前节点的左右孩子的队列

InitQueue(Q); // 初始化队列

BiTree p = bt; // 临时保存树根Root到指针p中 if (bt == NULL) return ERROR; //树为空则返回

EnQueue(Q,p); //先将根节点入队列

while (!QueueEmpty(Q)) // 若队列不空，则层序遍历 { DelQueue(Q, p); // 出队列

printf(\访问当前节点

if (p->lchild)

EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列 if (p->rchild)

EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列 }

//DelQueue(Q,p); // 释放队列空间 return OK;