(第一次发布海报,而不是新编程,请耐心等待!)
我对打印格式化二叉树(在CLI环境中)和C实现的高效通用算法感兴趣.这是我为了好玩而编写的一些代码(这是原始版本的简化版本,是支持许多BST操作的大型程序的一部分,但它应该编译得很好):
#include <stdbool.h> // C99, boolean type support
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define DATATYPE_IS_DOUBLE
#define NDEBUG // disable assertions
#include <assert.h>
#define WCHARBUF_LINES 20 // def: 20
#define WCHARBUF_COLMS 800 // def: 80 (using a huge number, like 500, is a good idea,
// in order to prevent a buffer overflow :)
#define RECOMMENDED_CONS_WIDTH 150
#define RECOMMENDED_CONS_WIDTHQ "150" // use the same value, quoted
/* Preprocessor directives depending on DATATYPE_IS_* : */
#if …我在一次采访中向我询问了这个问题:我有一个二叉树,我必须找到共同的祖先(父)给出该树的两个随机节点.我也得到了一个指向根节点的指针.
我的回答是:
分别遍历两个节点的树,直到到达预期的节点.遍历时并行存储元素和链接列表中的下一个地址.然后我们有两个链接列表.因此,尝试比较两个链表,两个链表中的最后一个公共节点是父列表.
我认为这个解决方案是正确的,如果我错了,请纠正我.如果这个解决方案是正确的,我可能知道这是这项任务的唯一更好的解决方案还是有比这更好的解决方案!
如何找到二叉树的垂直和.
例如,考虑下面的二叉树,
1
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
/ \ / \ / \ / \
5 9 1 3 6 7 5 5
对于上面的树,垂直和应该计算如下,
输出应该是:
5,4,12,5,10,6,15,7,5
所以,过去一个月我一直在学习C#,而目前我正在与Binary Trees进行斗争.
我的问题是,如何将我的树调用到控制台窗口？我试过Console.WriteLine(tree.Data);但这似乎写54到我的控制台窗口.
如果你需要检查一下,这是我的代码:
主文件
static void Main(string[] args)
{
//Creating the Nodes for the Tree
Node<int> tree = new Node<int>('6');
tree.Left = new Node<int>('2');
tree.Right = new Node<int>('5');
Console.WriteLine("Binary Tree Display");
Console.WriteLine(tree.Data);
Console.ReadLine();
}
节点类
class Node<T> where T : IComparable
{
private T data;
public Node<T> Left, Right;
public Node(T item)
{
data = item;
Left = null;
Right = null;
}
public T Data
{
set { data = value; }
get { return data; …我试图在C#中实现二叉树,而不是二进制搜索树.我实现了下面的代码,它工作正常,但不是我想要的.基本上我正在尝试实现一个完整的二叉树,但是使用我的下面的代码,我得到一个不平衡的二叉树.
Input : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
Desired Output :
10
/ \
20 30
/ \ / \
40 50 60 70
/ \ /
80 90 100
Current Output :
10
/ \
20 30
/ \
40 50
/ \
60 70
/ \
80 90
/
100
这是我的代码:
class Node
{
public int data;
public Node left;
public Node right;
public Node()
{
data = 0;
left = null;
right …给定一个带有整数,左右指针的二叉树,如何在O(n)时间和O(1)额外内存(没有堆栈/队列/递归)中遍历树？
这个人给出了一个解决方案,该解决方案不是将当前路径编码为整数的O(n)总时间(因此适用于有限深度的树).
我正在寻找经典的解决方案
(SPOILER)
编码子节点中每个节点的父节点.
有两个二叉树T1和T2存储字符数据,允许重复.
如何判断T2是否是T1的子树？.
T1有数百万个节点,T2有数百个节点.
I.刚刚实现了一种按位trie(基于nedtries),但我的代码执行了很多内存分配(对于每个节点).与我的实现相反,在其他事物中声称nedtries很快,因为它们的内存分配数量很少(如果有的话).作者声称他的实施是"就地"的,但在这种情况下它的真正含义是什么？nedtries如何实现如此少量的动态内存分配？
Ps:我知道源代码可用,但代码很难遵循,我无法弄清楚它是如何工作的
随着算法的进展,我有一棵大树.每个节点都包含set,我认为它是作为平衡二叉搜索树实现的.在创建该节点的子节点之前,每个节点的集合在该节点创建之后应保持固定.
但我担心复制每一套都非常昂贵.相反,我希望每个新创建的节点集合利用父节点集合的所有适当部分.简而言之,我很高兴复制集合的O(log n)而不是O(n).
STL的关联数据结构是否有任何变体可以提供这种部分复制优化？也许在Boost？当然,在Haskell或OCaML中实现这样的数据结构是微不足道的,但是在C++中需要更多的努力.
通常,基于二叉树的抽象可以使用实际的链接节点对象来实现,其中每个节点具有指向它的两个子节点的指针,或者数组,其中索引k中的节点的子节点是2k和2k + 1.
除了节点的小额外内存开销之外,一般的复杂性似乎是相同的.
一个是否有任何具体优势？有趣的是,我已经看到二进制堆倾向于使用数组实现,而二进制搜索树倾向于使用链接节点实现.有什么理由吗？