请查看附加的二叉树示例T1和T2。
![enter image description here](https://istack.dev59.com/UADW7.webp)
请注意,这个问题与子树问题不同。如果T2在T1中以结构完全相同的布局存在,并且T1可能包含额外的结构[无关紧要],则二叉树T2包含在二叉树T1中。
我已经用下面的代码解决了这个问题。它有点复杂,但请通过调试来理解。调用函数的方式在下面这行代码中。这里tree1是T1,tree2是T2,size2是T2树的大小。
return(containsInternal(tree1.getRoot(), tree2.getRoot(), size2));
bool checkContains(const BinaryTreeNode<int>* node1, const BinaryTreeNode<int>* node2, long& iterations)
{
if(iterations<0)
return(true);
if(!node1)
return(true);
bool returnStatus1=true, returnStatus2=false, returnStatus3=true;
if(node1->m_leftChild)
{
if(!node2->m_leftChild)
return(false);
else
returnStatus1=checkContains(node1->m_leftChild, node2->m_leftChild, iterations);
}
if(node1->m_data==node2->m_data)
{
returnStatus2=true;
--iterations;
}
if(node1->m_rightChild)
{
if(!node2->m_rightChild)
return(false);
else
returnStatus3=checkContains(node1->m_rightChild, node2->m_rightChild, iterations);
}
return(returnStatus1&&returnStatus2&&returnStatus3);
}
bool containsInternal(const BinaryTreeNode<int>* node1, const BinaryTreeNode<int>* node2, long size)
{
if(!node1||!node2)
return(false);
bool result1=containsInternal(node1->m_leftChild, node2, size);
bool result2=false;
if(node1->m_data==node2->m_data)
result2=checkContains(node2, node1, size);
bool result3=containsInternal(node1->m_rightChild, node2, size);
return(result1||result2||result3);
}
bool contains(BinaryTree<int>& tree1, BinaryTree<int>& tree2)
{
size_t size1=tree1.size();
size_t size2=tree2.size();
if(!size2)
return(true);
if(size2>size1)
return(false);
return(containsInternal(tree1.getRoot(), tree2.getRoot(), size2));
}