``````#include<stdio.h>
#include<iostream>
using namespace std;

#define OVERFLOW -1
#define OK 1
#define ERROE -2
#define MaxSize 100

typedef struct BiTNode{ //二叉树的二叉链表存储结构
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreatTree(BiTree &T)//先序序列构造二叉树,递归思想
{
char m;
scanf("%c",&m); //单个字符输入
if ( m == ' ')
T = NULL;
else
{
if( !(T = (BiTNode *) malloc (sizeof(BiTNode) ) ) )
exit(OVERFLOW);
T->data = m;
CreatTree(T->lchild);
CreatTree(T->rchild);
}
}

void PreOrderTraverse(BiTree T)//递归，先序遍历
{
if( T != )
{
cout << T->data << " ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

void Display(BiTree T,int &i)//递归判断输出叶子节点//即在先序遍历上多了一个判断左右孩子是否同时为空即可;
{
if(T != NULL)
{
if( ! T->lchild && ! T->rchild )
{
cout << T->data << " ";
i++;
}
Display(T->rchild,i);
}
}

void InOrderTraverse(BiTree T)//递归，中序遍历
{
if( T != NULL)
{
InOrderTraverse(T->lchild);
cout << T->data << " ";
InOrderTraverse(T->rchild);
}
}

void PostOrderTraverse(BiTree T)//递归，后序遍历
{
if( T != NULL)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data << " ";
}
}

int Visit(char e)
{
cout << e;
return OK;
}

//中序非递归算法,类似栈的方式;
void InOrder2(BiTNode *b)
{
BiTNode *St[MaxSize],*p;
int top = -1;
p = b; //把根的地址给p;
while (top > -1 || p != NULL)
{
while (p != NULL) //扫描*p的所有左结点并进栈
{
top++; //top在此地不断的增加
St[top] = p;
p = p->lchild; //关键点
}

if (top > -1)
{
p = St[top];
top--; //出栈*p结点
printf("%c ",p->data); //访问之
p = p->rchild; //扫描*p的右孩子结点####此时p为St[top]
}
}
}

void CenciTraverse(BiTree T)
{
cout << T->data;
}

//×××××××××层次遍历
void LevelOrder(BiTree b)
{
BiTNode *p;
BiTNode *qu[MaxSize]; /*定义环形队列,存放结点指针*/
int front,rear; /*定义队头和队尾指针*/
front=rear=-1; /*置队列为空队列*/
rear++;
qu[rear]=b; /*根结点指针进入队列*/

while (front != rear) /*队列不为空*/
{
front=(front+1)%MaxSize;
p = qu[front]; /*队头出队列*/
printf("%c ",p->data); /*访问结点*/

if (p->lchild!=NULL) /*有左孩子时将其进队*/
{
rear=(rear+1)%MaxSize;
qu[rear]=p->lchild;
}

if (p->rchild!=NULL) /*有右孩子时将其进队*/
{
rear=(rear+1)%MaxSize;
qu[rear]=p->rchild;
}
}
}

int main()
{
int m = 0;
BiTree T;
cout << "请输入先序序列（eg:ABC DE G F ）" << endl;
CreatTree(T);

cout << "先序:";
PreOrderTraverse(T);

cout << endl << "中序:";
InOrderTraverse(T);

cout << endl << "中序非递归算法:";
InOrder2(T);

cout << endl << "后序:";
PostOrderTraverse(T);

cout << endl << "层次遍历:";
LevelOrder(T);

cout << endl << "叶子节点：";
Display(T,m);

cout << endl << "叶子节点数：";
cout << m << endl;
return 0;
}
``````

# 👇 Share | 分享 👇

### 要不赞赏一下?

 微信 支付宝 PayPal Bitcoin

``https://www.emperinter.info/2018/12/02/%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e9%81%8d%e5%8e%86/``

## 优惠码

 阿里云国际版 20美元 Vultr 10美元 搬瓦工 | Bandwagon 应该有折扣吧？ Just My Socks JMS9272283 【注意手动复制去跳转】 域名 | namesilo `emperinter`(1美元) 币安 币安