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

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

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

DS森林叶子编码

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

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

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

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

输出样例1
0 1 1\n
1 0\n
1 1 0 1 0\n

森林转二叉树

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

#include<bits/stdc++.h>
using namespace std;
struct tree
{char value;tree* left;tree* brother;
};//创建树
tree* setTree(char c[],int b,int& index,int j)
{if(index>=j||c[index]=='0'){index++;return NULL;}tree* t=new tree;t->value=c[index];index++;if(b==1) t->brother=NULL;bool flag=0;tree* tr=NULL;tree* trr=NULL;for(int i=0;i<b;i++){//这里可以防止重复setTree，直接用变量记录trr=setTree(c,b,index,j);//第一个非空子节点作为左孩子if(!flag&&trr!=NULL) {t->left=trr;flag=1;tr=t->left;continue;}//这里就是要考虑一个节点下一个兄弟节点是空的情况if(tr==NULL||trr==NULL) {if(tr==NULL&&trr!=NULL) tr=trr;else if(tr==NULL&&trr==NULL) tr=trr;else tr=tr;}else {tr->brother=trr;tr=tr->brother;}//注意要给每个根节点最后一个子节点的兄弟节点赋值空指针！！！if(tr&&i==b-1) tr->brother=NULL;}if(flag==0) t->left=NULL;return t;
}
string s[105];
int flag=0;//查找叶子节点
void findLeaf(string path,tree* t)
{if(t==NULL) return ;else if(t!=NULL&&t->left==NULL&&t->brother==NULL){s[flag]=path;flag++;return ;}findLeaf(path+"0",t->left);findLeaf(path+"1",t->brother);
}int main()
{int n,b;cin>>n>>b;getchar();tree* trees[105];for(int i=0;i<n;i++){char c[105];char ch;int j=0,index=0;while((ch=getchar())!='\n'){c[j]=ch;j++;if(getchar()=='\n') break;}//先分别创建树，存进数组中tree* t=new tree;t=setTree(c,b,index,j);trees[i]=t;}//给每个树的根节点的兄弟节点赋值for(int i=0;i<n-1;i++) trees[i]->brother=trees[i+1];//最后一个树的根节点的兄弟节点赋值空指针trees[n-1]->brother=NULL;findLeaf("",trees[0]);for(int i=0;i<flag;i++){for(int j=0;j<s[i].size();j++){(j==0)?cout<<s[i][j]:cout<<" "<<s[i][j];}cout<<endl;}return 0;
}