int count(Node node) {
if (node == null)
return 0;
int r = count (node.right);
int l = count (node.left);
return 1 + r + l;
}
此函数返回根植于节点的二叉树中的节点数。有几篇文章说这是一个顺序前的遍历,但在我看来,这是一个后序遍历,因为在访问根之前,我们正在访问左边和右边的部分。我说错了吗?还是我“拜访”的想法是错的?
我读到前序和后序遍历也是为一般的(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遍历方法?
我知道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?
根据中的解释,我认为二叉树上的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
我刚才问过这个问题,但我不知道玫瑰树和普通树有何分别。现在我知道数据结构略有不同。
data GTree a = Leaf a | Branch [GTree a]
我想写一个postorderG函数,它会给我一个列表,其中包含所有后序的Gtree元素。
我知道如何在二叉树上这样做。
data BTree a = Nil | Node a (BTree a) (BTree a)
postOrder :: BTree a -> [a]
postOrder Nil = []
postOrder (Node x lt rt) = (postOrder lt) ++ (postOrder r