标签: tree-traversal

在由具有指向父级、兄弟级和第一个/最后一个子级的指针的节点表示的通用树中，如下所示：

class Tnode {

    def data
    Tnode parent = null
    Tnode first_child = null, last_child = null 
    Tnode prev_sibling = null, next_sibling = null 

    Tnode(data=null) {
        this.data = data
    }
}

是否可以在不使用任何其他辅助结构（例如队列）的情况下进行迭代（非递归）广度优先（级别顺序）遍历。

所以基本上：我们可以使用单节点引用进行回溯，但不能保存节点集合。到底能不能做到是理论上的部分，但更实际的问题是，在大段上不回溯的情况下，能否高效地做到。

为什么通过根、左和右遍历树称为预排序？这不应该是有序的，因为根总是在第一位吗？

为什么这样称呼它对我来说没有意义，因为根始终是第一个元素。

我在 leetcode 中遇到了以下问题 - https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

我能够编写下面的算法（找到前序和后序遍历并保存它们。然后从遍历中重建树），但遇到了一个更基本的问题 - 即，如何构造具有重复值的二叉树。我失败的测试用例是 [3,2,4,3]，其中前序和后序是相同的。

任何帮助和建议表示赞赏。

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        ArrayList<Integer> inorder = inOrder(root, new ArrayList<Integer>());
        ArrayList<Integer> preorder = preOrder(root, new ArrayList<Integer>());
        StringBuilder sb = new StringBuilder("");
        for(int val : inorder){
            sb.append(val + " ");
        }
        sb.append("|");
        for(int val : preorder){
            sb.append(val + " ");
        }
        String serialized = sb.toString();
        return serialized;
    }

    // Decodes your encoded data …

使用jQuery我想改变这个:

<h3>Question 1</h3>
<p>Answer 1 P1</p>
<p>Answer 1 P2</p>

<h3>Question 2</h3>
<p>Answer 2 P1</p>
<p>Answer 2 P2</p>
<p>Answer 2 P3</p>

成:

<ul>
   <li>
       <h3>Question 1</h3>
       <div>
          <p>Answer 1 P1</p>
          <p>Answer 1 P2</p>
       </div>
    </li>
    <li>
       <h3>Question 2</h3>
       <div>
          <p>Answer 2 P1</p>
          <p>Answer 2 P2</p>
          <p>Answer 2 P3</p>
       </div>
    </li>
</ul>

任何建议都会非常感激.

谢谢!

给定一个二叉树,其节点具有以下类型:

struct Node {
  Node* left;
  Node* right;
  int data;
  Node* foo;   // uninitialized - use it any way you like
};

按级别顺序打印树数据,并使foo每个节点的成员指向下一个兄弟节点.

除了具有非数组类型的常量变量外,我们不允许使用任何其他存储(特别是不允许使用外部队列).

我在Rosettacode.org上看到关于树遍历的这个页面.我正在看Go的实现,我是Go的新手,这就是为什么我想要你的帮助.

在文件的开头,创建一个结构.到目前为止,这是有道理的.但我不明白的是这个:

type node struct {
    value       int
    left, right *node
}

的left, right *node一部分.我知道左,右变量是指向节点的类型指针.但我不明白为什么,首先我不知道你可以包含你正在创建的类型,在本例中是实际结构本身的节点.然后我真的不明白为什么代码不只是说left, right node.

func (n *node) iterPreorder(visit func(int)) {
    if n == nil {
        return
    }
    visit(n.value)
    n.left.iterPreorder(visit)
    n.right.iterPreorder(visit)
}

我接下来的事情是,visit变量如何是类型的func(int).然后我也不知道如何iterPreorder在函数中使用iterPreorder.

最后我想问一下,这段代码做了什么？

tree := &node{1,
    &node{2,
        &node{4,
            &node{7, nil, nil},
            nil},
        &node{5, nil, nil}},
    &node{3,
        &node{6,
            &node{8, nil, nil},
            &node{9, nil, nil}},
        nil}}

谢谢,这里是Rosettacode.org上完整代码的链接.

我是SML的新手并且正在进行关于树遍历的练习.这是问题的设定.

datatype 'a bTree = nil | bt of 'a bTree * 'a * 'a bTree;

我需要编写一个函数inorder,它接受一个二叉树并在inorder遍历中返回树的所有成员的列表.

我写了这一行:

fun inorder(nil) = nil
  | inorder(bt(left,key,right)) = inorder(left) @ [key] @ inorder(right);

但得到一些错误,不知道如何解决:

Error: operator and operand don't agree [tycon mismatch]
operator domain: 'Z list * 'Z list
operand:         'Z list * 'Y bTree
in expression:
  (key :: nil) @ inorder right

Error: operator and operand don't agree [tycon mismatch]
operator domain: 'Z list * 'Z list
operand:         'Y bTree * _ …

正如维基百科所述，有多种算法可用于遍历树数据结构。但是有些算法是其他算法的组合，比如双向搜索，它几乎对其他图而不是树有用。但是对于一棵树，我们几乎不知道这棵树的末端，我们只能从根或它的子节点开始。

在这种情况下，我们可能能够在搜索过程中加入多处理或多线程。但我找不到任何描述这一点的综合方法。

现在我的问题是，当我们无法访问整个数据结构（以便能够索引它们等，例如文件目录）时，基本上什么是遍历树的最优化方法？

我在计算从根到二叉树中指定节点的路径时遇到了麻烦（这特别是关于此问题的Python解决方案）。

这是一个例子。给定下面的二叉树，如果我指定值为4的节点，我想返回[1、2、4]。如果我指定值为5的节点，我想返回[1、2、5]。

       1
     /  \
   2      3
 /  \
4    5

这是我尝试的解决方案。

class TreeNode:
 def __init__(self, x):
     self.val = x
     self.left = None
     self.right = None

def path(root, k, l=[]):
    if not root:
        return []
    if root.val == k:
        return l

    # Pre-order traversal: Visit root, then left, then right.
    l.append(root.val)
    path(root.left, k, l)
    path(root.right, k, l)
    return l

现在如果我运行这个

>>> a = TreeNode(1)
>>> b = TreeNode(2)
>>> c = TreeNode(3)
>>> d = TreeNode(4)
>>> e = TreeNode(5) …

我有二进制搜索树,必须执行三种类型的树遍历:这个结果是否正确？

Pre-order (root,left,right): 30,15,59,43,40,92

In-order (left,root,right): 15,30,59,40,43,92

Post-order (left,right,root): 15,59,40,43,92,30

更新:

有序: 15,30,40,43,59,92(投影？)

下订单: 15,40,43,92,59,30.

这样对吗？