二叉树基础操作

#include<bits/stdc++.h>
#define maxsize 100
using namespace std;
typedef struct node
{//定义二叉树结构
    char data;
    struct node *lchild,*rchild;
}*bitree,bitnode;

void createbitree(bitree &t)
{//先序创建二叉树
    char ch;
    cin>>ch;
    if(ch=='#') t=null;
    else{
        t=new bitnode;
        t->data=ch;
        createbitree(t->lchild);
        createbitree(t->rchild);
    }
}
//层序遍历
void levelordertraversal(bitree bt){
    queue<bitree> q;
    if(!bt)return;
    q.push(bt);
    while(!q.empty()){
        bitnode *q = q.front();
        cout<<q->data;
        q.pop();
        if(q->lchild)
            q.push(q->lchild);
        if(q->rchild)
            q.push(q->rchild);
    }
}
void inordertraverse(bitree t)
{//中序遍历
    if(t)
    {
        inordertraverse(t->lchild);
        cout<<t->data;
        inordertraverse(t->rchild);
    }
}
void preordertraverse(bitree t)
{//先序遍历
    if(t)
    {
        cout<<t->data;
        preordertraverse(t->lchild);
        preordertraverse(t->rchild);
    }
}
void postordertraverse(bitree t)
{//后序遍历
    if(t)
    {
        postordertraverse(t->lchild);
        postordertraverse(t->rchild);
        cout<<t->data;
    }
}
void copy(bitree t,bitree &newt)
{//二叉树的复制
    if(t==null){
        newt=null;
        return;
    }else
    {
        newt=new bitnode;
        newt->data=t->data;
        copy(t->lchild,newt->lchild);
        copy(t->rchild,newt->rchild);
    }
}
int depth(bitree t)
{//树的深度
    if(t==null)
        return 0;
    else
    {
        int m=depth(t->lchild);
        int n=depth(t->rchild);
        if(m>n) return (m+1);
        else return (n+1);
    }
}
int nodecount(bitree t)
{//统计二叉树中结点的个数
    if(t==null) return 0;
    else return nodecount(t->lchild)+nodecount(t->rchild)+1;
}
int leafcount(bitree t)
{//统计二叉树中叶子结点的个数
    if(!t) return 0;
    if(!t->lchild &&!t->rchild){//如果二叉树左子树和右子树皆为空,说明该二叉树根节点为叶子节点,加1.
        return 1;
    }else{
        return leafcount(t->lchild)+leafcount(t->rchild);
    }
}
int node_1_count(bitree t)
{//统计二叉树的度为1的结点个数
    if(!t) return 0;
    if((!t->lchild)&&(t->rchild)||(t->lchild)&&(!t->rchild))
        return 1;
    else
        return leafcount(t->lchild)+leafcount(t->rchild);
}
void printallpath(bitree t, char path[], int pathlen)
{//二叉树中从每个叶子结点到根结点的路径
    int i;
    if(t != null) {
        path[pathlen] = t->data; //将当前结点放入路径中
        if(t->lchild == null && t->rchild == null) {//叶子结点
            for(i = pathlen; i >= 0; i--)
                cout << path[i] << " " ;
            cout << endl;
        }else{
            printallpath(t->lchild, path, pathlen + 1);
            printallpath(t->rchild, path, pathlen + 1);
        }
    }
}
void exchangetree(bitree &t)
{//构造函数，使用递归算法进行左右结点转换
    bitree temp;
    if(t!=null){//判断t是否为空，非空进行转换，否则不转换
        temp=t->lchild;
        t->lchild=t->rchild;//直接交换节点地址
        t->rchild=temp;
        exchangetree(t->lchild);
        exchangetree(t->rchild);
    }
}
void dblordertraverse(bitree t)
{//二叉树的双序遍历
    if(t)
    {
        cout<<t->data;
        dblordertraverse(t->lchild);
        cout<<t->data;//访问两遍
        dblordertraverse(t->rchild);
    }
}
int main()
{
    bitree t;
    //测试例子ab#cd##e##f#gh###
    cout<<"先序遍历输入(以#结束):";
    createbitree(t);
    cout<<"中序遍历输出:";
    inordertraverse(t);
    cout<<endl<<"先序遍历输出:";
    preordertraverse(t);
    cout<<endl<<"后序遍历输出:";
    postordertraverse(t);
    cout<<endl<<"层序遍历输出:";
    levelordertraversal(t);
    cout<<endl<<"树的深度:"<<depth(t);
    cout<<endl<<"结点的个数:"<<nodecount(t);
    cout<<endl<<"叶结点的个数:"<<leafcount(t);
    cout<<endl<<"度为1的结点个数:"<<node_1_count(t);
    cout<<endl<<"二叉树中从每个叶子结点到根结点的所有路径："<<endl;
    char path[256];
    int pathlen=0;
    printallpath(t,path,pathlen);//
    //交换二叉树每个结点的左孩子和右孩子
    bitree tem=t;//直接复制一颗树，在不改变原树的前提下，对临时树进行交换。
    exchangetree(tem);
    cout<<"先序遍历输出交换后的结果:";
    preordertraverse(tem);
    cout<<endl<<"双序遍历输出:";
    dblordertraverse(t);
    return 0;
}