二叉树 前 后 中序遍历， 按层遍历， 求高度， 交换左右儿子等

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <queue>

using namespace std;
typedef struct node
{
    char data;
    bool flag;
    struct node *left, *right;
}Node;
int level[50];
int hight;

Node *createTree() {

    Node *Root;
    char ch = getchar();
    if(ch == ' ') {

        Root = NULL;
    }
    else {

        Root = (Node*)malloc(sizeof(Node));
        Root->data = ch;
        Root->left = createTree();
        Root->right =createTree();
    }
    return Root;
}

void preOrder(Node *t) {

     stack<Node*>s;
     Node *temp;
     while(t!= NULL || !s.empty())
     {
         while(t!= NULL)
         {
             printf("%c ", t->data);
             s.push(t);
             t = t->left;
         }
         if(!s.empty())
         {
             temp = s.top();
             s.pop();
             t = temp->right;
         }
     }
}

void inOrder(Node *t) {

     Node *temp;
     stack<Node*>s;
     while(t != NULL || !s.empty()) {

        while(t != NULL) {

            s.push(t);
            t = t->left;
        }
        if(!s.empty()) {

            temp = s.top();
            printf("%c ", temp->data);
            s.pop();
            t = temp->right;
        }
     }
}

void postOrder(Node *t) {

       Node *temp;
       stack<Node*>s;

       while(t != NULL || !s.empty()) {

             while(t != NULL) {
                t->flag = true;
                s.push(t);
                t = t->left;
             }
             if(!s.empty()) {

                temp = s.top();
                s.pop();
                if(temp->flag) {

                    temp->flag = false;
                    s.push(temp);
                    t = temp->right;
                }
                else {

                    printf("%c ", temp->data);
                }
             }
       }
}

void levelOrder(Node *t) {


     queue<Node*>s;
     if(t) {

        printf("%c ", t->data);
        s.push(t);
        while(!s.empty())
        {
            t = s.front();
            s.pop();
            if(t->left)
            {
                printf("%c ", t->left->data);
                s.push(t->left);
            }
            if(t->right)
            {
                printf("%c ", t->right->data);
                s.push(t->right);
            }
        }
     }
}

void countBreet(Node *t, int l, int level[]) {

         if(t) {

            level[l]++;
            countBreet(t->left, l+1, level);
            countBreet(t->right, l+1, level);
         }
}

int Breethight(Node *t) {

    int h1, h2;
    if(t == NULL)
    {
        return 0;
    }
    else
    {
        h1 = Breethight(t->right);
        h2 = Breethight(t->left);
        return h2 = max(h1, h2) + 1;
    }

}

Node *copyTreet(Node *t) {


     if(t == NULL)
        return NULL;

         Node *Root2 = (Node*)malloc(sizeof(Node));
         Root2->data = t->data;
         Root2->left =copyTreet(t->left);
          Root2->right=copyTreet(t->right);

     return Root2;
}

void exchange(Node *t)
{
    if(t)
    {
        exchange(t->left);
        exchange(t->right);
        swap(t->left, t->right);
    }
}

int main()
{
    Node *Root = NULL;
    printf("用字符表示飞空节点 ， 有空格表示此节点为空；\n");
    printf("例如你可以输入ABE^^EG^^^CF^^^回车得到结果 ^表示输入的数空格\n");
    printf("创建二叉树\n");
    Root = createTree();
   printf("二叉树的非递归前序遍历！\n\n");
    preOrder(Root);
    printf("\n二叉树的非递归中序遍历 ！\n\n");
    inOrder(Root);
    printf("\n二叉树的非递归后序遍历！\n\n");
    postOrder(Root);
    printf("二叉树按层遍历！\n\n");
    levelOrder(Root);
    printf("求二叉树高度！\n\n");
    hight = Breethight(Root);
    printf("二叉树的高度是：%d\n", hight);
    printf("求二叉树每层节点数 ！\n");
    countBreet(Root, 1, level);
    for(int i = 1; i <= hight; i++) {
        printf("第 %d 层节点数： %d\n", i, level[i]);
    }
    Node *Root2 = NULL;
    Root2 = copyTreet(Root);
     printf("复制后二叉树的非递归前序遍历！\n\n");
    preOrder(Root2);
       printf("\n将复制后的二叉树的左右儿子交换\n");
      exchange(Root2);
       printf("交换左右儿子后二叉树的非递归前序遍历！\n\n");
       preOrder(Root2);
    return 0;
}