标签: binary-tree

任何人都可以指出在不使用递归的情况下在二叉树(不是平衡的树或BST)中获取节点深度的方法吗？理想情况下在Java/C/C#

该节点表示为:

class Node
{
  Node Left;
  Node Right;
  string Value;
  int Depth;
}

使用带有FIFO列表的Level Order是我的第一个想法,但是当我发现水平发生变化时,我很难过,特别是对于不平衡的树.

我正在研究java中的数据结构,我在二进制搜索树中使用泛型有困难.

对于我们的任务,我们将使用包含父节点,左节点和右节点以及数据值的节点来实现二进制搜索树.

在我们的例子中,数据值采用Pair对象的形式.这就是它的样子:

public class Pair<A,B> {

    public final A fst;
    public final B snd;

    public Pair(A x, B y) {
        fst = x;  snd = y;
    }

    public String toString() {
      return new String("("+fst.toString()+", "+snd.toString()+")");
    }
}

Pair与两个不同的泛型相关联,第一部分是Key,第二部分是与该键相关的Value.

我还需要在我的BST课程中实现Iterator.我在内部类中实现Iterator,看起来像这样:

public Iterator<Pair<K,T>> iterator() {
    return new BSTMapIter<Pair<K,T>>(this.root, this.size, this.order);
}

private class BSTMapIter<Pair<K,T>> implements Iterator<Pair<K,T>> { <=== Compiler error "> expected"
    ...
    ... (Implementation here)
    ...
}

我遇到的问题是编译器错误说" > expected"导致其他编译器错误(" <identifier expected>"等).根据我的理解,它很窒息, <Pair<K,T>>但我不明白为什么.我假设这是我在某处使用泛型的错误,但我不完全确定在哪里看.

我很抱歉,如果我提供的内容过于模糊,但我在其他地方的实现中没有遇到任何问题,但在Iterator的实现中.

谁能告诉我这里我做错了什么??? 如果需要任何进一步的信息,请告诉我,我会尽力提供:)

我对以下代码有疑问

private void printTree(Node node){
    if(node==null) return;
    printTree(node.left);
    System.out.print(node.data+" ");
    printTree(node.right);
}

我真的不明白'回归'.那里的声明.看起来如果node为null,则代码不返回任何内容.但是如果没有那一行,编译器会生成异常错误.

这可能是完整二叉树中的节点只有一个子节点吗？谢谢

这可以是一个完整的二叉树吗？

        23
       /  \
      12  15
     /  \   
    9   11 
   / \    \
  10  5    13  

我想使用自平衡二叉树来使用一些算法,但是我很难找到Ruby的等效于Java的TreeSet(或C#的SortedSet).

我找到了像以下网页代码:

https://github.com/nahi/avl_tree#readme

https://github.com/MishaConway/binary_search_tree

http://blog.mikedll.com/2009/09/balanced-avl-binary-search-tree.html

我宁愿依赖Ruby标准库中的东西.Ruby的标准库中是不是有一些类？除了RubyTree之外我似乎找不到太多东西,我不相信它是自我平衡的.

(我会继续谷歌搜索,直到我找到它,或者这个论坛上有人指出我正确的方向:))

正如主题所述,我需要描述一种不使用递归来评估二进制算术表达式树的方法.没有给我任何其他细节或说明.

至于我对这些事情的理解,我需要模拟树的顺序遍历.假设在我的书列出的ADT方法的可用性,我有hasLeft(),hasRight(),left(),right(),isInternal(),和isExternal()方法.我需要问我的教授我是否可以制作自己的方法,但是没有parent()方法可以使用,所以我可以遍历树.虽然,我确实有一种root()方法.

有人可能会指出我正确的方向来弄清楚如何做到这一点？我没有想到没有递归的方法,因为我没有立即跳回树的方法.

我想找到二叉树中最长的路径.我计划将它们添加到列表中,这样我就能告诉我的敌人角色在简易模式上走很长的路.

private static <T> ArrayList<T> depthFirstSearch(BinaryNode<T> node)
{
    if(node != null)
    {
        Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();

        stack.push(node);

        while(!stack.isEmpty())
        {
            BinaryNode<T> currentNode = stack.pop();



            if(currentNode.right != null)
                stack.push(currentNode.right);

            // We want to visit left child first, so push left node last.
            if(currentNode.left != null) 
                stack.push(currentNode.left);
        }
    }
}

我写了那段代码,但这是一团糟.我正在尝试使用DFS找到最长的路径.有什么建议？

编辑:我确实有树的高度,我可以使用它.

public static <T> int height(BinaryNode<T> t)
{
    if (t == null)
        return -1;

    else 
        return 1 + Math.max(height(t.left), height(t.right));
}

我的问题是:我何时知道我找到了使用DFS的最长路径,以便我可以将节点添加到我的列表中？

Linux内核中rb_node的定义如下:

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
#define rb_color(r)   ((r)->rb_parent_color & 1)
#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)

我的问题是__rb_parent_color,其中最后一位是颜色,其余是指向其父级的指针.

我学到有人说最后2位__rb_parent_color因为没用aligned(sizeof(long)),但为什么呢？

不是sizeof(struct rb_node *)4还是不是sizeof(unsigned long)4？即使它们不相等,也应该aligned在Byte中如果没有对齐那么至少有一个整个Byte是无用的？

如何在Swift中打印二叉树,以便输入79561打印输出如下:

    7
   / \
  5   9
 / \
1   6

我试着使用一些代码来安排这个For Loops和If Statements,但它并没有奏效.我的代码是:

import UIKit

//Variable "node" used only to arrange it in output.
var node = "0"
var space = " "
var linkLeft = "/"
var linkRight = "\\"
var str = "Hello, playground"

var height = 6
var width = height * 2 + 1

print()

//Height
for h in 1...height {
    //Width
    for w in 1...width {
        switch h { …

我对“ 解析树”代码有疑问。当我尝试用后置订单显示它时，它给我一个错误消息，该错误消息应该是str参数而不是int。

from classStack import Stack
from classTree import BinaryTree

def buildParseTree(fpexp):
    fplist = fpexp.split()
    pStack = Stack()
    eTree = BinaryTree('')
    pStack.push(eTree)
    currentTree = eTree
    for i in fplist:
        if i == '(':
            currentTree.insertLeft('')
            pStack.push(currentTree)
            currentTree = currentTree.getLeftChild()

        elif i not in ['+', '-', '*', '/', ')']:
            currentTree.setRootVal(int(i))
            parent = pStack.pop()
            currentTree = parent

        elif i in ['+', '-', '*', '/']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree = currentTree.getRightChild()

        elif i == ')':
            currentTree = …