判断一个节点是否在一棵二叉树中和判断一颗二叉树是否是另一颗树的子树——题集（十二）

判断一个节点是否在一棵二叉树中和判断一颗二叉树是否是另一颗树的子树——题集（十二）

       今天分享一下，判断一个节点是否在一棵二叉树中和判断一颗二叉树是否是另一颗树的子树。

      判断一个节点是否在一棵二叉树中的源代码和运行示例。

     说明：节点为空，默认结点在二叉树中；二叉树为空，默认结点不在二叉树中。本程序默认对比结点的值，所以该二叉树中最好没有有重复值的结点。

源代码如下：

#include<iostream>
using namespace std;
 
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x)
:val(x)
,left(NULL)
,right(NULL)
{
    }
};
 
//判断一个节点是否在一棵二叉树中
bool _IsPointExit(TreeNode*  root,const TreeNode* point){//前序遍历求解一遍
if(root==NULL) return false;
 
if(root->val ==point->val ) return true;
 
if(!_IsPointExit( root->left, point)){
return _IsPointExit( root->right, point);
}
return true;
}
bool IsPointExit(TreeNode*  root,const TreeNode*  point){//判断一个节点是否在一棵二叉树中
if(point==NULL) return true;
TreeNode*  proot=root;
 
return _IsPointExit( proot, point);
}
 
void Print(TreeNode* pRoot) {//层序遍历打印
queue<TreeNode*> cur;
    if(pRoot==NULL) return ;
    cur.push(pRoot);
 
    while(!cur.empty()){
        TreeNode* point=cur.front();
        cur.pop();
        cout<<point->val<<" ";
 
        if(point->left != NULL)
        cur.push(point->left);
        
if(point->right != NULL)
            cur.push(point->right);
    }
cout<<endl;
 
    return;
}
 
void TestTree(){//判断一个节点是否在一棵二叉树中
TreeNode * pRoot1=new TreeNode(1);
TreeNode * pRoot2=new TreeNode(2);
TreeNode * pRoot3=new TreeNode(3);
TreeNode * pRoot4=new TreeNode(4);
TreeNode * pRoot5=new TreeNode(5);
TreeNode * pRoot6=new TreeNode(6);
TreeNode * pRoot7=new TreeNode(7);
TreeNode * pRoot8=new TreeNode(8);
TreeNode * pRoot9=new TreeNode(9);
 
pRoot1->left = pRoot2;
pRoot1->right = pRoot3;
pRoot2->left = pRoot4;
pRoot2->right = pRoot5;
pRoot3->left = pRoot6;
pRoot3->right = pRoot7;
pRoot4->left = pRoot8;
pRoot4->right = pRoot9;
 
TreeNode * root0=new TreeNode(11);
 
cout<<"判断一个节点是否在一棵二叉树中"<<endl;
cout<<"********************************"<<endl<<endl;
cout<<"打印二叉树pRoot1：";
Print(pRoot1);
cout<<"pRoot1节点的值为: "<<pRoot1->val<<"，IsPointExit(pRoot1,pRoot1): "<<IsPointExit(pRoot1,pRoot1)<<endl;
cout<<"pRoot2节点的值为: "<<pRoot2->val<<"，IsPointExit(pRoot1,pRoot2): "<<IsPointExit(pRoot1,pRoot2)<<endl;
cout<<"pRoot3节点的值为: "<<pRoot3->val<<"，IsPointExit(pRoot1,pRoot3): "<<IsPointExit(pRoot1,pRoot3)<<endl;
cout<<"pRoot4节点的值为: "<<pRoot4->val<<"，IsPointExit(pRoot1,pRoot4): "<<IsPointExit(pRoot1,pRoot4)<<endl;
cout<<"pRoot5节点的值为: "<<pRoot5->val<<"，IsPointExit(pRoot1,pRoot5): "<<IsPointExit(pRoot1,pRoot5)<<endl;
cout<<"pRoot6节点的值为: "<<pRoot6->val<<"，IsPointExit(pRoot1,pRoot6): "<<IsPointExit(pRoot1,pRoot6)<<endl;
cout<<"pRoot7节点的值为: "<<pRoot7->val<<"，IsPointExit(pRoot1,pRoot7): "<<IsPointExit(pRoot1,pRoot7)<<endl;
cout<<"pRoot8节点的值为: "<<pRoot8->val<<"，IsPointExit(pRoot1,pRoot8): "<<IsPointExit(pRoot1,pRoot8)<<endl;
cout<<"pRoot9节点的值为: "<<pRoot9->val<<"，IsPointExit(pRoot1,pRoot9): "<<IsPointExit(pRoot1,pRoot9)<<endl;
cout<<"root0节点的值为: "<<root0->val<<"，IsPointExit(pRoot1,root0): "<<IsPointExit(pRoot1,root0)<<endl;
 
cout<<"********************************"<<endl<<endl;
}
 
int main(){
TestTree();//判断一个节点是否在一棵二叉树中
system("pause");
return 0;
}

运行结果：

  

     判断一颗二叉树是否是另一颗树的子树的源代码和运行示例。

     如图：tree2是tree1的子树。

源代码如下：

#include<iostream>
using namespace std;
 
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x)
:val(x)
,left(NULL)
,right(NULL)
{
    }
};
 
