【15分】E. 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
2
3
4

输出样例1

0 1 1
1 0
1 1 0 1 0
1
2
3

思路

创建四个类，分别为普通节点Node，二叉结点BiNode，普通树Tree，二叉树BiTree。

循环N次，每次先序遍历创建一棵普通树，然后将这棵普通树转换成一棵二叉树。

注意：转换的时候有一个易错点，我在这里卡了好久！！！
 
我们再来复习一下普通树转二叉树的核心步骤:
将树的根节点的第一个子节点作为二叉树根节点的左指针，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右指针,并递归进行下一步
 
我当时做错的原因就是把根节点的第一个子节点理解错了，其实更准确的表达是根节点的第一个非空子节点。因此不是p->firstchild = change(T->child[0])，而是找到一个非空的子节点cnt，然后p->firstchild = change(T->child[cnt])

接下来就是把所有已经转换好的二叉树合并了，如果是第一棵二叉树就直接赋值，剩下的二叉树就并为上一棵二叉树的根节点的右子树。

代码

#include 
#include 
using namespace std;

int B;
int N;

class Node
{
public:
    char data;
    Node **child;
    

    Node()
    {
        child = new Node*[B];
    }
};

class BiNode
{
public:
    char data;
    BiNode *firstchild;
    BiNode *next;
};


class Tree
{
public:
    Node *root;
    string str;
    int pos;

    Tree(string s)
    {
        str.assign(s);
        pos = 0;
        root = creat();
        
    }

    Node* creat()
    {
        if(str[pos] == '0')
        {
            pos ++;
            return NULL;
        }

        Node *p = new Node;
        p->data = str[pos];
        pos ++;
        for(int i = 0;i < B;i ++)
        {
            p->child[i] = creat();
        }
        return p;
    }

    BiNode* change(Node *T)
    {
        BiNode *p = NULL;
        if(T)
        {
            p = new BiNode;
            p->data = T->data;
            int cnt = 0;
            // 易错的地方！！！！
            while(!T->child[cnt] && cnt < B) cnt ++;
            if(cnt == B) p->firstchild = change(NULL);
            else p->firstchild = change(T->child[cnt]);
            if(p->firstchild)
            {
                BiNode *q = p->firstchild;
                
                for(int i = cnt+1;i < B;i ++)
                {
                    q->next = change(T->child[i]);
                    if(q->next) q = q->next;
                }
            }
        }
        return p;
    }
};

class BiTree
{
public:
    BiNode *root;

    BiTree(Tree T)
    {
        root = T.change(T.root);
    }
};

void preOrder(BiNode *p, string s)
{
    if(!p->firstchild && !p->next) 
    {
        for(int i = 0;i < s.length();i ++)
        {
            if(i) cout << " ";
            cout << s[i];
        }
        cout << endl;
    }
    if(p->firstchild) preOrder(p->firstchild, s + '0');
    if(p->next) preOrder(p->next, s + '1');
}


int main()
{
    cin >> N >> B;
    BiNode *p;
    for(int i = 0;i < N;i ++)
    {
        string s;
        char op;
        while(cin >> op)
        {
            s += op;
            if(getchar() == '\n') break;
        }
        Tree mytree(s);
        BiTree t(mytree);
        if(i == 0)
        {
            p = t.root;
        }
        else
        {
            BiNode *q = p;
            while(q->next) q = q->next;
            q->next = t.root;
        }
    }
    preOrder(p,"");
    
    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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146