DS森林叶子编码/森林转二叉树 【数据结构】

DS森林叶子编码

题目描述
给定一组森林，编写程序生成对应的二叉树，输出这颗二叉树叶结点对应的二进制编码.规定二叉树的左边由0表示，二叉树的右边由1表示。

输入
N B 表示N个树，每结点最多B个分支
第2行至第N+1行，每个树的先序遍历

输出
每行表示一个叶结点对应的二进制编码.

输入样例1
3 3
A B 0 0 0 C 0 0 0 D 0 0 0
E F 0 0 0 0 0
G H 0 0 0 I J 0 0 0 0 0 0

输出样例1
0 1 1
1 0
1 1 0 1 0

森林转二叉树

注意点：不是根节点的第一个子节点是左孩子，而是根节点的第一个非空子节点是左孩子，同样的，一个结点的下一个非空兄弟节点是他的右节点！！！！！
另外树的问题一定一定不要忽略一些空节点的赋值，一个非空节点的结构体中必要节点都一定要保证赋值到，不然会报错
另外，其实建了树后不用再特意转化为二叉树，因为我下面这种创建方法直接是一个有两个指针的结构体，可以直接当成二叉树来继续

//优化版
#include
using namespace std;
struct tree
{
    char data;
    tree* tarr[10];
};
struct binaryTree
{
    char data;
    binaryTree* left=NULL;
    binaryTree* right=NULL;
};
//建树
tree* setTree(char carr[],int &idx,int len,int b)
{
    if(idx>=len||carr[idx]=='0')
    {
        idx++;
        return NULL;
    }
    tree* t= new tree;
    t->data=carr[idx++];
    for(int i=0;i<b;i++) 
    {
        t->tarr[i]=setTree(carr,idx,len,b);
    }
    return t;
}
//建二叉树
binaryTree* setBinaryTree(tree* t,tree* par,int b)
{
    binaryTree* bt=new binaryTree;
    bt->data=t->data;
    for(int i=0;i<b;i++)
    {
        //第一棵非空字树为左孩子
        if(t->tarr[i]) 
        {
            bt->left=setBinaryTree(t->tarr[i],t,b);
            break;
        }
    }
    bool flag=0;
    for(int i=0;i<b;i++)
    {
        if(!par) break;
        //第一个非空兄弟是右子树
        if(!flag&&par->tarr[i]&&par->tarr[i]==t)
        {
            flag=1;
            continue;
        }
        if(flag&&par->tarr[i])
        {
            bt->right=setBinaryTree(par->tarr[i],par,b);
            break;
        }
    }
    return bt;
}
//输出叶子节点的二进制编码
void print(binaryTree* bt,string path)
{
    //到了叶子节点
    if(!bt->left&&!bt->right)
    {
        for(int i=0;i<path.size();i++) (i==0)?cout<<path[i]:cout<<" "<<path[i];
        cout<<endl;
        return ;
    }
    if(bt->left) print(bt->left,path+"0");
    if(bt->right) print(bt->right,path+"1");
    return ;
}
int main()
{
    int n,b;
    cin>>n>>b;
    getchar();
    //记录每棵树
    tree* t[205];
    for(int i=0;i<n;i++)
    {
        char c;
        //记录字符
        char carr[205];
        int idx=0;
        while(scanf("%c",&c)!=EOF)
        {
            carr[idx++]=c;
            //空格
            scanf("%c",&c);
            if(c=='\n') break;
        }
        int len=idx;
        idx=0;
        //建树
        t[i]=setTree(carr,idx,len,b);
    }
    //将每棵树转成二叉树
    binaryTree* btarr[205];
    //建二叉树
    for(int i=0;i<n;i++) btarr[i]=setBinaryTree(t[i],NULL,b);
    //将二叉树连接成一棵树
    for(int i=0;i<n-1;i++) btarr[i]->right=btarr[i+1];
    print(btarr[0],"");
    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
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110