二叉树分解
本帖最后由 aimisiyou 于 2016-7-26 23:36 编辑两正整数n,m（n>=m）按以下规则进行类似二叉树分解：
1、若n,m不互质，d=gcd(n,m),则对（n/d,m/d）进行分解；
2、一般情况分解后的左节点为（(a+1)/2，（b+1）/2）,右节点为（a/2，b/2）;若除叶子及根节点为（奇，偶）形式外分解得到左节点为（偶，奇）形式，则此时左右节点对换；数值较大的节点路经上标注两节点之差；左路径节点值之差可为（1,1）或（1,0），右路径节点值之差可为（1,1）或（0,1）或（1,0）但（0,1）和（1,0）不能同时出现在同一路径上（通过交换左右叶子）；
3、所有叶子均为（n,1）形式；
4、若通长左路径标注上有（1,1）和（1,0），则通过叶子对换使得左叶子为（1,1），同样若通长右路径标注上有（1,1）和（0,1），则通过叶子对换使得右叶子为（1,1）；
5、通长左路径上有（1,0）标注的叶子权值为-1；通长右路经上标注有（0，1）的叶子权值为-1，通长右路经上标注有（1，0）的叶子权值为1。其余情况的叶子权值为0.
那么对满足要求的（a,b）是否必有分解（若有分解则其二叉树分解必然唯一）？叶子权值和与（a,b）间的关系？叶子权值和能否取到所有整数？ 本帖最后由 aimisiyou 于 2016-7-26 22:19 编辑
（11,7）分解后叶子权值和为2. 本帖最后由 aimisiyou 于 2016-7-27 07:43 编辑
出现特例。 经多次尝试发现个别数据无法分解，说明规则还有待完善。先考虑下再说。 本帖最后由 aimisiyou 于 2016-7-27 14:32 编辑
重新整理了下。
两正整数n,m（n>=m）按以下规则进行类似二叉树分解：
1、所有叶子均为（n,1）形式；
2、若n,m不互质，d=gcd(n,m),则对（n/d,m/d）进行分解；
3、第一次分解左节点为（(a+1)/2，（b+1）/2），右节点分别为（a/2，b/2），结果取整。左路径上标注两节点数值之差（（1,1）或（1,0））。后续分解节点数值按照第一次算法，只是左右位置可互换，同时节点数值较大的路径上要标注数值之差。
4、若直线路径标注上同时有（1,1）和（1,0），则该路径上叶子为（1,1）；若直线路径标注上同时有（1,1）和（0,1），则该路径上叶子为（1,1）；直线路径上标注不能同时出现（1,0）和（0,1）；
5、若左叶子直线路径上有（1,0），则其叶子权值为-1；若左叶子直线路径上有（0,1），则其叶子权值为1；若右叶子直线路径上有（0,1），则其叶子权值为-1；若右叶子直线路径上有（1,0），则其叶子权值为1；
6、其余情况的叶子权值为0.
那么对满足要求的（a,b）是否必有分解（根据对称性可知，若有分解必然不唯一）？任意分解下的叶子权值和是否相等（感觉是肯定的）？叶子权值和与（a,b）间的关系？叶子权值和能否取到所有整数？ 有什么好的算法设计，只要得到其中一个分解就行？初步想法就是直接按步骤分解，再判断是否满足要求，若不符合要求再去调整相关节点左右位置。 本帖最后由 aimisiyou 于 2016-12-11 15:00 编辑
将（n,m）分解规则重新定义如下：
1、若n<m,则n,m互换位置;
2、若n,m非互质，则将其化简为最简式；
3、一般情况下，权值赋在左路径上；
4、若左路径上为全为（1,1），则叶子点方向值为+1；
5、若左路径上为（1,1）,(0,1)的重复组合，则叶子点方向为+1；
6、若左路径上全为（1,0），则叶子点方向值为-1；
7、若左路径上全为（0,1），则叶子点方向值为+1；
8、若左路径上以（1,0）开始，则后续左路径上只能接（1,0），否则权值赋在右路径上；
9、若左路径上以（0,1）或（1,1）开始，则后续左路径上只能接（0,1）或（1,1），否则权值赋在右路径上；
10、若右路径上为全为（1,1），则叶子点方向值为-1；
11、若右路径上为为（1,1）,(0,1)的重复组合，则叶子点方向值为-1；
12、若右路径上为全为（1,0），则叶子点方向值为+1；
13、若右路径上为全为（0,1），则叶子点方向值为-1；
14、若右路径上以（1,0）开始，则后续右路径上只能接（1,0），否则权值赋在左路径上；
15、若右路径上以（0,1）或（1,1）开始，则后续右路径上只能接（0,1）或（1,1），否则权值赋在左路径上；
16、通长路径上无赋值的叶子点方向值规定为+1.
显然，对于所有的正整数（n,m）均有唯一分解，那么所有叶子点方向值之和能否取到所有正整数？或者所有叶子点方向值之和为20的（n,m）最小为多少？ （97,89）分解后所有叶子点和值为10.
页:
[1]