bool _IsChildTree(TreeNode* T1,TreeNode* T2){//前序遍历求解一遍
if(T2==NULL && T1==NULL) return true;
if(T1==NULL || T2==NULL) return false;
 
if(T1->val == T2->val){
if(_IsChildTree(T1->left, T2->left)){//左树相同继续求解右树
return _IsChildTree(T1->right, T2->right);
}
}
return false;
}
 
bool _Find(TreeNode* T1,TreeNode* T2){
if(T1==NULL) return false;
 
if(T1->val == T2->val){
if(_IsChildTree(T1, T2)){
return true;
}
}
if(!_Find(T1->left, T2)){
return _Find(T1->right, T2);
}
return true;
}
 
//一颗二叉树是否是另一颗树的子树
bool IsChildTree(TreeNode*  T1, TreeNode*  T2){//一颗二叉树是否是另一颗树的子树
//找到重合的第一个点，入口——中序遍历一遍
if(T2==NULL) return true;
if(T1==NULL) return false;
 
TreeNode* t1= T1;
TreeNode* t2= T2;
 
return _Find(t1,t2);
}
 
void _PrePrint(TreeNode* root)//先序打印
{
if(root==NULL) return;
 
cout<<root->val<<" ";
_PrePrint(root->left);
_PrePrint(root->right);
}
 
void TestTree(){//一颗二叉树是否是另一颗树的子树
TreeNode * pRoot1=new TreeNode(1);
TreeNode * pRoot2=new TreeNode(2);
TreeNode * pRoot3=new TreeNode(3);
TreeNode * pRoot4=new TreeNode(4);
TreeNode * pRoot5=new TreeNode(5);
TreeNode * pRoot6=new TreeNode(6);
TreeNode * pRoot7=new TreeNode(7);
TreeNode * pRoot8=new TreeNode(8);
TreeNode * pRoot9=new TreeNode(9);
 
pRoot1->left = pRoot2;
pRoot1->right = pRoot3;
pRoot2->left = pRoot4;
pRoot2->right = pRoot5;
pRoot3->left = pRoot6;
pRoot3->right = pRoot7;
pRoot4->left = pRoot8;
pRoot4->right = pRoot9;
 
TreeNode * root0=new TreeNode(11);
TreeNode * root1=new TreeNode(3);
TreeNode * root2=new TreeNode(4);
TreeNode * root4=new TreeNode(6);
TreeNode * root5=new TreeNode(7);
TreeNode * root6=new TreeNode(8);
 
root0->left = root1;
root0->right = root2;
root1->left = root4;
root1->right = root5;
root2->left = root6;
 
cout<<"一颗二叉树是否是另一颗树的子树"<<endl;
cout<<"********************************"<<endl<<endl;
 
cout<<"先序打印二叉树pRoot1：";
_PrePrint(pRoot1);
cout<<endl;
cout<<"IsChildTree(pRoot1, pRoot1): "<<IsChildTree(pRoot1, pRoot1)<<endl;//一颗二叉树是否是另一颗树的子树
cout<<"IsChildTree(pRoot1, pRoot2): "<<IsChildTree(pRoot1, pRoot2)<<endl;
cout<<"IsChildTree(pRoot1, pRoot3): "<<IsChildTree(pRoot1, pRoot3)<<endl;
cout<<"IsChildTree(pRoot1, pRoot4): "<<IsChildTree(pRoot1, pRoot4)<<endl;
cout<<"IsChildTree(pRoot1, pRoot5): "<<IsChildTree(pRoot1, pRoot5)<<endl;
cout<<"IsChildTree(pRoot1, pRoot6): "<<IsChildTree(pRoot1, pRoot6)<<endl;
cout<<"IsChildTree(pRoot1, pRoot7): "<<IsChildTree(pRoot1, pRoot7)<<endl;
cout<<"IsChildTree(pRoot1, pRoot8): "<<IsChildTree(pRoot1, pRoot8)<<endl;
cout<<"IsChildTree(pRoot1, pRoot9): "<<IsChildTree(pRoot1, pRoot9)<<endl;
cout<<"********************************"<<endl<<endl;
 
 
cout<<"先序打印二叉树pRoot1：";
_PrePrint(pRoot1);//先序打印
cout<<endl;
cout<<"先序打印二叉树root0：";
_PrePrint(root0);
cout<<endl;
cout<<"IsChildTree(pRoot1, root0): "<<IsChildTree(pRoot1, root0)<<endl;
cout<<endl<<endl;
 
cout<<"先序打印二叉树pRoot1：";
_PrePrint(pRoot1);
cout<<endl;
cout<<"先序打印二叉树root1：";
_PrePrint(root1);
cout<<endl;
cout<<"IsChildTree(pRoot1, root1): "<<IsChildTree(pRoot1, root1)<<endl;
cout<<endl<<endl;
 
cout<<"先序打印二叉树pRoot1：";
_PrePrint(pRoot1);
cout<<endl;
cout<<"先序打印二叉树root2：";
_PrePrint(root2);
cout<<endl;
cout<<"IsChildTree(pRoot1, root2): "<<IsChildTree(pRoot1, root2)<<endl;
cout<<endl<<endl;
 
cout<<"********************************"<<endl<<endl;
}
 
int main(){
TestTree();//一颗二叉树是否是另一颗树的子树
system("pause");
return 0;
}

运行结果：

 

      分享如上，如有错误，望斧正！愿大家学得开心，共同进步！