标签: binary-tree

我被告知java类TreeMap使用RB树的实现.如果是这种情况,如何在TreeMap上进行顺序,预订和后序树步行？

或者这不可能吗？

关于二元搜索树我有两个问题,都是关于空树的.

1. 空树(null)是否有效？
2. 没有子节点的根节点是否有效？

添加1000个随机整数时,如何计算二叉搜索树的平均高度？平均身高是多少？

这是学校处理递归和二叉树的实验室的一部分.如果我要插入4或5个数字并输出结果,我只得到3个数字.这是插入的代码:

Node *insert(Node *t, int key) {
    Node *insertParent;
    Node *result=NULL;

    if (t!=NULL) {
        result=search(t,key,insertParent);
    } else {
        t=new Node;
        t->data=key;
        t->leftchild=NULL;
        t->rightchild=NULL;
        return t;
    }

    if (result==NULL) {
        if (insertParent->data>key) {
            insertParent->leftchild=new Node;
            insertParent->leftchild->data=key;
            insertParent->leftchild->leftchild=NULL;
            insertParent->leftchild->rightchild=NULL;
            return insertParent->leftchild;
        } else if (insertParent->data<key) {
            insertParent->rightchild=new Node;
            insertParent->rightchild->data=key;
            insertParent->rightchild->leftchild=NULL;
            insertParent->rightchild->rightchild=NULL;
            return insertParent->rightchild;
        }
    } else
        return NULL;
}

但我相信问题在于搜索功能,特别是引用父节点指针:

Node* search(Node *t, int key, Node *&parent) {
    if (t!=NULL) {
        parent=t;
        if (t->data==key)
            return t;
        else if (t->data>key)
            return search(t->leftchild,key,t);
        else …

我有一个树结构,其节点具有父ID(无限子节点).出于显示目的,我需要这个树结构作为二叉树.我如何做到这一点是在每个级别节点根据条件分组到一个节点.选择节点后,将显示其子节点.例:

绿色是条件true,红色是false

B,C已分组到左侧节点,D,E根据其条件在右侧.

问题:我正在使用KnockoutJS来显示我的树,我需要能够执行常规树操作,例如根据其ID获取节点,插入节点删除节点.这是我的结构.有没有更好的结构/方式来做到这一点？

var tree = [
    { groupNodeId: "A", childNodes: [
        { nodeId: "A", childGroupNodes: [
            { groupNodeId: "B", condition: true, childNodes: [
                { nodeId: "B", childGroupNodes: []},
                { nodeId: "C", childGroupNodes: []}
            ]},
            { groupNodeId: "D", condition: false, childNodes: [
                { nodeId: "D", childGroupNodes: []},
                { nodeId: "E", childGroupNodes: []}
            ]}
        ]}
    ]}
];

如果我构造一个二进制搜索树,按顺序添加以下值:

 10, 7, 16, 12, 5, 11, 2, 20, 1, 14

我得到一个高度为5的树.是否有一个方法(除了试验和错误)我可以用来确定一个整数的排序,它将创建一个高度为4的树？

以下是我对二进制搜索树的最低共同祖先的实现.我有两个问题:

1)时间复杂度为O(n),空间复杂度为O(n)更差情况,但如果BST平衡,则时间和空间的O(logn)平均情况.那是对的吗？2)我如何将我的解决方案扩展到二叉树而不仅仅是二叉搜索树.

希望早日收到你的消息.

//The function findOrQueue is to enqueue all elements upto target node to a queue
public void findOrQueue(Node target, Node top, LLQueue q) {
    int cmp = target.getData().compareTo(top.getData()); 
    if(cmp == 0) {
        q.enqueue(top);
        return ;
    }
    else if (cmp < 0) {
        q.enqueue(top);
        findOrQueue(target, top.getLeftChild(),q);
    }
    else {
        q.enqueue(top);
        findOrQueue(target, top.getRightChild(),q);
   }
}

public Node LCA(Node n1, Node n2) throws QueueEmptyException {
    LLQueue q1 = new LLQueue();
    LLQueue q2 = new LLQueue();
    findOrQueue(n1,getRoot(),q1);
    findOrQueue(n2,getRoot(),q2);
    Node t = null; …

我正在传递一个表示数学公式的二进制AST.每个内部节点都是运算符,叶节点是操作数.我需要走树并以中缀表示法输出公式.通过使用递归算法(例如Print()下面显示的方法)遍历树,这很容易实现.该Print()方法的问题在于转换为中缀时操作顺序丢失,因为没有生成括号.

我编写了PrintWithParens()输出正确的中缀公式的方法,但它添加了无关的括号.您可以在我的main方法的四个案例中的三个中看到它在没有必要时添加括号.

我一直绞尽脑汁试图弄清楚PrintWithMinimalParens()应该是什么样的正确算法.我确信必须有一个算法只能在必要时输出括号来组合术语,但是我无法正确实现它.我想我必须要查看当前节点下面树中运算符的优先级,但我现在的算法不起作用(参见我的main方法中的最后两种情况.不需要括号,但是我的逻辑添加它们).

public class Test {

static abstract class Node {

    Node left;
    Node right;
    String text;

    abstract void Print();
    abstract void PrintWithParens();
    abstract void PrintWithMinimalParens();

    int precedence()
    {
        return 0;
    }
}

enum Operator { 
    PLUS(1,"+"), 
    MINUS(1, "-"), 
    MULTIPLY(2, "*"), 
    DIVIDE(2, "/"), 
    POW(3, "^") 
    ;

    private final int precedence;
    private final String text;

    private Operator(int precedence, String text)
    {
        this.precedence = precedence;
        this.text = text;
    }

    @Override
    public String toString() …

我有一个表示类型签名的数据结构,这个数据结构是在第一个图片中作为红色示例的树.我想得到黑色的,到目前为止我只得到了橙色的(第二张图片),这是类型树但与左边相关联.

这是我到目前为止的橙树(遵循橙色箭头)

我通过漂亮打印树然后用解析器组合器解析它来解决了这个问题,但这种效率低下是不可取的.我想我可以有另一种算法从橙树转换为黑树,但如果不是组合两种算法,我只能写一种算法会更好.

我将此标记为Haskell,因为我正在编写我的解决方案.我可以提供代码来获取像红树这样的数据结构,但我认为它只会使解决方案的尝试复杂化.

我想知道这个算法是否有名称和/或红树中操作员位置的名称是什么.是前缀吗？

谢谢.

问题在具有n个节点的完整二叉树中查找叶节点的数量.

我为上述问题编写了一个递归程序,每当我到达一个没有子节点的节点时遍历树并增加叶子节点的数量.但由于树是一个完整的二叉树,我认为它会使问题更容易,但我无法弄清楚如何.它可以以紧凑的形式(类似公式)减少.