전차순(후차순)을 통해 중차순 역행 두 갈래 트리 구해 차원 역행

2422 단어 두 갈래 나무
제목 링크
두 갈래 나무의 구축은 앞뒤를 두루 훑어보든 차원을 두루 훑어보든 모두 중차례 훑어보는 성질과 한 차례 앞뒤를 두루 훑어보든 뒷뒤를 두루 훑어보든 한 노드의 왼쪽 모든 수, 오른쪽 모든 수와 이 노드의 수를 분리한 다음에 제목에 따라 다시 정렬한다.
앞의 순서 반복: 이 노드의 수, 왼쪽 지수, 오른쪽 지수;
중서 역력: 왼쪽 지수, 이 노드의 수, 오른쪽 지수;
뒷차례 두루 훑어보다.왼쪽 지수, 오른쪽 지수, 이 노드의 수
(앞의 순서는 노드의 수가 항상 그의 왼쪽 지렛대와 오른쪽 지렛대에서 앞을 지렛대 (먼저 왼쪽 지렛대 뒤의 오른쪽 지렛대) 이다.후차적 역력은 노드의 수가 그 좌지의 수와 우지의 수를 모두 역력하고 후차적 역력하는 것이다.중서는 왼쪽 지렛대, 노드 지렛대, 오른쪽 지렛대 이 순서를 정말 몰라요?
다른 것은 부호 이상의 문제를 추측하여 모두 해결할 수 있다
#include
#include
#include
#include

using namespace std;

struct tree
{
    char key;
    tree *left;
    tree *right;
};

tree *creat(string pre,string mid)//   
{

    if(pre.size()<=0)
    {
        return NULL;
    }
    tree *p;
    p=new tree[1];
    p->key=pre[0];
    int pos=mid.find(pre[0]);
    p->left=creat(pre.substr(1,pos),mid.substr(0,pos));
    int len=mid.size()-pos-1;
    p->right=creat(pre.substr(pos+1,len),mid.substr(pos+1,len));
    return p;
}

int print_mid(tree *ROOT)// 
{
    if(ROOT==NULL)
    {
        return 0;
    }
    print_post(ROOT->left);
    cout << ROOT->key;
    print_post(ROOT->right);
    return 0;
}

int print_post(tree *ROOT)// 
{

    if(ROOT==NULL)
    {
        return 0;
    }
    print_post(ROOT->left);
    print_post(ROOT->right);
    cout << ROOT->key;
    return 0;


}

int print_forth(tree *ROOT)// 
{
    if(ROOT==NULL)
    {
        return 0;
    }
    cout << ROOT->key;
    print_post(ROOT->left);
    print_post(ROOT->right);
    return 0;
}

int PrintByLevel(tree *ROOT)// ( )
{
    tree *temp[100];// 
    int j;
    for(j=0;j<100;j++)
    {
        temp[j]=NULL;
    }
    temp[0]=ROOT;//    
    j=0;
    int t=1;
    while(temp[j]!=NULL)
    {
        if(temp[j]->left!=NULL)//       ;
        {
            temp[t++]=temp[j]->left;
        }
        if(temp[j]->right!=NULL)
        {
            temp[t++]=temp[j]->right;
        }
        cout<key;
        j++;
    }
}


int main()
{
    string pre_order;
    string post_order;
    int n;cin>>n;
    while(n--)
    {
        tree *root;
        cin>>pre_order>>post_order;
        root=creat(pre_order,post_order);
        print_post(root);
        cout<

좋은 웹페이지 즐겨찾기