我读到前序和后序遍历也是为一般的(n元)树定义的,如下所示:
preOrder(v)
if(v==null) return;
print(v)
for each child w of v
preOrder(w)
postOrder(v)
if(v==null) return;
for each child w of v
postOrder(w)
print(v)
但中序遍历仅适用于二叉树。为什么我不能像上面展示的pre和postOrder例子那样做一个inOrder遍历方法?
int count(Node node) {
if (node == null)
return 0;
int r = count (node.right);
int l = count (node.left);
return 1 + r + l;
}
此函数返回根植于节点的二叉树中的节点数。有几篇文章说这是一个顺序前的遍历,但在我看来,这是一个后序遍历,因为在访问根之前,我们正在访问左边和右边的部分。我说错了吗?还是我“拜访”的想法是错的?
根据中的解释,我认为二叉树上的DFS等同于预序遍历根--left-right(我说的对吗?)
但是我只是做了一点搜索,得到了这个代码,它的作者声称DFS需要一个树来记录节点以前是否被访问过(或者我们在图的情况下需要这个吗?)。
// copyright belongs to the original author
public void dfs() {
// DFS uses Stack data structure
Stack stack = new Stack();
stack.push(this.rootNode);
rootNode.visited=t
我知道BST (二叉树)的顺序遍历并不是唯一的。例如 in-order traversal = [a, b, c] where a < b < c
1) b
/ \
a c
2) a
\
b
\
c
Two different BSTs output same in-order traversal array. 我不确定这对于后序遍历还是前序遍历是正确的-我找不到反例。前序遍历还是后序遍历唯一表示BST?
如果有一棵树,它有一个rootNode,并且它指向左右的子节点(二叉树),有没有办法像Objective-C2.0那样把它转换成快速枚举?所以我们可以这样做
for (id node in [tree allNodes]) {
// do something
}
顺序并不重要,但它可能是深度优先的顺序。
我有一个简单的二叉树,它没有父指针。
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Tree:
def __init__(self, root=None):
self.root = root
我需要自下而上遍历树,不能修改Node类,所以我想回忆一下父母。我可以这样修改Tree类:
class Tree:
def _