题目：二叉树的结点定义如下：struct TreeNode{int m_nValue;TreeNode* m_pLeft;TreeNode* m_pRight;};输入两棵二叉树A和B，判断树B是不是A的子结构。例如，下图中的两棵树A和B，由于A中有一部分子树的结构和B是一样的，因此B就是A的子结构。1 8/ / / /8 7 9 2/ /9 2/ /4 7
//============================================================================ // Name : 100题之树为另一树的子结构.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> using namespace std; struct TreeNode { int value; TreeNode* left; TreeNode* right; TreeNode(int date):value(date),left(NULL),right(NULL){} }; void create_tree(TreeNode**root,int date) { TreeNode*p=new TreeNode(date); TreeNode *q=*root; TreeNode *s=NULL; if(!(*root)) { *root=p; } else { while(q) { s=q; if(q->value>date) q=q->left; else q=q->right; } if(s->value>date) { s->left=p; } else { s->right=p; } } } void print_tree( TreeNode*root) { if(root) { print_tree(root->left); cout<<root->value<<" "; print_tree(root->right); } } bool HasSubtree(const TreeNode* pTreeHead1, const TreeNode* pTreeHead2) { if((pTreeHead1 == NULL && pTreeHead2 != NULL) ||(pTreeHead1 != NULL && pTreeHead2 == NULL)) return false; if(pTreeHead1 == NULL && pTreeHead2 == NULL) return true; if(!pTreeHead2) return true; if(!pTreeHead1) return false; bool result=false; if(pTreeHead1->value==pTreeHead2->value) { result=HasSubtree(pTreeHead1->left, pTreeHead2->left); result&=HasSubtree(pTreeHead1->right, pTreeHead2->right); if(result) return result; } result=HasSubtree(pTreeHead1->left, pTreeHead2); if(result) return result; result=HasSubtree(pTreeHead1->right, pTreeHead2); if(result) return result; return false; } int main() { TreeNode*tree=NULL; create_tree(&tree,8); create_tree(&tree,6); create_tree(&tree,10); create_tree(&tree,5); create_tree(&tree,7); create_tree(&tree,9); create_tree(&tree,11); print_tree(tree); TreeNode*tree1=NULL; create_tree(&tree1,10); create_tree(&tree1,9); create_tree(&tree1,11); cout<<endl; print_tree(tree1); cout<<endl<<HasSubtree(tree,tree1)<<endl; return 0; }
