洛谷OJ P1087 FBI树

一时失言乱红尘 2022-04-14 06:57 355阅读 0赞

#### 题目： ####

题目描述  
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N  
的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：

1.  T的根结点为R，其类型与串S的类型相同；
2.  若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1  
     和S\_2  
     ；由左子串S\_1  
     构造R的左子树T\_1  
     ，由右子串S\_2  
     构造R的右子树T\_2  
     。

现在给定一个长度为2^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。

输入输出格式  
输入格式：  
第一行是一个整数N(0≤N≤10)，

第二行是一个长度为2^N  
的“01”串。

输出格式：  
一个字符串，即FBI树的后序遍历序列。

--------------------

#### 自己的分析：最简单的思路：就直接按照题意模拟，建一颗树，然后对这个树进行后序遍历。 ####

卡的最久的点就是建树的过程了，自己打的方法是：每次建立左（右）子树前传递父节点的左（右）指针。在递归中，每次判断完当前节点的字母后，用引用把传进来的父节点左（右）指针指向当前节点。其他都好办，就是根节点要特别处理，因为它的特征与其他节点相同，但却不用“把父节点指向自身”。所以我人为得加了一个参数sign来区分根节点和非根节点，只有第一次执行建树函数时sign才为1，其他都传入0。

贴上自己的代码：

#include <iostream>
    #include <string>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    typedef struct tnode* link;
    typedef struct tnode { 
    	char ch;
    	link left;
    	link right;
    	int sign;
    }node;
    char str[1025];
    int judge(int left, int right) {                  //判断一个节点的字符串对应的字母
    	bool one = false;
    	bool zero = false;
    
    	for (int i = left; i!= right + 1; i++) { 
    		if (str[i] == '0')   zero = true;
    		else if (str[i] == '1') one = true;
    	}
    	if (zero == true && one == true)   return 1;
    	else if (zero == true && one == false) return 2;
    	else if (zero == false && one == true)    return 3;
    }
    link create(int left, int right,link& father,int sign) {        //通过递归来建树
    	int length = (right - left + 1);
    	int type = judge(left, right);
    
    	link p = new node();
    	if (type == 1)  p->ch = 'F';
    	else if (type == 2) p->ch = 'B';
    	else if (type == 3) p->ch = 'I';
    ;
    
    	if (length > 1) { 
    		if (sign==1) {         //sign为人为添加的标记，说明这个节点是根节点
    			create(left, (left+right)/2, p->left,0);
    			create((left+right)/2+1, right, p->right,0);
    		}
    		else {                         //不是根节点的话先与父节点连接
    			father = p;
    			create(left, (left + right) / 2, p->left,0);
    			create((left + right) / 2 + 1, right, p->right,0);
    		}
    	}
    	else { 
    		p->left = NULL;
    		p->right = NULL;
    		father=p;
    	}
    	return p;
    }
    
    void postorder(link p) { 
    	if (p) { 
    		postorder(p->left);
    		postorder(p->right);
    		cout << p->ch;
    	}
    }
    
    int main() { 
    	int n,i,length;
    	bool one = false;
    	bool zero =false;
    	link root=NULL;
    
    	cin >> n ;
    	length = pow(2, n);
    
    	for (i = 1; i <= length; i++) { 
    		cin >> str[i] ;
    	}
    
    	root = create(1,length,root,1);
    	postorder(root);
    }

--------------------

### 反思、收获： ###

1.把字符串二分的过程中的左右子区间的下标自己还不熟悉：

（对于int值（下标），左下标为left，右下标为right）：

**区间从0、1开始都通用**：左子区间为（left,(left+right)/2) , 右子区间为((left+right)/2+1,right ).  
（其中，区间中有偶数个元素时左右子区间相等大小，为奇数时左子区间比右子区间长度多1）

2原来与树的遍历有关的题目还可以直接输出每步结果，并不实际建树。学到了