二叉树应用_树的子结构

心已赠人 2022-05-22 02:40 162阅读 0赞

题目： 输入两棵二叉树A和B，判断B是不是A的子结构（空树不是任一树的子结构）。

分析：要想查找树A中是否存在和树B一样的结构，我们可以分成两步：  
1、在树A中找到和树B的根节点一样的节点R  
2、在判断树A中以R为根节点的树中是不是包含和树B一样的结构。  
具体实现如下：

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    
    bool HasSubtree(TreeNode *proot1,TreeNode *proot2)
    {
        bool result=false;
        if(proot1!=NULL&&proot2!=NULL)
        {
            if(proot1->val==proot2->val)
                //判断树A中以R为根节点的树是不是包含和树B一样的结构。
                result=Doestree1hastree2(proot1,proot2);
            if(!result)
                result=HasSubtree(proot1->left,proot2);
            if(!result)
                result=HasSubtree(proot1->right,proot2);
        }
        return result;
    }
    
    bool Doestree1hastree2(TreeNode *proot1,TreeNode *proot2)
    {
        if(proot1==NULL)
            return false;
        if(proot2==NULL)
            return true;
    
        if(proot1->val==proot2->val)
            return  Doestree1hastree2(proot1->left,proot2->left)&& 
                Doestree1hastree2(proot1->right,proot2->right);
    }

在写遍历树的代码时，一定要注意，在每一处要访问地址的时候都要想一想这个地址有没有可能是NULL，如果是NULL该怎么处理。

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】-二叉树的应用(二叉排序树)

二叉排序树BST 1.头文件及类型定义 2.二叉排序树结点类型定义 3.函数声明 4.基本操作 4.1 查找操作

绝地灬酷狼/ 2023年03月03日 13:28/ 0 赞/ 23 阅读

相关数据结构二叉树的应用

1、二叉树相似性判断。试设计算法，判断两棵二叉树是否相似。所谓二叉树t1与t2相似，指的是t1和t2都是空的二叉树；或者t1的左子树与t2的左子树相似，同时t1的右子树与t

骑猪看日落/ 2022年08月21日 08:46/ 0 赞/ 186 阅读

相关 Java数据结构-树的应用-二叉查找树

二叉查找树也叫二叉排序树。对于树中的每个节点X，它的所有左子树中项的值小于X节点中的项，所有右子树中的项的值大于X的项。需要实现的基本操作有： 1.包含：

痛定思痛。/ 2022年08月03日 00:52/ 0 赞/ 185 阅读

相关二叉树应用_二叉树深度

题目：输入一颗二叉树的根节点，求该树的深度。分析：方法一：在[二叉树中和为某一值的路径][Link 1]中已经知道了如何存取树的一条路径，这里我们可以用此方法求出树的最长

妖狐艹你老母/ 2022年05月22日 03:41/ 0 赞/ 343 阅读

相关二叉树应用_打印二叉树

题目：从上往下打印二叉树的每个节点，同一层的节点按照从左往右的顺序打印。分析：每次打印一个节点的时候，如果该节点有子节点，就把该节点的子节点放到一个队列的末尾。每次打印队

谁践踏了优雅/ 2022年05月22日 02:46/ 0 赞/ 277 阅读

相关二叉树应用_树的子结构

题目：输入两棵二叉树A和B，判断B是不是A的子结构（空树不是任一树的子结构）。分析：要想查找树A中是否存在和树B一样的结构，我们可以分成两步： 1、在树A中找到和树B

心已赠人/ 2022年05月22日 02:40/ 0 赞/ 163 阅读

相关二叉树应用_重建二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8

喜欢ヅ旅行/ 2022年05月22日 02:37/ 0 赞/ 240 阅读

相关【数据结构】（二叉树）递归交换二叉树的左右子树

> \\算法思想:\\递归交换二叉树左右子树可以采取先序，中序，后序，遍历的思想，划分子问题对其求解 -------------------- 代码： void

逃离我推掉我的手/ 2021年11月14日 15:06/ 0 赞/ 289 阅读

相关【数据结构】（二叉树）二叉树删除结点值为x的子树

删除结点值为x的子树（包含结点本身）方法一递归: > 算法思想：递归的思想就是在前序遍历的过程中查找值为x的元素找到后将其释放 void Release(

川长思鸟来/ 2021年11月13日 14:46/ 0 赞/ 400 阅读

相关二叉树的子结构

树的子结构题目：输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。二叉树的定义如下

╰+哭是因爲堅強的太久メ/ 2021年10月30日 00:28/ 0 赞/ 257 阅读