标签: binary-tree

我编写了以下代码,用于从inorder和preorder遍历构造树.它看起来对我来说是正确的,但它产生的最终树不具有与它构建的输出相同的顺序输出.任何人都可以帮我找到这个功能的缺陷吗？

public btree makeTree(int[] preorder, int[] inorder,  int left,int right)
{
    if(left > right)
        return null;

    if(preIndex >= preorder.length)
        return null;

    btree tree = new btree(preorder[preIndex]);
    preIndex++;

    int i=0;
    for(i=left; i<= right;i++)
    {
        if(inorder[i]==tree.value)
            break;

    }


        tree.left = makeTree(preorder, inorder,left, i-1);
        tree.right = makeTree(preorder, inorder,i+1, right );

    return tree;

}

注意:preIndex是在函数外声明的静态.

任何人都可以向我解释双顺序遍历吗？

        A
      /   \
     B     E
   /  \   /  \
  C   D  F    G

双顺序遍历输出:ABCCBDDAEFFEGG

我对解释而不是代码感兴趣.

谢谢

我有下面的数组,我想以特定的HTML列表格式输出.

我的PHP数组如下:

Array
(
    [MAIN] => Master Product
    [ID1] => Array
        (
            [0] => Product 1
        )

    [ID2] => Array
        (
            [0] => Product 2
            [ID3] => Array
                (
                    [0] => Product 3
                )

            [ID4] => Array
                (
                    [0] => Product 4
                )
        )
)

我正在寻找的HTML列表格式如下.

<ul id="treeview">
    <li>Master Product
        <ul>
            <li>Product 1</li>
            <li>Product 2
                <ul>
                    <li>Product 3</li>
                    <li>Product 4</li>
                </ul>
            </li>
        </ul>
    </li>
</ul>

任何帮助,将不胜感激.

我有一个相当愚蠢的问题,我发誓不是家庭作业.对于我的生活,我不记得我是否研究过这样做的算法,而我的思维/创造力让我失望.

我有一个唯一节点列表.我需要生成包含这些节点的二叉树的所有唯一排列.如果你想知道,手性问题很重要; 在其轴(左/右)上翻转的二叉树是不一样的.

一些背景信息,如果你想知道:它是一个进化程序的种子创建算法,所以大量的小种子是好的.

编辑:澄清唯一性

Examples:

This:
  1
 / \
2   3

Is not the same as this:
  1
 / \
3   2

Nor is it the same as this:

    1
   /
  3
 /
2   

Nor this:

1
 \
  2
   \
    3

我有一个大小为10的整数数组.我需要绘制完成的二叉树.现在我需要使用siftup过程插入其他三个元素.显示每个插入后的最大堆.

我不确定是什么显示每个插入后的最大堆.这是否意味着每次插入一个元素时我需要显示最大堆的大小？

定义(最大堆)HEAP(X)设X是一个完全有序的集合.X上的堆是空的,∅,或者它是一个完整的二叉树,t,包括nt≥1个节点到每个节点,其中X的值被分配,使得:节点i的值≤节点i的父节点的值,i = 2,3,...,nt.堆的大小是树中的节点数.当且仅当其大小为0时,堆为空.

max heap的定义是这样的,但对我来说看起来有点模棱两可.

我有一本书以非常糟糕的方式解释二元搜索树背后的理论我知道左右两个孩子的顺序有一些东西,但我仍然无法得到一个大于另一个前一个级别的想法.

以这个字符串树为例:

(抱歉我的油漆)这个例子直接来自我的书:)

有人可以向我解释订单吗？这背后的逻辑是什么？

我正在尝试编写一种方法来搜索二叉树的所有节点以获取传递的值,并在找到时返回该节点.我似乎无法正确地搜索树的两侧.这是我到目前为止所拥有的.

private Node locate(String p, Node famTree)
{  
    if (root == null)//If tree empty return null;
        return null;
    if (famTree.value.equals(p)) //If leaf contains the passed parent value the boolean becomes true.
        return famTree;
    if (famTree.left != null)
        return locate(p,famTree.left);
    else
        return locate(p,famTree.right);

}

public static void preorder(Node root) {
    if(root == null) return;

    root.printValue();
    preorder(root.getLeft());
    preorder(root.getRight());
}

我试图多次通过这个功能,但我仍然无法弄清楚如何遍历所有左边的孩子后,算法会回到最近的祖先(父母).有人可以向我解释一下.

我发现这个代码用于在Java中将二叉树展平为数组.我很难理解它是如何工作的.

这是代码:

private static int FlattenTreeIntoArray(Node tree, int[] array, int i)
{
    if (tree == null) return i;
    // Flatten left subtree
    i = FlattenTreeIntoArray(tree.Left, array, i);
    // Get data from the current node
    array[i] = tree.Data;
    // Flatten right subtree
    i = FlattenTreeIntoArray(tree.Right, array, i + 1);
    return i;
} 

我的问题如下:

1. 这是辅助方法,实际调用的方法是什么,或者作为参数(int[] array和int i)传递的是什么？我们不知道二叉树的大小.

2. 该方法如何工作？当它tree是null,它返回i.那是什么意思？

3. 扁平化是如何发生的？为什么i+1被传递给right tree,但i要left tree？

如果您可以使用此二叉树进行演示,则可以很容易地遵循:

来自脚本语言背景和一些C,试图"学习"Rust让我质疑我的能力.我正在试图找出如何更改自有指针,并努力做到这一点.

除了从额外的lib中复制之外,我无法弄清楚我在二叉树上需要的递归.特别是,我不知道如何换出指针分支.虽然使用链表我可以作弊并使用临时向量来返回一个新列表,或者在列表头前添加一个新的Cons(值,~Cons),但是分支让我感到困惑.

enum NaiveTreeNode {
    NNil,
    NNode(~NaiveTreeNode, ~NaiveTreeNode, int, char) 
    //         left            right          key   val
}

impl NaiveTreeNode {
  fn eq(first_node: &NaiveTreeNode, second_node: &NaiveTreeNode) -> bool {
      match (first_node, second_node) {
          (&NNil, &NNil)              => true,
          ( &NNode( ~ref left_lval, ~ref left_rval, left_leafkey, left_leafval ),
            &NNode( ~ref right_lval, ~ref right_rval, right_leafkey, right_leafval )
          ) if left_leafkey == right_leafkey && left_leafval == right_leafval => {
              NaiveTreeNode::eq(left_lval, right_lval) && NaiveTreeNode::eq(left_rval, right_rval)
          },
          _                           => false
      }
  }

  fn add_branch(&mut self, node_to_add: ~NaiveTreeNode) { …