可以观看一个视频来了解具体过程,我感觉讲的很好!
Youtube视频教程
在Github数据结构代码,比如我的:Github
#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;
}