树型结构数据怎么查找_查找两棵树在结构上是否相同| 数据结构

Dear 丶 2023-03-05 05:24 30阅读 0赞

树型结构数据怎么查找

**Solution:**

**解：**

Since we need to check only structural similarity we needn’t check their respective node values, rather we need to check whether both have the same structural organization or not. So the simple algorithm to solve it can be:

因为我们只需要检查结构相似性，所以我们不需要检查它们各自的节点值，而是需要检查两者是否具有相同的结构组织。 因此，解决它的简单算法可以是：

1.  If both trees are NULL, then they are structurally similar.
    
    如果两个树都为NULL，则它们在结构上相似。
2.  If one of the two is NULL and other is not NULL, then they are not structurally similar.
    
    如果两者之一是NULL，而另一个不是NULL，则它们在结构上不相似。
3.  If both of the trees are not NULL we recursively check right and left subtree.
    
    如果两个树都不为NULL，则我们递归检查左右子树。

**Example:**

**例：**

![structurally identical trees][]

**Fig:** Two tree which are structurally identical but are not similar  
**Image source:** wikipedia

**图：**两棵结构相同但不相似的树  
**图片来源：** Wikipedia

**Functional problem:**

**功能问题：**

We need to write a Boolean function where we are given two roots for two trees.

我们需要编写一个布尔函数，其中给我们两棵树的两个根。

bool IsSimilar(Tree* root1, Tree* root2);

**Pseudocode:**

**伪代码：**

bool IsSimilar( Tree* root1, Tree* root2){
        
    	// both tree empty
    	if(root1==NULL && root2==NULL)  
    		return true;
    	// one tree empty, another is not
    	if(root1==NULL || root2==NULL) 
    		return false;
    
    	// above two are base conditions
    	
    	//if both tree is not empty
    	// recursively check for left and right subtrees
    	return (IsSimilar(root1->left,root2->left) && IsSimilar(root1->right,root2->right)); 
    }

**C++ implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    // tree node is defined
    class tree{
            
    	public:
    		int data;
    		tree *left;
    		tree *right;
    };
    
    bool IsSimilar( tree *root1, tree* root2){
        
    	// both tree empty
    	if(root1==NULL && root2==NULL)  
    		return true;
    	// one tree empty, another is not
    	if(root1==NULL || root2==NULL) 
    		return false;
    
    	// above two are base conditions
    
    	//if both tree is not empty
    	// recursively check for left and right subtrees
    	return (IsSimilar(root1->left,root2->left) && IsSimilar(root1->right,root2->right)); 
    }
    
    // creating new node
    tree* newnode(int data)  
    {
         
    	tree* node = (tree*)malloc(sizeof(tree)); 
    	node->data = data; 
    	node->left = NULL; 
    	node->right = NULL; 
    
    	return(node); 
    } 
    
    
    int main() 
    {
         
    	//**same trees are built as shown in example**
    
    	// building first tree
    	tree *root1=newnode(2); 
    	root1->left= newnode(7); 
    	root1->right= newnode(5); 
    	root1->right->right=newnode(9);
    	root1->right->right->left=newnode(4);
    	root1->left->left=newnode(2); 
    	root1->left->right=newnode(6);
    	root1->left->right->left=newnode(5);
    	root1->left->right->right=newnode(11);
    	cout<<"first tree is built,same as image1"<<endl;
    	
    	// building second tree
    	tree *root2=newnode(8); 
    	root2->left= newnode(3); 
    	root2->right= newnode(10); 
    	root2->right->right=newnode(14);
    	root2->right->right->left=newnode(13);
    	root2->left->left=newnode(1); 
    	root2->left->right=newnode(6);
    	root2->left->right->left=newnode(4);
    	root2->left->right->right=newnode(7);
    	
    	cout<<"second tree is built,same as image2"<<endl;
    	if(IsSimilar(root1,root2))
    		cout<<"Both are structurally similar"<<endl;
    	else
    		cout<<"Both aren't structurally similar"<<endl;
    
    	return 0; 
    }

**Output**

**输出量**

first tree is built,same as image1
    second tree is built,same as image2
    Both are structurally similar

**Let’s consider another thing:**

**让我们考虑另一件事：**

If the question was whether two trees are identical or not then we had to check the node data’s also. A little bit modification like below would have been enough.

如果问题是两棵树是否相同，那么我们还必须检查节点数据。 像下面这样的一些修改就足够了。

**Modified pseudocode:**

**修改后的伪代码：**

bool IsSimilar( Tree* root1, Tree* root2){
        
    	// both tree empty
    	if(root1==NULL && root2==NULL)  
    		return true;
    	// one tree empty, another is not
    	if(root1==NULL || root2==NULL) 
    		return false;
    
    	// above two are base conditions
    
    	//if both tree is not empty
    	// recursively check for left and right subtrees
    	return ( (root1->data==root2->data) && IsSimilar(root1->left,root2->left) && IsSimilar(root1->right,root2->right)); 
    	// check the modification for comapring node' data also
    }

> 翻译自: [https://www.includehelp.com/data-structure-tutorial/find-whether-two-trees-are-structurally-identical-or-not.aspx][https_www.includehelp.com_data-structure-tutorial_find-whether-two-trees-are-structurally-identical-or-not.aspx]

树型结构数据怎么查找

[structurally identical trees]: /images/20230208/835ba482ad664d3d9602539622881695.png
[https_www.includehelp.com_data-structure-tutorial_find-whether-two-trees-are-structurally-identical-or-not.aspx]: https://www.includehelp.com/data-structure-tutorial/find-whether-two-trees-are-structurally-identical-or-not.aspx