树与二叉树的常见操作

实验内容：

    1．输入字符序列，建立二叉链表。

    2．前序，中序，后序遍历二叉树:递归算法。

    3．中序遍历二叉树:非递归算法。

    4．求二叉树的高度 。

    5．求二叉树的叶子个数。

    6．借助队列实现二叉树的层次遍历。 

    7．在主函数中设计一个简单的菜单，分别调试上述算法。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
struct binode
{
    char data;
    binode *l,*r;
};
binode *create(binode *T)///建树
{
    char x;
    cin>>x;
    if(x=='@')T=NULL;
    else
    {
        T=(binode*)malloc(sizeof(binode));
        T->data=x;
        T->l=create(T->l);
        T->r=create(T->r);
    }
    return T;
}
void postorder( binode *T )///递归实现后序遍历
{
    if ( T != NULL )
    {
        postorder ( T->l);
        postorder ( T->r);
        printf("%c ",T->data);
    }
}
void preorder(binode *T)///递归实现前序遍历
{
    if (T != NULL)
    {
        printf("%c ",T->data);
        preorder ( T->l);
        preorder ( T->r);
    }
}
void midorder( binode * T )///递归实现中序遍历
{
    if ( T != NULL )
    {
        midorder ( T->l);
        printf("%c ",T->data);
        midorder ( T->r);
    }
}

void mid(binode *T)///非递归实现中序遍历
{
    stack<binode*>s;
    binode *p=T;
    while(p||!s.empty())
    {
        if(p)
        {
            s.push(p);
            p=p->l;
        }
        else
        {
            p=s.top();
            s.pop();
            cout<<p->data<<' ';
            p=p->r;
        }
    }
}

int deep(binode*T)///求树的高度
{
    int s=1;
    if(T!=NULL)
    {
        int max0=0;
        if(T->l!=NULL)
            max0=max(max0,deep(T->l));
        if(T->r!=NULL)
            max0=max(max0,deep(T->r));
        s+=max0;
    }
    return s;
}

int yezi(binode*T)///求叶子树
{
    int s=0;
    if(T->l!=NULL)
        s+=yezi(T->l);
    if(T->r!=NULL)
        s+=yezi(T->r);
    if(T->l==NULL&&T->r==NULL)
        s=1;
    return s;
}
queue<binode*>q;
void cengcibianli(binode*T)///队列实现层次遍历
{
    if(T!=NULL)
    {
        if(T->l!=NULL)
            q.push(T->l);
        if(T->r!=NULL)
            q.push(T->r);
        cengcibianli(T->l);
        cengcibianli(T->r);
    }
}

int main()
{
    binode *a=NULL;
    a=create(a);
    cout<<"递归实现中序遍历:"<<endl;
    midorder(a);
    cout<<endl;
    cout<<"递归实现后序遍历:"<<endl;
    postorder(a);
    cout<<endl;
    cout<<"递归实现前序遍历:"<<endl;
    preorder(a);
    cout<<endl;
    cout<<"非递归实现中序遍历"<<endl;
    mid(a);
    cout<<endl;
    cout<<"树的高度为："<<endl;
    cout<<deep(a)<<endl;
    cout<<"树的叶子数为："<<endl;
    cout<<yezi(a)<<endl;
    cout<<"树的层次遍历："<<endl;
    q.push(a);
    cengcibianli(a);
    while(!q.empty())
        cout<<q.front()->data<<' ',q.pop();

    return 0;
}