标签: binary-tree

我是C的新手,并且一直在学习K&R的书"The C Programming Language".在对二叉树进行练习之后,我想为char*,long和double制作二叉树的标题.

下面的代码中有一个函数让我感到悲伤 - 它应该填充一个字符指针数组,其中的值以字典顺序存储在树中,但它在某处有一个bug.这是String Tree Header btree.h的代码:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    /************** TYPES **************/
    typedef struct ctree 
    {
        char *name;
        ctree *left;
        ctree *right;
    }; 
    /************** Globals **************/

    static int c_inc = 0;

    /************** Function Prototypes **************/

    ctree *add_to_c_tree  (ctree *cnode, char *name);
    void print_c_tree     (ctree  *cnode);
    ctree *c_tree_alloc   (void);
    void   c_tree_free    (ctree  *cnode);
    void  return_c_tree   (ctree  *cnode, char **array);

    /************** Function Definitions **************/

    /* add_to_c_tree() : Adds a new node to a *character binary …

我有这个问题要做:

"定义一个函数findpath:: BTree a -> a -> Path(其中Btreea在前面的问题中定义),给定二叉树t和值x,返回从根t到叶子的路径(x如果有的话),Nothing否则返回值.运行时间您的程序应该是树中节点数的线性."

到目前为止,我有:

data Maybe a = Nothing | Just a
data BTree a = Leaf a | Fork (BTree a) (BTree a)
type Path = Maybe [Dir]
data Dir = Left | Right

findpath :: Eq a => BTree a -> a -> Path
findpath (Leaf y) x = if y==x then ??? else Nothing
findpath (Fork l r) …

我需要一个非常快的python中的树对象。查找的速度比内存更重要。叶节点是我想要的值。因此，如果给定 state=NY、postion=3、hourOfDay=2 和 dayOfWeek=3，我需要快速获得值 =100。带 * 的节点是叶节点。

0) root
    1) {state: [NY,LA]}
        2) {howOfDay:[1,2,3,4,5], postion:[1,2,3]}
                             *3) {dayOfWeek:[234]} => value:100
            4) {state: [FL,NV,……rest of the states]}
                5) {howOfDay:[1,6,7,8,9….23]}
                      *6) {dayOfWeek:[1,5,6,7]} => value:120

在我的数据库中，我的数据看起来像这样，属性为 json 对象。

parent child attribute value

0 1 state NY,LA
1 2 {howOfDay:[1,2,3,4,5], postion:[1,2,3]}
2 3 dayOfWeek dayOfWeek [2,3,4] 100
0 3 state  [FL,NV,……rest of the states]
4 5 howOfDay:[1,6,7,8,9….23]
5 6 dayOfWeek:[1,5,6,7] 120

那么，我应该使用什么 python 库和树结构来最好地找到一个值？如何将数据转换为最好的快速查找？

我和我的朋友正在做一个简单的 Python 项目。实际上，我们正在以自己的方式实现前缀并行求和算法。

我们正在创建和处理一个非常奇怪的格式的二叉树。我们希望将此格式转换为 Tree 打印库/软件（如 ete2）接受的格式。

因此，树的每一层都以这种方式推送到列表中

[ [level0], [level1], ... [level i-1], [root] ]

在我们的格式中，每个内部列表（树的级别）都有偶数个节点或叶子。

例如，假设我们有这个输入：[1, 2, 3, 4, 5]。这将产生以下输出列表：[[1, 2, 3, 4], [3, 7], [10, 5], [15]]

上述输出示例的问题在于，有时叶子不在最后一层，但它们包含在上层列表中。这使得处理列表列表和区分节点和叶子并将它们排列在正确位置变得困难。

我们想将其可视化如下：

http://i.imgur.com/BKrqNZi.png

其中括号中的数字是节点，其他数字是叶子。

为了产生这个输出树，我们想使用一个树绘图库。他们中的大多数人期望这种格式：[root, [left], [right]]

所以，在我们的例子中，我们的格式应该是这样的：

[15, [10, [3, [1], [2]], [7, [3], [4]] ], [5] ]

因为我们目前无法重写代码的整个逻辑，所以我们正在寻找一种巧妙的方法将我们奇怪的格式转换成那种格式。

欢迎任何想法。非常感谢您提前。

我目前正在尝试获取文本文件,并将文本文件分解为单词.然后我尝试将每个单词存储为二叉树中的节点.这样做后,我也尝试打印二叉树.出于某种原因,当我运行我的代码时,我现在陷入无限循环,但我不明白在哪里或为什么这是如果你可以看到我被抓到哪里将是一个很大的帮助谢谢

public class Tester {

public static void main(String[] args) throws FileNotFoundException {

    Tester run = new Tester();
    run.it();

}

public void it() throws FileNotFoundException { 

    BTree theTree = new BTree();

    String str = this.readInFile();

    int position = 0;

    String newWord = this.breakIntoWords(str, position);

    while(newWord != null){

        theTree.add(newWord);

        newWord = this.breakIntoWords(str, position);

    }

    theTree.print();

}

public String readInFile() throws FileNotFoundException {


    String myFile = "";
    int numWords = 0;

    Scanner myScan = new Scanner(new File("Dracula.txt"));

    while(myScan.hasNext() == true) {

        myFile …

我正在尝试使用递归初始化二叉树。

@tailrec
def expressionToTreeNodeConversion(expression:String): TreeNode = {

    var chars = expression.toCharArray

    var operatorIndex = findIndexOfMiddleOperator(chars)
    var isOperator = true
    while(operatorIndex==(-1) & isOperator) {

      if (!(chars.contains(OPEN_BRACKET_CHAR) | chars.contains(CLOSE_BRACKET_CHAR)))
        isOperator = false
      else {
        chars = chars.slice(1, chars.length-1)
        operatorIndex = findIndexOfMiddleOperator(chars)
      }
    }

    //If this is an operand
    if (!isOperator)
      return new OperandNode(chars.mkString(""))

    //If this is an operator, recursively call for sub nodes
    val  node = chars(operatorIndex).toString match {
      case AND => new AndNode()
      case OR => new OrNode()
    }

    node.left = …

我刚刚创建了一个测试二叉树实现高度的方法,如下所示:

public int height() {
    return height(rootNode);
}
private int height(BinaryTreeNode node) {
    if(node == null) return -1;
    else return 1 + Math.max(height(node.getLeftChild()), height(node.getRightChild()));
}

但是当我添加节点1-6时,它返回高度6,而不是7.

这是我的二叉树代码:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E extends Comparable<E>>
{
    private class BinaryTreeNode
    {
        private E value;
        private BinaryTreeNode leftChild, rightChild;

        public BinaryTreeNode(E value) {
            this(value, null, null);
        }

        public BinaryTreeNode(E value, BinaryTreeNode leftChild, BinaryTreeNode rightChild) {
            this.value = value;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }

        public E …

我想使用 Python 将二叉树转换为数组，但我不知道如何为树节点提供索引？

我已经使用公式 left_son=(2*p)+1; 和 right_son=(2*p)+2; 在java中但我被困在python中。是否有任何函数可以为 python 中的树节点提供索引？

我决定将数组存储到二叉树中，以便数组的所有元素都位于树的右侧。如何计算所有这些元素？

int get_length(Node * array) {
   static int len = 0;
   if (array == NULL) return len;
   else {
       len++;
       get_length(array->right);
   }
}

静态变量问题：每次使用该函数后，变量len未复位，返回长度不正确。每次使用后，该变量都会增加。

我有以下功能，我不确定他们是在实现二叉树还是 B 树。

这是代码：

def foo(x):
    if x:
        a, b, c = x
        return foo(a) + b + foo(c)
    else:
        return 0

谁能帮我弄清楚正在使用哪些数据结构？