该文章创建(更新)于12/2/2018，请注意文章的时效性！

可以观看一个视频来了解具体过程，我感觉讲的很好！
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;
}

要不赞赏一下?

微信

支付宝

PayPal

Bitcoin