【面试题】剑指offer18

题目： 输入两颗二叉树A和B，判断B是不是A的子结构。

#include<iostream> using namespace std; struct BinTreeNode { int _value; BinTreeNode* _pLeft; BinTreeNode* _pRight; BinTreeNode(int x) :_value(x) ,_pLeft(NULL) ,_pRight(NULL) {} }; class BinTree { public: BinTree() :_root(NULL) {} ~BinTree() { delete _root; _root=NULL; } BinTree(int * a,size_t size,const int& invalid) { int index=0; CreatTree(_root,a,size,index,invalid); } void CreatTree(BinTreeNode*& root,int a[],int size,int& index,const int invalid) { if(index<size&&a[index]!=invalid) { root=new BinTreeNode(a[index]); CreatTree(root->_pLeft,a,size,++index,invalid); CreatTree(root->_pRight,a,size,++index,invalid); } } void Proder() { _Proder(_root); cout<<endl; } void _Proder(BinTreeNode* root) { if(root==NULL) return; cout<<root->_value<<" "; _Proder(root->_pLeft); _Proder(root->_pRight); } BinTreeNode* getroot() { return _root; } private: BinTreeNode* _root; }; bool DoesTree1HaveTree2(BinTreeNode* root1,BinTreeNode* root2) { if (root2==NULL) return true; if(root1==NULL) return false; if(root1->_value!=root2->_value) return false; return DoesTree1HaveTree2(root1->_pLeft,root2->_pLeft)&&DoesTree1HaveTree2(root1->_pRight,root2->_pRight); } bool HasSubTree(BinTreeNode* root1,BinTreeNode* root2)//找与树2根节点相同的节点 { bool result=false; if(root1!=NULL&&root2!=NULL) { if(root1->_value==root2->_value) result=DoesTree1HaveTree2(root1,root2);//找到与树2根节点相同的节点后，进行下一步判断 if(!result) result=HasSubTree(root1->_pLeft,root2); if(!result) result=HasSubTree(root1->_pRight,root2); } return result; } void test() { int arr[10]={1,2,3,'#','#',4,'#','#',5,6}; BinTree t1(arr,10,'#'); t1.Proder(); } void test2() { int arr[13]={8,8,9,'#','#',2,4,'#','#',7,'#','#',7}; BinTree t1(arr,13,'#'); t1.Proder(); int arr2[5]={8,9,'#','#',2}; BinTree t2(arr2,5,'#'); t2.Proder(); cout<<HasSubTree(t1.getroot(),t2.getroot())<<endl; } #include "BinTree.h" #include<cstdlib> int main() { test(); test2(); system("pause"); return 0; }

这里的二叉树全是按照前序建立的，如下图 “#”表示子树为空