标签: binary-tree

有序树遍历显然有应用; 按顺序获取内容.

预序遍历似乎对创建树的副本非常有用.

二叉树的后序遍历是否常见？

我的印象是,可以通过使用箭头和点运算符一起访问链表或类似结构的子节点中的数据,如下所示:

typedef struct a{
int num;
struct a *left;
struct a *right;
}tree;

tree *sample;
...
if(sample->left.num > sample->right.num)
    //do something

但是当我尝试实现它时,使用 - >和.从子节点访问数据我得到错误"请求成员数字不是结构或联合".

给出了两个BSTs(二叉搜索树).如何在给定的两个中找到最大的公共子树binary trees？

编辑1: 这是我的想法:

设r1 =第1树的当前节点r2 =第2树的当前节点

There are some of the cases I think we need to consider:

Case 1 : r1.data < r2.data
     2 subproblems to solve:
     first, check r1 and r2.left 
     second, check r1.right and r2

Case 2 : r1.data > r2.data
     2 subproblems to solve:
       - first, check r1.left and r2
       - second, check r1 and r2.right

Case 3 : r1.data == r2.data
     Again, 2 cases to consider here:
     (a) current node …

是否有一个可以使用二进制树的java库？我不期待测试和实施我自己的.

我正在阅读B树,看起来他们在O(lg n)时间内实现了动态集合操作.红黑树(Java中的TreeMap)也在渐近相同的时间范围内实现相同的操作.所以我想知道是什么让B树对数据库和文件系统更有用

我在互联网上看到了几个关于此的引用,但没有官方文档？谁能告诉我在哪里可以获得有关此信息？

假设我有一个简单的二叉树节点类,如下所示:

public class BinaryTreeNode {
    public String identifier = "";
    public BinaryTreeNode parent = null;
    public BinaryTreeNode left = null;
    public BinaryTreeNode right = null;

    public BinaryTreeNode(BinaryTreeNode parent, String identifier)
    {
        this.parent = parent; //passing null makes this the root node
        this.identifier = identifier;
    }

    public boolean IsRoot() {
        return parent == null;
    }
}

我如何添加一个能够以递归方式遍历任何大小树的方法,从左到右访问每个现有节点,而无需重新访问已遍历的节点？

这会有用吗？:

public void traverseFrom(BinaryTreeNode rootNode)
{
    /* insert code dealing with this node here */

    if(rootNode.left != null)
        rootNode.left.traverseFrom(rootNode.left);

    if(rootNode.right != null) …

可以从n个不同的元素构造多少个二叉搜索树？我们怎样才能找到一个经过数学验证的公式呢？

示例: 如果我们有3个不同的元素,比如说1,2,3,则有5个二叉搜索树.

假设我们有一个递归数据结构,就像二叉树一样.有许多方法可以遍历它,它们具有不同的内存使用配置文件.例如,如果我们只是打印每个节点的值,使用伪代码,如下面的按顺序遍历...

visitNode(node) {
    if (node == null) return;
    visitNode(node.leftChild);
    print(node.value);
    visitNode(node.rightChild);
}

...我们的内存使用量是常量,但由于递归调用,我们会增加调用堆栈的大小.在非常大的树上,这可能会溢出它.

假设我们决定针对调用堆栈大小进行优化; 假设这种语言能够进行适当的尾调,我们可以将其重写为以下预先遍历...

visitNode(node, nodes = []) {
    if (node != null) {
        print(node.value);
        visitNode(nodes.head, nodes.tail + [node.left, node.right]);
    } else if (node == null && nodes.length != 0 ) {
        visitNode(nodes.head, nodes.tail);
    } else return;
}

虽然我们永远不会破坏堆栈,但我们现在看到堆使用量相对于树的大小线性增加.

假设我们当时试图懒洋洋地遍历树 - 这就是我的推理变得模糊的地方.我认为即使使用基本的懒惰评估策略,我们也会以与尾部优化版本相同的速度增长内存.下面是使用Scala的Stream类的具体示例,它提供了延迟评估:

sealed abstract class Node[A] {
  def toStream: Stream[Node[A]]
  def value: A
}

case class Fork[A](value: A, left: Node[A], right: Node[A]) extends Node[A] {
  def toStream: Stream[Node[A]] = …

好吧,这是CS领域的另一个理论领域.

在90年代,我在实施BST方面做得相当不错.我唯一无法理解的是算法的复杂性以平衡二叉树(AVL).

你能帮助我吗？