数据结构-树-遍历合集

通常做题，遇到最多的是已知树的前序遍历和中序遍历 或者 中序遍历和后序遍历，求这棵树的遍历，可以确定的是，无论是哪种情况，必须确定树的中序遍历，如 图1-1树 所示：

以前序遍历和中序遍历举例，无疑前序遍历第一个元素就是各节点，但是无法确定的是那一边是右子节点，或者左子树的终点。那么可以从中序遍历开始，找到根节点，在其左边一定是左子节点，右边一定是右子节点，从而一次递推。中序遍历与后序遍历亦然。

已知前序遍历，表明空节点，求后序遍历与中序遍历：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>

using namespace std;

char a[100];
int shu;
struct node
{
    int data;
    struct node *l, *r;
};

struct node *create()
{
    struct node *root;
    char c;
    c = a[shu++];
    if(c == ',')
    {
        return NULL;
    }
    else
    {
        root = new struct node;
        root->data = c;
        root->l = create();
        root->r = create();
    }
    return root;
}

void before(struct node *root)
{
    if(root)
    {
        printf("%c", root->data);
        before(root->l);
        before(root->r);
    }
};

void mid(struct node *root)
{
    if(root)
    {
        mid(root->l);
        printf("%c", root->data);
        mid(root->r);
    }
}

void after(struct node *root)
{
    if(root)
    {
        after(root->l);
        after(root->r);
        printf("%c", root->data);
    }
}

int main()
{
    struct node *root;
    scanf("%s", a);
    shu = 0;
    root  = new struct node;
    root = create();
    printf("树的前序遍历：");
    before(root);
    printf("\n");
    printf("树的中序遍历：");
    mid(root);
    printf("\n");
    printf("树的后序遍历：");
    after(root);
    printf("\n");
    return 0;
}

已知树的前序遍历和中序遍历，求树的深度、后序遍历、层序遍历：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>

using namespace std;

struct node
{
    char data;
    struct node *l, *r;
};
struct node *create(int n, char a[], char b[])
{
    struct node *root;
    int i;
    if(!n)
    {
        return NULL;
    }
    for(i = 0;i < n;i++)
    {
        if(b[i] == a[0])
        {
            break;
        }
    }
    root = new struct node;
    root->data = a[0];
    root->l = create(i, a+1, b);
    root->r = create(n-i-1, a+i+1, b+i+1);
    return root;
};
int deep(struct node *root)
{
    int d = 0;
    if(root)
    {
        int l1 = deep(root->l);
        int l2 = deep(root->r);
        d = l1>l2 ? l1+1 : l2+1;
    }
      return d;
}

void after(struct node *root)
{
    if(root)
    {
        after(root->l);
        after(root->r);
        cout<<root->data;
    }
}

void cengci(struct node *root)
{
    struct node *temp[100];
    int in = 0, out = 0;
    temp[in++] = root;
    while(in > out)
    {
        if(temp[out])
        {
            printf("%c", temp[out]->data);
            temp[in++] = temp[out]->l;
            temp[in++] = temp[out]->r;
        }
        out++;
    }
}

int main()
{
    int n, m;
    char a[101], b[101];
    while(~scanf("%d", &n))
    {
        struct node *root;
        scanf("%s", a);
        scanf("%s", b);
        root = create(n, a, b);
        m = deep(root);
        printf("树的深度为：%d\n", m);
        printf("后序遍历:\n");
        after(root);
        printf("\n");
        printf("层序遍历:\n");
        cengci(root);
    }
    return 0;
}

已知树的中序遍历和后序遍历，求树的深度、前序遍历、层序遍历：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>

using namespace std;

struct node
{
    char data;
    struct node *l, *r;
};
struct node *create(int n, char a[], char b[])
{
    struct node *root;
    int i;
    if(!n)
    {
        return NULL;
    }
    else
    {
        root = (struct node *)malloc(sizeof(struct node));
        root->data = a[n-1];
    for(i = 0;i < n;i++)
    {
        if(a[n-1] == b[i])
        {
            break;
        }
    }
    root->l = create(i, a, b);
    root->r = create(n-i-1, a+i, b+i+1);
    }
    return root;
}
int deep(struct node *root)
{
    int d = 0;
    if(root)
    {
        int l1 = deep(root->l);
        int l2 = deep(root->r);
        d = l1>l2 ? l1+1 : l2+1;
    }
      return d;
}

void before(struct node *root)
{
    if(root)
    {
        cout<<root->data;
        before(root->l);
        before(root->r);
    }
}

void cengci(struct node *root)
{
    struct node *temp[100];
    int in = 0, out = 0;
    temp[in++] = root;
    while(in > out)
    {
        if(temp[out])
        {
            printf("%c", temp[out]->data);
            temp[in++] = temp[out]->l;
            temp[in++] = temp[out]->r;
        }
        out++;
    }
}

int main()
{
    int n, m;
    char a[101], b[101];
    while(~scanf("%d", &n))
    {
        struct node *root;
        scanf("%s", b);
        scanf("%s", a);
        root = create(n, a, b);
        m = deep(root);
        printf("树的深度为：%d\n", m);
        printf("前序遍历:\n");
        before(root);
        printf("\n");
        printf("层序遍历:\n");
        cengci(root);
    }
    return 0;
}