二叉树遍历以及二叉树打印-数据结构实验

/*
input:ABC#D##EF###G#H##

output:

pre  : A B C D E F G H
in   : C D B F E A G H
post : D C F E B H G A
level: A B G C E H D F

               A
           /      \
        B             G
      /  \              \
    C      E              H
     \    /
      D  F

*/

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;

struct ss{
    char ch;
    ss* left=NULL;
    ss* right=NULL;
    ss(){
        ch='.';
        left=NULL;
        right=NULL;
    }
};

void createBiTree(ss* &root)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#'){
        root = NULL;
    }else{
        //root=(ss *) malloc(sizeof(ss));

        root->ch=ch;
        root->left=(ss *) malloc(sizeof(ss));
        root->right=(ss *) malloc(sizeof(ss));

        createBiTree(root->left);
        createBiTree(root->right);
    }
}

void pre(ss *root)
{
    if(root)
    {
        cout<<root->ch<<" ";
        pre(root->left);
        pre(root->right);
    }
}
void in(ss *root)
{
    if(root)
    {
        in(root->left);
        cout<<root->ch<<" ";
        in(root->right);
    }
}
void post(ss *root)
{
    if(root)
    {
        post(root->left);
        post(root->right);
        cout<<root->ch<<" ";
    }
}

void level(ss *root)
{
    queue<ss> Q;
    Q.push(*root);
    while(!Q.empty())
    {
        cout<<Q.front().ch<<" ";
        root=&Q.front();
        if(root->left) Q.push(*root->left);
        if(root->right) Q.push(*root->right);
        Q.pop();
    }
}

int tree[100][1000];
int ceng=0;
int step[1000];
HANDLE hOut;
#define move(y,x) SetConsoleCursorPosition(hOut,{x,y})

int deep=0;

void print(ss &root,int ceng,int pos,int l,int r)
{
    deep=max(deep,ceng+1);
    move((short int)ceng,(short int)pos);
    cout<<root.ch;
    if(root.left) 
    {
        int mid=(l+pos)/2;
        move((short int)ceng+1,(short int)(mid+pos)/2);
        cout<<'/';
        print(*root.left,ceng+2,mid,l,pos);
    } 
    if(root.right) 
    {
        int mid=(r+pos)/2;
        move((short int)ceng+1,(short int)(mid+pos)/2);
        cout<<'\\';
        print(*root.right,ceng+2,mid,pos,r);
    }
}

int main()
{
    //freopen("in.txt","r",stdin); 
    ss root;
    ss *p;
    p = &root;
    createBiTree(p);

    //获得屏幕的尺寸。
    hOut=GetStdHandle(STD_OUTPUT_HANDLE);

    //move(12,12);

    //print(root)

    cout<<"pre  : ";pre(p);cout<<endl;

    cout<<"in   : ";in(p);cout<<endl;

    cout<<"post : ";post(p);cout<<endl;

    cout<<"level: ";level(p);cout<<endl;

    int width=30;

    print(root,5,width/2,1,width);
    move(deep,0);
    return 0;
}

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注