二叉树的建立以及各种操作

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
typedef struct BinTreeNode
{
    char data;
    struct BinTreeNode *lchild;
    struct BinTreeNode *rchild;
} BinTreeNode,*BITree;

int FindComma(char s[], int len)
{
    int match = 0;
    int i;
    for(i = 0; i < len; i++)
    {
        if(s[i] == '(')
            ++match;
        else if(s[i] == ')')
            --match;
        if(match==0 && s[i]==',')
            break;
    }
    return i;
}
BITree Create(char s[], int len)
{
    if(s[0] == '#')
        return NULL;
    BITree root = (BITree)malloc(sizeof(BinTreeNode));
    root->data = s[0];
    if(len == 1)
    {
        root->lchild = NULL;
        root->rchild = NULL;
    }
    else
    {
        int commaPos = FindComma(s+2, len-2);
        root->lchild = Create(s+2, commaPos);
        root->rchild = Create(s+2+commaPos+1,len-3-commaPos-1);
    }
    return root;
}
void LevelPrint(BITree T)
{
    queue<BITree>q;
    if(T==NULL)return;
    BITree p = T;
    q.push(p);
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        if(p->data != '#')
            printf("%c ",p->data);
        if(p->lchild)
            q.push(p->lchild);
        if(p->rchild)
            q.push(p->rchild);
    }
    printf("
");
}
void preOrderTraverse(BITree T,int level)
{
    if(T==NULL)return;
    else
    {
        printf("%c ",T->data);//先序遍历，意思是我先跑根节点，再跑左节点，再跑右节点
        preOrderTraverse(T->lchild,level+1);
        preOrderTraverse(T->rchild,level+1);
    }
}
void OrderTraverse(BITree T,int level)
{
    if(T==NULL)return;
    else
    {
        OrderTraverse(T->lchild,level+1);
        printf("%c ",T->data);//中序遍历，意思是我先跑左节点再根，再右节点，再根
        OrderTraverse(T->rchild,level+1);
    }
}
void PostorderTraverse(BITree T,int level)
{
    if (T==NULL)return;
    else
    {
        PostorderTraverse(T->lchild,level+1);
        PostorderTraverse(T->rchild,level+1);
        printf("%c ",T->data);//后序遍历，意思是我先跑左节点，再右节点，再根。
    }
}
void preOrder2(BITree root)     //非递归前序遍历
{
    stack<BITree> s;
    BITree p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}
void inOrder2(BITree root)      //非递归中序遍历
{
    stack<BITree> s;
    BITree p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<" ";
            s.pop();
            p=p->rchild;
        }
    }
}
void postOrder3(BITree root)     //非递归后序遍历
{
    stack<BITree> s;
    BITree cur;                      //当前结点
    BITree pre=NULL;                 //前一次访问的结点
    s.push(root);
    while(!s.empty())
    {
        cur=s.top();
        if((cur->lchild==NULL&&cur->rchild==NULL)||
                (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
        {
            cout<<cur->data<<" ";  //如果当前结点没有孩子结点或者孩子节点都已被访问过
            s.pop();
            pre=cur;
        }
        else
        {
            if(cur->rchild!=NULL)
                s.push(cur->rchild);
            if(cur->lchild!=NULL)
                s.push(cur->lchild);
        }
    }
}
int Depth(BITree T)
{
    int m,n;
    if(T == NULL ) return 0;        //如果是空树，深度为0，递归结束
    else
    {
        m=Depth(T->lchild);            //递归计算左子树的深度记为m
        n=Depth(T->rchild);            //递归计算右子树的深度记为n
        if(m>n) return(m+1);        //二叉树的深度为m 与n的较大者加1
        else return (n+1);
    }
}
int NodeCount(BITree T)
{
    if(T==NULL)return 0;
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int getWidth(BITree root)
{
    if(!root)
    {
        return 0;
    }
    int width = 0;
    int maxWidth = 0;
    queue<BITree> Q;
    BITree p = nullptr;
    Q.push(root);
    while(!Q.empty())
    {
        width = Q.size();
        if(maxWidth < width)
        {
            maxWidth = width;
        }
        for(int i=0; i<width; i++)
        {
            p = Q.front();
            Q.pop();
            if(p->lchild)
            {
                Q.push(p->lchild);
            }
            if(p->rchild)
            {
                Q.push(p->rchild);
            }
        }
    }
    return maxWidth;
}
void ReverseLeftRightChild(BITree *T)
{
    if (*T == NULL)
    {
        return;
    }

    swap((*T)->lchild, (*T)->rchild); // 直接使用swap交换函数比较方便，直接交换指针；
    ReverseLeftRightChild(&((*T)->lchild));
    ReverseLeftRightChild(&((*T)->rchild));
}
int main()
{
    char str[200];
    scanf("%s",&str);
    BITree root;
    root = (BITree)malloc(sizeof(BinTreeNode));
    root = Create(str, strlen(str));
    printf("按照层次遍历
");
    LevelPrint(root);
    printf("
");
    printf("按照先序遍历:
");
    printf("递归写法
");
    preOrderTraverse(root,1);
    printf("
");
    printf("非递归写法:
");
    preOrder2(root);
    printf("
");
    printf("按照中序遍历
");
    printf("递归写法:
");
    OrderTraverse(root,1);
    printf("
");
    printf("非递归写法:
");
    inOrder2(root);
    printf("
");
    printf("按照后序遍历:
");
    printf("递归写法
");
    PostorderTraverse(root,1);
    printf("
");
    printf("非递归写法
");
    postOrder3(root);
    printf("
");
    printf("树的深度为:%d
",Depth(root));
    printf("树的节点数目为:%d
",NodeCount(root));
    printf("树的宽度为%d
",getWidth(root));
    printf("
");

    printf("交换树的左右儿子
");
    ReverseLeftRightChild(&root);
    printf("交换后的按层遍历的顺序为:
");
    LevelPrint(root);
    return 0;
}
/*
A(B(D(H,#),E(#,I)),C(F(#,J),G(K,#)))
*/