这个二叉树的伪代码是什么

Question

基本上，我需要拿出一个伪代码。我现在拥有的是

dictionary={}
if节点。左==无和节点。右==无
访问（节点）
字典[节点]=1

这只是叶节点，如何获取每个节点（父节点和根节点）的大小？

Answer 1

这个概念是，每个节点都会知道它的子树大小，首先知道它的所有子节点的子树大小，在这里是最大的两个子节点，因为它是一个二叉树，所以，一旦它知道所有子节点的子树大小，它就可以将所有子节点相加，最后在结果中加1，然后它的父节点也会做同样的事情，依此类推到根节点。若我们考虑叶节点，它并没有子节点，所以结果子树的大小只有1，其中包含它自己。

这个想法很清楚，编写代码很容易，在遍历时，我们将首先知道当前节点的子节点的子树大小，然后在其中添加1，如果是叶节点，则子树大小仅为1，下面是traverse Function的伪代码，它查找每个节点的子树大小并将它们存储在dictionary sizeDictionary中，并使用范围更大的访问字典/数组跟踪访问的节点。

traverse(Tree curNode, dictionary subTreeSizeDictionary)
   visited[curNode] = true
   subtreeSizeDictionary[curNode] = 0
   for child of curNode
       if(notVisited[child])
           traverse(child , sizeDictionary)
           subtreeSizeDictionary[curNode] += subtreeSizeDictionary[child]
   subtreeSizeDictionary[curNode] += 1;

这里是二叉树，但是从伪代码中可以看出，这个概念可以用于任何有效的树，时间复杂度为O（n），因为我们只访问了每个节点一次。

Answer 2

您可以进行后序遍历来查找每个节点的大小。

这个想法是首先处理左树和右树。然后，在处理它们之后，您可以使用这些数据来处理当前节点。

这应该类似于：

count = 0
if (node.left != none)
  count += visit(node.left)
if (node.right != none)
  count += visit(node.right)
// self is included.
count += 1 
// update the node
node.size = count
return count

不需要访问节点的字典，因为这是一棵树，它保证结束。

作为旁注，每个节点的size属性是一个重要的属性。它基本上将您的树升级为订单统计树