关于获取二进制树中的节点数的问题 [英] A question on getting number of nodes in a Binary Tree

问题描述

我已经写了两个函数（伪代码），用于计算树的根数和二进制树的树高度。
最重要的是，二进制树被表示为第一个chiled / next兄弟格式。

所以

  struct TreeNode 
 {
对象元素; 
 TreeNode * firstChild; 
 TreeNode * nextSibling; 
} 
  

计算节点数：

  public int countNode（TreeNode root）
 {
 int count = 0; 
 while（root！= null）
 {
 root = root.firstChild; 
 count ++; 
} 
 
返回计数; 
} 
 
 public int countHeight（TreeNode root）
 {
 int height = 0; 
 while（root！= null）
 {
 root = root.nextSibling; 
 height ++; 
} 
 
返回高度; 
  

}

这是问题我在算法书上看到，我的解决方案似乎有一些问题，我也没有得到使用这个第一个孩子/右兄弟二叉树表示的点，你能给我一些想法和反馈，请？
干杯！

解决方案

下一个兄弟姐妹和第一个孩子的使用大概可视化如下：

  A1  -  A2  -  A3 
 | | 
 | B1  -  B2  -  B3 
 | | 
 D1  -  D2 C1 
  

图中的水平线代表 nextSibling ，垂直线对应于 firstChild 链接。对于某些问题，这可能是自然可视化（但是对于其他一些问题，您可能更喜欢使用具有两个子节点的常规树 - 它们是等价的）。

代码似乎缺少一些东西，因为你并没有真正计数任何东西。我想你想在中分别 count ++ height ++ 而循环。

无论如何，要计算节点数，您需要添加子节点数以及同一级别的节点数（兄弟姐妹）。对于合理的小树，可以递归地执行：

  public int countNode（TreeNode root）{
 if（root == null）return 0; 
 return 1 + countNodes（root.firstChild）
 + countNodes（root.nextSibling）; 
} 
  

对于较大的数据结构，您需要将节点存储为处理在一个内存中的堆栈，以避免堆栈溢出（sic！）

要计算高度，你首先需要决定如何定义高度。当您遵循 firstChild 链接（即 A1 - > D1 ）或您想要最长时间树（任何地方）（路径为 A1 - > A2 - > B1 - > B2 - > C1 ）。在第一种情况下，您的实施将是正确的。在第二种情况下，您需要一个类似于计数节点的递归函数（而不是添加，您将选择较大的子树）。

I have written up two functions (pseudo code) for calculation the number of nodes and the tree height of a Binary Tree,given the root of the tree. Most importantly,the Binary Tree is represented as the First chiled/next sibling format.

so

struct TreeNode
{
  Object element;
  TreeNode *firstChild;
  TreeNode *nextSibling;
}

Calculate the # of nodes:

public int countNode(TreeNode root)
{
     int count=0;
     while(root!=null)
     {
        root= root.firstChild;
        count++;
     }

      return count;
}

public int countHeight(TreeNode root)
{
     int height=0;
     while(root!=null)
     {
        root= root.nextSibling;
        height++;
     }

  return height;

}

This is one of the problem I saw on an algorithm book,and my solution above seems to have some problems,also I didn't quite get the points of using this First Child/right sibling representation of Binary Tree,could you guys give me some idea and feedback,please? Cheers!

解决方案

The use of next sibling and first child can be probably visualized like this:

A1 -- A2 -- A3
|     |    
|     B1 -- B2 -- B3
|           |
D1 -- D2    C1

The horizontal lines in the diagram represent nextSibling and the vertical lines correspond to firstChild link. For some problems, this may be natural visualization (but for some other problems, you may prefer usual tree with two sub-nodes - they are equivalent).

Your pseudo-code seems to be missing something, as you aren't really counting anything. I suppose you wanted to have count++, respectively height++ in the while loop.

Anyway, to count the number of nodes, you need to add the number of nodes of the child as well as the number of nodes on the same level (siblings). For reasonably small trees, this can be done recursively:

public int countNode(TreeNode root) { 
  if (root == null) return 0;
  return 1 + countNodes(root.firstChild) 
           + countNodes(root.nextSibling);
}

For larger data structures, you'll need to store the nodes "to be processed" in an in-memory stack to avoid stack overflow (sic!)

To count the height, you first need to decide how is the height defined. Is it the path when you follow firstChild links (that is A1 -> D1) or do you want the longest path in the tree (anywhere) (which would be A1 -> A2 -> B1 -> B2 -> C1). In the first case, your implementation would be correct. In the second case, you'd need a recursive function similar to the one for counting nodes (instead of adding, you'd pick the larger sub-tree).

这篇关于关于获取二进制树中的节点数的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！