树形数据结构题解

, ,

总结下面几道题：首先想好用什么数据类型去处理这些输入的数据，然后就是遍历过程的实现。要的不仅仅是数据结构的思想，还需要分析问题，解决问题的能力，还有就是代码语言工具的熟练度。

FBI树
题目链接
解题思路：
由题意可知，一开始输入的字符为根结点。然后一半一半分，左半部分为左子树，右半部分为右子树。然后再将左边的一半分，左边同样为此结点的左子树，右边为此结点的右子树。
不然看出，可以用递归的思想去实现此过程，而且这个过程很像二分查找。
题目要求输出这个二叉树的后序遍历。所以我们要输出左子树，右子树，根结点的顺序。
注意1处的位置，a,b对应的递归处，以及2处之间的逻辑关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
using namespace std;

char s[1030];

void bianli(int low,int high){
    if(low>high)    return;
    int mid=(low+high)/2;
    if(low!=high){//这个if，保证一直递归到叶子结点 	1
        bianli(low,mid);   //a
        bianli(mid+1,high);   //b
    }
//当遍历过程中，不能满足low！=high这个条件时，就运行下面的计数部分，
//不满足low!=high，且是从bianli(low,high)出来运行到这时，一般此时low和high同时指向了同一个结点，
//此时这种情况，对应的是左叶子结点(第一次时)；
//若是从bianli(mid+1,high)出来的，此时对应的是右叶子结点(第二次时)。
//最后一种情况，是递归全部出来了，顺序执行到这里，此时是根结点的情况，即是后序遍历。
    int shua=0;//  2
    //int shub=0;注释掉的为方法二（计数方式）
    for(int i=low;i<=high;i++){
        if(s[i]=='1')   shua++;
        //else shub++;
    }
    // if(shua&&shub)  cout<<"F";
    // else if(shua) cout<<"B";
    // else    cout<<"I";
    if(shua==high-low+1)    cout<<"I";
    else if(shua)   cout<<"F";
    else    cout<<"B";
}

int main(){
    int n;
    cin>>n;
    cin>>s+1;
    bianli(1,1<<n);//左移运算
    return 0;
}

求先序排列
题目链接

此题是一个典型的基础题。
用string类型的比较好操作，首先再后缀string中找到根结点，存在gen中，接着在中序遍历中找到根结点的位置（用find函数）。
然后进递归，substr(i,j)是输出i到j的字符，且不包含j字符。

递归部分的思想是：
比如有中序badc，后序bdca，那么，根结点是a。输出根结点a。
中序就变成b和dc两个子树，后序就变为b和dc两个子树。
那么问题就变成了1.求b中序遍历和b后序遍历的树，和2.中序遍历是dc和后序遍历是dc的树。
那么1.b就为根结点，输出。2.根结点是c，中序遍历分为左子树d，后序遍历变为左子树d。
那么输出根结点c，还有一个d，也成了根结点，输出。
总结：流程可以概括为，
step1:找到根并输出

step2:将中序，后序各分为左右两棵子树；

step3:递归，重复step1,2；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<string>
using namespace std;

void hx(string xx,string zx){
    if(xx.size()>0){
        char gen=zx[zx.size()-1];//根节点
        cout<<gen;
        int k=xx.find(gen);//在中序遍历中找到根结点的位置
        hx(xx.substr(0,k),zx.substr(0,k));//将中序遍历按照找到的根结点的位置
        //分为左右子树，先对其左子树递归，同时对后序遍历的也分为对应左右子树部分
        //将左子树递归
        hx(xx.substr(k+1),zx.substr(k,xx.size()-k-1));
        //这里是对分出来的右子树递归
    }
}

int main(){
    string xx,zx;
    cin>>xx>>zx;
    hx(xx,zx);
    return 0;
}

新二叉树
题目链接
首先想好用什么数据类型存储数据，这里用结构体。其实本题的第一个输入的字母就是为根结点，是数据太水了，我们应该要按照一般的思想，先找到根结点是谁。
此题的思想是用每一个不同的数组下标分别指示一个字母，这样，就很方便的存储了输入的各个字母之间的树形结构的关系了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<string>

using namespace std;

struct node{
    char l,r,farther;
}tree[30];
//这里的数组，0号数组用来存根结点，
//1到26存对应的26个字母的左右儿子和父结点的情况，
//下标即可反映自身是什么字母

