巩义网站,做网站的技术,苏宁易购商城,.net做网站后台DS森林叶子编码
题目描述 给定一组森林#xff0c;编写程序生成对应的二叉树#xff0c;输出这颗二叉树叶结点对应的二进制编码.规定二叉树的左边由0表示#xff0c;二叉树的右边由1表示。
输入 N B 表示N个树#xff0c;每结点最多B个分支 第2行至第N1行#xff0c;每个…DS森林叶子编码
题目描述 给定一组森林编写程序生成对应的二叉树输出这颗二叉树叶结点对应的二进制编码.规定二叉树的左边由0表示二叉树的右边由1表示。
输入 N B 表示N个树每结点最多B个分支 第2行至第N1行每个树的先序遍历
输出 每行表示一个叶结点对应的二进制编码.
输入样例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
森林转二叉树
注意点不是根节点的第一个子节点是左孩子而是根节点的第一个非空子节点是左孩子同样的一个结点的下一个非空兄弟节点是他的右节点 另外树的问题一定一定不要忽略一些空节点的赋值一个非空节点的结构体中必要节点都一定要保证赋值到不然会报错 另外其实建了树后不用再特意转化为二叉树因为我下面这种创建方法直接是一个有两个指针的结构体可以直接当成二叉树来继续
#includebits/stdc.h
using namespace std;
struct tree
{char value;tree* left;tree* brother;
};//创建树
tree* setTree(char c[],int b,int index,int j)
{if(indexj||c[index]0){index;return NULL;}tree* tnew tree;t-valuec[index];index;if(b1) t-brotherNULL;bool flag0;tree* trNULL;tree* trrNULL;for(int i0;ib;i){//这里可以防止重复setTree直接用变量记录trrsetTree(c,b,index,j);//第一个非空子节点作为左孩子if(!flagtrr!NULL) {t-lefttrr;flag1;trt-left;continue;}//这里就是要考虑一个节点下一个兄弟节点是空的情况if(trNULL||trrNULL) {if(trNULLtrr!NULL) trtrr;else if(trNULLtrrNULL) trtrr;else trtr;}else {tr-brothertrr;trtr-brother;}//注意要给每个根节点最后一个子节点的兄弟节点赋值空指针if(trib-1) tr-brotherNULL;}if(flag0) t-leftNULL;return t;
}
string s[105];
int flag0;//查找叶子节点
void findLeaf(string path,tree* t)
{if(tNULL) return ;else if(t!NULLt-leftNULLt-brotherNULL){s[flag]path;flag;return ;}findLeaf(path0,t-left);findLeaf(path1,t-brother);
}int main()
{int n,b;cinnb;getchar();tree* trees[105];for(int i0;in;i){char c[105];char ch;int j0,index0;while((chgetchar())!\n){c[j]ch;j;if(getchar()\n) break;}//先分别创建树存进数组中tree* tnew tree;tsetTree(c,b,index,j);trees[i]t;}//给每个树的根节点的兄弟节点赋值for(int i0;in-1;i) trees[i]-brothertrees[i1];//最后一个树的根节点的兄弟节点赋值空指针trees[n-1]-brotherNULL;findLeaf(,trees[0]);for(int i0;iflag;i){for(int j0;js[i].size();j){(j0)?couts[i][j]:cout s[i][j];}coutendl;}return 0;
}
