[数据结构与算法]既可以实现二叉树树的先序、中序、后序的递归遍历，又可以实现非递归遍历。实现二叉树的层次遍历并找到叶子结点树。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MAX 1024
using namespace std;
int leafCout=0;

typedef struct Tree
{
? ? int data;
? ? struct Tree *lchild;
? ? struct Tree *rchild;
}Tree,*BiTree;
BiTree CreatTree()
{
? ? int elem;
? ? cin>>elem;
? ? BiTree T;
? ? if(elem==-1)
? ? {
? ? ? ? return NULL;
? ? }
? ? else
{
? ? T=(BiTree)malloc(sizeof(Tree));
? ? T->data=elem;
? ? cout<<elem<<"的左子树";
? ? T->lchild=CreatTree();
? ? cout<<elem<<"的右子树";
? ? T->rchild=CreatTree();
}
return T;
}
void Levle(BiTree T)
{
? ? BiTree Queue[MAX];
? ? BiTree p;
? ? int front=0,rear=0;
? ? if(T)
? ? {
? ? ? ? Queue[rear++]=T;
? ? ? ? while(front!=rear)
? ? ? ? {
? ? ? ? ? ? p=Queue[front++];
? ? ? ? ? ? cout<<p->data;
? ? ? ? ? ? if(p->lchild!=NULL) Queue[rear++]=p->lchild;
? ? ? ? ? ? if(p->rchild!=NULL) Queue[rear++]=p->rchild;
? ? ? ? }
? ? }
}
void LeafCoutBinaryCout(BiTree node)
{
? ? if(node==NULL)
? ? {
? ? ? ? return;
? ? }
? ? if(node->lchild==NULL&&node->rchild==NULL)
? ? {
? ? ? ? leafCout++;
? ? }
? ? LeafCoutBinaryCout(node->lchild);
? ? LeafCoutBinaryCout(node->rchild);
? ? return;
}
void xian(BiTree T)
{
? ? if(T==NULL)
? ? {
? ? ? ? return;
? ? }
? ? cout<<T->data;
? ? xian(T->lchild);
? ? xian(T->rchild);
}
void zhong(BiTree T)
{
? ? if(T==NULL)
? ? {
? ? ? ? return;
? ? }
? ? xian(T->lchild);
? ? cout<<T->data;
? ? xian(T->rchild);
}
void hou(BiTree T)
{
? ? if(T==NULL)
? ? {
? ? ? ? return;
? ? }
? ? xian(T->lchild);
? ? xian(T->rchild);
? ? cout<<T->data;
}
void preOrder(BiTree root)//非递归实现先序遍历二叉树
{
? ? BiTree stack[MAX];
? ? BiTree node;
? ? int k=-1;
? ? if(root==NULL)
? ? {
? ? ? ? cout<<"empty";
? ? ? ? return;
? ? }
? ? else
? ? {
? ? ? ? k++;
? ? ? ? stack[k]=root;
? ? ? ? while(k>-1)
? ? ? ? {
? ? ? ? ? ? node=stack[k--];
? ? ? ? ? ? cout<<node->data;
? ? ? ? ? ? if(node->rchild!=NULL){
? ? ? ? ? ? ? ? stack[++k]=node->rchild;
? ? ? ? ? ? }
? ? ? ? ? ? if(node->lchild!=NULL){
? ? ? ? ? ? ? ? stack[++k]=node->lchild;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
void inOrder(BiTree root)
{
? ? BiTree stack[MAX];
? ? BiTree node;
? ? int top=0;
? ? if(root==NULL)
? ? {
? ? ? ? cout<<"empty";
? ? ? ? return;
? ? }
? ? node=root;
? ? while(node!=NULL||top>0)
? ? {
? ? ? ? while(node!=NULL)
? ? ? ? {
? ? ? ? ? ? stack[++top]=node;
? ? ? ? ? ? node=node->lchild;
? ? ? ? }
? ? ? ? node=stack[top--];
? ? ? ? cout<<node->data;
? ? ? ? node=node->rchild;
? ? }
}
int main()
{
? ? BiTree T;
? ? cout<<"请输入第一个结点的数据：";
? ? T=CreatTree();
? ? cout<<"先序遍历：";
? ? xian(T);
? ? cout<<"中序遍历：";
? ? zhong(T);
? ? cout<<"后序遍历：";
? ? hou(T);
? ? LeafCoutBinaryCout(T);
? ? cout<<endl;
? ? cout<<"输出叶子结点个数:";
? ? cout<<leafCout;
? ? cout<<"输出层次遍历：";
? ? Levle(T);
? ? cout<<"非递归先序：";
? ? preOrder(T);
? ? cout<<"非递归中序遍历：";
? ? inOrder(T);

? ? return 0;
}