void pre(char zf){//遍历
    cout<<zf;//先序遍历，即先打印根结点
    if(tree[zf-97].l!='*')  pre(tree[zf-97].l);
    if(tree[zf-97].r!='*')  pre(tree[zf-97].r);
}
int main(){
    int n;
    cin>>n;//个数
    char root='*';//初始化根结点
    for(int i=0;i<26;i++)   tree[i].farther='*';//初始化每一个节点的父亲
    
    for(int i=1;i<=n;i++){//输入部分
        char zf,zfl,zfr;
        cin>>zf>>zfl>>zfr;
        if(root=='*')   root=zf;//第一个输入的为根结点
        tree[zf-97].l=zfl;//将其的左右儿子赋值
        tree[zf-97].r=zfr;
        if(zfl!='*')    tree[zfl-97].farther=zf;//将左右儿子的父亲交代清楚
        if(zfr!='*')    tree[zfr-97].farther=zf;
    }
        while(tree[root-97].farther!='*')   root=tree[root-97].farther;//找根节点
        pre(root);//从根结点开始遍历
        cout<<endl;
        return 0;
}

对称二叉树
题目链接
这一题中的子树概念是从一个结点（此时这个结点就是根结点）出发，要直到这个结点所在树的最底部，构成的树，才叫子树。
递归思想是：枚举根结点，判断其左右两个孩子节点是否存在以及是否相同，如果存在且点权相等，就递归左右两个孩子节点的左右两个孩子节点。
重复上述判断。
当上面的递归完成后，即判断好对称二叉树后，就可以计算以该节点为根结点的对称二叉子树的节点数量，然后以max函数取出最大的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000;
long long zhi[maxn];//这里存的是结点的数值
long long leftt[maxn],rightt[maxn];
//这里存的是编号为i的结点的左孩子的编号
//以及编号为i的结点的右孩子的编号
//如果没有左右孩子，则在其中存-1
long long ans,n;
bool flag;

long long  zc(long long x)//递归遍历，数从这个根结点出发有多少个结点数
{
    long long sum = 0;
    if(leftt[x] != -1) sum += zc(leftt[x]);//注意，这里加的是zc函数中return的返回值
    if(rightt[x] != -1) sum += zc(rightt[x]);
    //遍历顺序是一直往左走，直到走到一个没有左孩子的结点，此时看有没有右节点，如果有，就
    //遍历这个结点的右节点，然后再递归这个结点的左孩子，如此。
    
    //总的概括而言，就是一直往左走，走不下去了，就看从这一步看能不能往右走一步，如果能往右走，
//就往右走一步，然后接着判断在此处能不能一直往左走；
    //如果不能往右走，就回退一步，再看能不能往右走一步，如果还是不能，就再回退一步。如此。

    return sum + 1;
    //一种情况是递归进去了，就说明有左或者右孩子，结点个数加一
    //加一的另一种情况是因为加上根节点（在最后出来的时候）
}

void digui(long long a,long long b){
    if(a==-1&&b==-1)   return;//没有孩子结点了，结束
    if(a==-1||b==-1||zhi[a]!=zhi[b]){//不对称
    //由题意可知，只要左右孩子有一个没有，不管他们孩子结点的值是否相同，他们一定不是对称二叉树
        flag=false;
        return;
    }
    digui(leftt[a],rightt[b]);//递归是左边结点的左孩子和右边节点的右孩子比较
    digui(leftt[b],rightt[a]);//或者是左边结点的右孩子和右边节点的左孩子比较，
    //是一个镜面对称的比较，因为题意是翻转结点，这里要理解好
}

int main(){
    //输入部分，也要绕过弯来，什么表示什么
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>zhi[i];
    }
    for(int i=1;i<=n;i++){
        cin>>leftt[i];
        cin>>rightt[i];
    }
    ans=1;
    for(int i=1;i<=n;i++){
        if(leftt[i]!=-1&&rightt[i]!=-1&&zhi[leftt[i]]==zhi[rightt[i]]){
            //如果左右孩子都存在，且其左右孩子的值都相同的情况下
            flag=true;
            digui(leftt[i],rightt[i]);
            if(flag==true){
                ans=max(ans,zc(i));
            }
        }
    }
    cout<<ans;
    return 0; 
}