检查二叉树是否具有相同的结构

我应该检查一个二叉树是否与使用递归的另一个树具有相同的结构。我遇到麻烦的部分是搞清楚如何在每个级别检查是否存在左侧或右侧并将其与其他树进行比较。任何形式的帮助，将不胜感激谢谢。检查二叉树是否具有相同的结构

public boolean hasSameStructureAs(BinaryTree tree){ 
    //If left and right are null they are still similar 
    if(leftChild == null && rightChild == null); 
     return true; 
    if (leftChild == null && rightChild != null) 
     return false; 
    if (leftChild != null && rightChild == null){ 
     return false;

//我有下面的代码的递归部分的麻烦，我想我有这部分正确

if (!tree.equals(rightChild.left,leftChild.left)) return false; 
    if (!tree.equals(rightChild.right, leftChild.right)) return false; 

    return true;

下面是一些构造函数和get/set方法。

public class BinaryTree { 
private String data; 
private BinaryTree leftChild; 
private BinaryTree rightChild; 

public BinaryTree(String d) { 
    data = d; 
    leftChild = null; 
    rightChild = null; 
} 

public BinaryTree(String d, BinaryTree left, BinaryTree right) { 
    data = d; 
    leftChild = left; 
    rightChild = right; 
} 

public String getData() { 
    return data; 
} 

public BinaryTree getLeftChild() { 
    return leftChild; 
} 

public BinaryTree getRightChild() { 
    return rightChild;}

来源

2014-03-30 user3450909

您的BinaryTree是递归数据结构，因此您可以在编写递归函数时按照常用方法递归执行检查 - 假定它已经写入。

以下是我的意思：想象一下，您的BinaryTree类有一个工作hasSameStructureAs方法，您只能在子节点上使用该方法。你将如何检查当前节点？

检查tree.getLeftChild()的左侧子树再次this.leftChild;如果hasSameStructureAs返回false，则返回false。如果两个左子树null，继续检查
检查的tree.getRightChild() agains this.rightChild右子树;如果hasSameStructureAs返回false，则返回false。如果两个右子树null，或hasSameStructureAs返回true，返回true为好。

这就是它 - 你做！你所要做的全部方法是null检查它的左右子树，并且在它们上面调用hasSameStructureAs。

来源

2014-03-30 00:57:08 dasblinkenlight

感谢使它很清楚，你很不错！ – user3450909

我需要看到你的.equals方法是绝对肯定的，但它会显示你没有递归执行它。如果你希望它是递归的，如果两棵树都有一个左边的孩子，或者两个都有一个正确的孩子（或者两者都有）递归地返回该方法，那么将这些孩子作为新的“根”来检查他们的孩子。

如果他们不匹配的任何一点，返回false。如果你已经达到所有孩子都是叶子的地步（无效孩子），那么返回true。

除此之外，它是作为制作方法预购递归一样简单。（访问家长 - >访问左边的孩子，如果有的话 - >访问正确的孩子，如果有的话，每次访问孩子重复过程）。

来源

2014-03-30 00:52:22 Gurgadurgen

假设你没有覆盖等于，这样的：你想要什么

if (!tree.equals(rightChild.left,leftChild.left)) return false;

不会做。 equals（）的默认实现返回（this == other），并且只有当它们是完全相同的对象（即在内存中的相同位置）时才是如此。

你居然没有任何递归呢。递归意味着函数自己调用。考虑左右儿童也是树木。你已经有了一个方法hasSameStructureAs，那完成后，对于等结构的树将返回true。因此，你的解决方案应该在两棵树的左边和右边的孩子上合并调用hasSameStructureAs（），并且组合从每个“边”获得的值。

一般而言，递归问题的策略是将其分解为递归情况和一个或多个基本情况。用树结构，你的基本情况将涉及叶子。树中的叶子是子链接为空的节点。

想象一下，您有一个布尔值用于临时存储左侧是否相等。

如果this.leftChild和other.leftChild都为null，leftEq是真的
如果只是其中之一为null，leftEq是假
否则leftEq是this.leftChild.hasSameStructure（other.leftChild ）

你会这样做rightEq然后返回leftEq和rightEq。

就我个人而言，我认为让这个棘手的问题考虑的事情之一是，你的hasSameStructure是从其中一棵树的角度写的。也许想想如何用外部方法hasSameStructure(treeA, treeB)来解决它，然后将其转化为实际要求的内容。

来源

2014-03-30 01:22:36 johncip

线索＃1：你的方法被称为“hasSameStructureAs”。为了递归，它需要调用“hasSameStructureAs”。线索＃2：你的代码被传递了一个名为“tree”的参数，但你甚至没有看它。建议：将BinaryTree重命名为Node（因为它是一个有孩子的节点，而不是树），并将“tree”参数重命名为“that”，然后明确使用“this”访问“this “对象，这样就可以看到什么是属于‘本’与‘说’：

public boolean hasSameStructureAs(Node that) 
    { 
    // first, only bother to check if the children are different at all 
    // (if they are both null, for example, then they will be equal) 
    if (this.leftChild != that.leftChild) 
     { 
     // second, since we already know that they are unequal, if either 
     // one of them is null, then the data structure is unequal 
     if (this.leftChild == null || that.leftChild == null) 
      { 
      return false; 
      } 

     // third, since neither one is null, let's recursively ask them if 
     // they are the same 
     if (!this.leftChild.hasSameStructureAs(that.leftChild)) 
      { 
      return false; 
      } 
     } 
    // and so on ..

而且，因为这可能是一个家庭作业，你真的需要学习的身影一些它在你的拥有。

来源

2014-03-30 02:12:54 cpurdy

对分配同样的问题，这是我做的，可能不是最有效的，但结果是准确的

public boolean hasSameStructureAs(BinaryTree tree){ 


    if(tree.getLeftChild() == null && this.getLeftChild() == null) { 
     if(tree.getRightChild() == null && this.getRightChild() == null) { 
      return true;}} 

    if(tree.getLeftChild() == null && this.getLeftChild() == null) { 
     if(tree.getRightChild() != null && this.getRightChild() != null) { 
      return this.getRightChild().hasSameStructureAs(tree.getRightChild());}} 

    if(tree.getLeftChild() != null && this.getLeftChild() != null) { 
     if(tree.getRightChild() != null && this.getRightChild() != null) { 
      return this.getRightChild().hasSameStructureAs(tree.getRightChild()) && this.getLeftChild().hasSameStructureAs(tree.getLeftChild());}} 

    if(tree.getLeftChild() != null && this.getLeftChild() != null) { 
     if(tree.getRightChild() == null && this.getRightChild() == null) { 
      return this.getLeftChild().hasSameStructureAs(tree.getLeftChild());}} 


    return false; 



}

来源

2014-03-31 17:53:59

检查二叉树是否具有相同的结构

回答

相关问题