一道POI题
刚才在一本书上看到这么一道题，不知怎么入手，特向大家请教，原文如下：
二进制病毒审查委员会最近发现了如下规律：某些确定的二进制串是病毒的代码，如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找到了所有病毒代码段，试问：是否存在一个无限长的安全的二进制代码？
例如：
如果{011 ， 11 ，00000}为病毒代码段，那么一个可能的无限长的安全代码可以是010101.........。
如果{01 ，11 ， 000000}为病毒代码段，那么就不存在一段无限长的安全代码。
请写一个程序，读入病毒代码，判断是否存在一个无限长的安全代码。
不知道这个是不是跟线性代数有什么关系。
[解决办法]
按照大概意思写了一个，测得不细致，不知是否写对了，两个例子似乎是对的。效率大概相当于遍历所有节点吧。using System;namespace ConsoleApplication4{ class Program { public class TreeNode { public bool Flag; public bool IsLeaf; public TreeNode ParentNode; public TreeNode RightNode; public TreeNode LeftNode; public void AppendRight(TreeNode node) { RightNode = node; node.ParentNode = this; } public void AppendLeft(TreeNode node) { LeftNode = node; node.ParentNode = this; } public bool IsRight() { return ParentNode.RightNode.Equals(this); } public bool IsLeft() { return ParentNode != null && ParentNode.LeftNode.Equals(this); } } public class Tree { public TreeNode Root = new TreeNode(); public void Add(string word) { TreeNode currentNode = Root; for (int i = 0; i < word.Length; i++) { if (word[i] == '0') { if (currentNode.LeftNode == null) currentNode.AppendLeft(new TreeNode()); currentNode = currentNode.LeftNode; } else { if (currentNode.RightNode == null) currentNode.AppendRight(new TreeNode()); currentNode = currentNode.RightNode; } } currentNode.IsLeaf = true; } public void Combine(TreeNode node) { TreeNode tNode = node.IsLeft() ? Root.LeftNode: Root.RightNode; if (node.LeftNode != null) Combine(node.LeftNode); else if (!node.Equals(tNode) && tNode.LeftNode != null) node.LeftNode = tNode.LeftNode; else node.LeftNode = Root.LeftNode; if (node.RightNode != null) Combine(node.RightNode); else if (!node.Equals(tNode) && tNode.RightNode != null) node.RightNode = tNode.RightNode; else node.RightNode = Root.RightNode; if (node.RightNode.IsLeaf && node.LeftNode.IsLeaf) { node.IsLeaf = true; node.RightNode = null; node.LeftNode = null; } } } static void Main(string[] args) { Tree tree = new Tree(); tree.Add("0001"); tree.Add("0000"); tree.Add("001"); tree.Add("01"); tree.Add("111"); tree.Combine(tree.Root); if (tree.Root.IsLeaf) Console.WriteLine("Can Not"); else Console.WriteLine("Yes"); } }}
[解决办法]
其实我自己感觉Combine那里有点问题，没时间多试了，如果有问题，就是dfs对节点遍历的先后顺序，
可能会影响处理结果，另外回溯的节点也可能有些问题。
其实原理还是挺简单的，如果某个节点的Right和Left都为叶子节点，那么就删除Right和Left，
并将该节点设为叶子节点，这样可以不断降低树高，如果不能表示为无限长的串，经过递归和回溯之后，
最终Root本身将成为叶子节点，否则Root则不是叶子节点。
以01 ，11111， 000000为例，由于不允许出现01串，那么不能出现000001，也不能出现000000，
因此不能出现00000，同理，不能出现00001，也就不可以出现0000.....不可以出现0，
由于不可以出现0，不可以出现11111，也不能出现11110，所以不能出现1111，一直推出不能出现1，
此时Root的0和1两个分支都为叶子节点，Root也就成为了叶子节点。