在Java中计算树中的节点

首先,我发誓这不是家庭作业,这是我在接受采访时被问到的一个问题。 我想我弄得一团糟(尽管我确实意识到解决方案需要递归)。 这是一个问题:

实现count()方法,该方法返回树中的节点数。 如果节点没有左子节点或右子节点,则相关的getXXChild()方法将返回null

 class Tree { Tree getRightChild() { // Assume this is already implemented } Tree getLeftChild() { // Assume this is already implemented } int count() { // Implement me } } 

我提出这个问题的理由只是好奇地看到了正确的解决方案,从而衡量了我的糟糕程度。

干杯,托尼

 int count() { Tree right = getRightChild(); Tree left = getLeftChild(); int c = 1; // count yourself! if ( right != null ) c += right.count(); // count sub trees if ( left != null ) c += left.count(); // .. return c; } 

一个简单的递归解决方案:

 int count() { Tree l = getLeftTree(); Tree r = getRightTree(); return 1 + (l != null ? l.count() : 0) + (r != null ? r.count() : 0); } 

一个不那么微不足道的非递归的:

 int count() { Stack s = new Stack(); s.push(this); int cnt = 0; while (!s.empty()) { Tree t = s.pop(); cnt++; Tree ch = getLeftTree(); if (ch != null) s.push(ch); ch = getRightTree(); if (ch != null) s.push(ch); } return cnt; } 

后者可能稍微提高内存效率,因为它用堆栈和迭代替换递归。 它也可能更快,但没有测量就很难分辨。 一个关键的区别是递归解决方案使用堆栈,而非递归解决方案使用堆来存储节点。

编辑:这是迭代解决方案的一种变体,它使用堆栈的次数较少:

 int count() { Tree t = this; Stack s = new Stack(); int cnt = 0; do { cnt++; Tree l = t.getLeftTree(); Tree r = t.getRightTree(); if (l != null) { t = l; if (r != null) s.push(r); } else if (r != null) { t = r; } else { t = s.empty() ? null : s.pop(); } } while (t != null); return cnt; } 

无论您需要更高效还是更优雅的解决方案,自然取决于树木的大小以及您打算使用此例程的频率。 Rembemer Hoare说:“过早优化是万恶之源。”

我更喜欢这个,因为它写道:

返回计数为left + count为rigth + 1

  int count() { return countFor( getLeftChild() ) + countFor( getRightChild() ) + 1; } private int countFor( Tree tree ) { return tree == null ? 0 : tree.count(); } 

更多的文字编程。

顺便说一句,我不喜欢Java上常用的getter / setter约定,我认为使用leftChild()会更好:

  return countFor( leftChild() ) + countFor( rightChild() ) + 1; 

就像Hoshua Bloch在这里解释http://www.youtube.com/watch?v=aAb7hSCtvGw一样。 32:03

如果你得到它,你的代码会读取……

但是,我必须承认get / set约定现在几乎是该语言的一部分。 🙂

对于许多其他部分,遵循此策略创建自我记录代码,这是好事。

托尼:我想知道,你在采访中的回答是什么。

 return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1; 

或类似的东西。

像这样的东西应该工作:

 int count() { int left = getLeftChild() == null ? 0 : getLeftChild().count(); int right = getRightChild() == null ? 0 : getRightCHild().count(); return left + right + 1; } 
 class Tree { Tree getRightChild() { // Assume this is already implemented } Tree getLeftChild() { // Assume this is already implemented } int count() { return 1 + getRightChild() == null? 0 : getRightChild().count() + getLeftChild() == null? 0 : getLeftChild().count(); } } 

您可以通过多种方式遍历树来计算树。 只需预先遍历遍历,代码就是(基于您定义的函数):

 int count() { count = 1; if (this.getLeftChild() != null) count += this.getLeftChild().count(); if (this.getRightChild() != null) count += this.getRightChild().count(); return count; } 

实施方法:

 public static int countOneChild(Node root) { ... } 

计算具有一个子节点的二叉树中的内部节点数。 将函数添加到tree.java程序。

我通过预先订购递归来做到这一点。 尽管使用localRoot并不完全遵循访谈格式,但我认为你明白了。

 private int countNodes(Node localRoot, int count) { if (localRoot == null) return count; count++; // Visit root count = countNodes(localRoot.left, count); // Preorder-traverse (left) count = countNodes(localRoot.right, count); // Preorder-traverse (right) return count; } public int countNodes() { return countNodes(root, 0); } 

这是一个标准的递归问题:

 count(): cnt = 1 // this node if (haveRight) cnt += right.count if (haveLeft) cnt += left.count return cnt; 

非常低效,如果树很深,也是一个杀手,但这是你的递归…

 int count() { int retval = 1; if(null != getRightChild()) retval+=getRightChild().count(); if(null != getLeftChild()) retval+=getLeftChild().count(); return retval; } 

上帝,我希望我没有犯错误。

编辑:我确实做到了。

当然,如果你想在计算时避免访问树中的每个节点,并且处理时间对你来说比内存更有价值,你可以通过在构建树时创建计数来作弊。

  1. 在每个节点中有一个int计数,初始化为1,它表示以该节点为根的子树中的节点数。

  2. 插入节点时,在从递归插入例程返回之前,递增当前节点的计数。

 public void insert(Node root, Node newNode) { if (newNode.compareTo(root) > 1) { if (root.right != null) insert(root.right, newNode); else root.right = newNode; } else { if (root.left != null) insert(root.left, newNode); else root.left = newNode; } root.count++; } 

然后从任何点获取计数只需要查找node.count

我的第一次尝试没有任何新的东西要添加,但后来我开始怀疑递归深度以及是否有可能重新排列代码以利用最新Java编译器的尾调用优化function。 主要问题是null测试 – 可以使用NullObject解决。 我不确定TCO是否可以处理两个递归调用,但它至少应该优化最后一个。

 static class NullNode extends Tree { private static final Tree s_instance = new NullNode(); static Tree instance() { return s_instance; } @Override Tree getRightChild() { return null; } @Override Tree getLeftChild() { return null; } int count() { return 0; } } int count() { Tree right = getRightChild(); Tree left = getLeftChild(); if ( right == null ) { right = NullNode.instance(); } if ( left == null ) { left = NullNode.instance(); } return 1 + right.count() + left.count(); } 

NullNode的精确实现取决于Tree中使用的实现 – 如果Tree使用NullNode而不是null,那么子访问方法可能会抛出NullPointerException而不是返回null。 无论如何,主要的想法是使用NullObject以试图从TCO获益。

在访谈中应该预期与二叉树相关的问题。 我会说在下次采访之前需要时间并通过这个链接。 解决了大约14个问题。您可以查看解决方案是如何完成的。 这将让您了解如何在将来解决二叉树问题。

我知道你的问题是计数方法特有的。这也是我提供的链接中实现的

 class Tree { Tree getRightChild() { // Assume this is already implemented } Tree getLeftChild() { // Assume this is already implemented } int count() { if(this.getLeftChild() !=null && this.getRightChild()!=null) return 1 + this.getLeftChild().count() + this.getRightChild().count(); elseif(this.getLeftChild() !=null && this.getRightChild()==null) return 1 + this.getLeftChild().count(); elseif(this.getLeftChild() ==null && this.getRightChild()!=null) return 1 + this.getRightChild().count(); else return 1;//left & right sub trees are null ==> count the root node } }