首页 / C# / c# – 递归树映射
c# – 递归树映射
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c# – 递归树映射,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2552字,纯文字阅读大概需要4分钟。
内容图文
![c# – 递归树映射](/upload/InfoBanner/zyjiaocheng/783/941956616af84351ae0398bb9490e317.jpg)
我最近在树实现方面做了很多工作,以及我们如何表示和理解树.我的重点是将数学表达式转换为二叉树,我设置了以线性形式表示树的问题,如字符串或数组,同时仍保留有关树及其子树的重要信息.
因此,我已经为二进制表达式树开发了一个非常简单的编码.然而,我在一个递归庄园中有效地实现它有一些问题,它似乎是概念背后的一个失败方面.
如果节点作为左子节点存在,则编码很简单如果它作为右子节点被赋予0,则给出1的映射.这种简单的编码允许我对整个平衡和非平衡树进行编码,如下所示:
## ##
/ \ / 1 0 OR 1 0
/ \ / \ / 11 10 01 00 01 00
等到深度为N的树木
有没有人有任何关于如何创建递归函数的建议,该递归函数将创建表示此类映射的前缀字符串(例如## 1 11 10 0 01 00).
我被告知这将是困难/不可能的,因为必须跟踪1和0之间的交替,同时保留和连接到父母的价值.
我想知道是否有人对C#如何做到这一点有任何见解或想法?
解决方法:
我不确定我是否理解你的问题,但这里可能有所帮助.一种解决方案可能是在Graph上实现图遍历例程(记住Tree是一个专门的图),在第一次遇到节点/顶点时进行访问.当你要求C#发布Java代码时,我很抱歉,但我知道Java …
public void depthFirstSearch(Graph graph, Vertex start){
Set<Vertex> visited = new HashSet<Vertex>(); // could use vertex.isVisited()...
Deque<Vertex> stack = new ArrayDeque<Vertex>(); // stack implies depth first
// first visit the root element, then add it to the stack so
// we will visit it's children in a depth first order
visit(start);
visited.add(start);
stack.push(start);
while(stack.isEmpty() == false){
List<Edge> edges = graph.getEdges(stack.peekFirst());
Vertex nextUnvisited = null;
for(Edge edge : edges){
if(visited.contains(edge.getEndVertex)) == false){
nextUnvisited = edge.getEndVertex();
break; // break for loop
}
}
if(nextUnvisited == null){
// check the next item in the stack
Vertex popped = stack.pop();
} else {
// visit adjacent unvisited vertex
visit(nextUnvisited);
visited.add(nextUnvisited);
stack.push(nextUnvisited); // visit it's "children"
}
}
}
public void visit(Vertex vertex){
// your own visit logic (string append, etc)
}
您可以使用Deque作为队列而不是堆栈,轻松地将其修改为广度优先搜索,如下所示:
stack.pop() >>>> queue.removeFirst()
stack.push() >>>> queue.addLast()
请注意,为此,Graph和Edge类支持以下操作:
public interface Graph {
...
// get edges originating from Vertex v
public List<Edge> getEdges(Vertex v);
...
}
public interface Edge {
...
// get the vertex at the start of the edge
// not used here but kind of implied by the getEndVertex()...
public Vertex getStartVertex();
// get the vertex at the end of the edge
public Vertex getEndVertex();
...
}
希望这会给你一些想法.
内容总结
以上是互联网集市为您收集整理的c# – 递归树映射全部内容,希望文章能够帮你解决c# – 递归树映射所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。