题目:二叉树的结点定义如下:
struct TreeNode
{
int m_nValue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入两棵二叉树A和B,判断树B是不是A的子结构。
例如,下图中的两棵树A和B,由于A中有一部分子树的结构和B是一样的,因此B就是A的子结构。
1 8
/ \/ \
87 9 2
/ \
9 2
/ \
47
分析:这是2010年微软校园招聘时的一道题目。二叉树一直是微软面试题中经常出现的数据结构。对微软有兴趣的读者一定要重点关注二叉树。
回到这个题目的本身。要查找树A中是否存在和树B结构一样的子树,我们可以分为两步:第一步在树A中找到和B的根结点的值一样的结点N,第二步再判断树A中以N为根结点的子树是不是包括和树B一样的结构。
第一步在树A中查找与根结点的值一样的结点。这实际上就是树的遍历。对二叉树这种数据结构熟悉的读者自然知道我们可以用递归的方法去遍历,也可以用循环的方法去遍历。由于递归的代码实现比较简洁,面试时如果没有特别要求,我们通常都会采用递归的方式。下面是参考代码:
bool HasSubtree(TreeNode* pTreeHead1, TreeNode* pTreeHead2)
{
if((pTreeHead1 == NULL && pTreeHead2 != NULL) ||
(pTreeHead1 != NULL && pTreeHead2 == NULL))
return false;
if(pTreeHead1 == NULL && pTreeHead2 == NULL)
return true;
return HasSubtreeCore(pTreeHead1, pTreeHead2);
}
bool HasSubtreeCore(TreeNode* pTreeHead1, TreeNode* pTreeHead2)
{
bool result = false;
if(pTreeHead1->m_nValue == pTreeHead2->m_nValue)
{
result = DoesTree1HaveAllNodesOfTree2(pTreeHead1, pTreeHead2);
}
if(!result && pTreeHead1->m_pLeft != NULL)
result = HasSubtreeCore(pTreeHead1->m_pLeft, pTreeHead2);
if(!result && pTreeHead1->m_pRight != NULL)
result = HasSubtreeCore(pTreeHead1->m_pRight, pTreeHead2);
return result;
}
在上述代码中,我们递归调用hasSubtreeCore遍历二叉树A。如果发现某一结点的值和树B的头结点的值相同,则调用DoesTree1HaveAllNodeOfTree2,做第二步判断。
在面试的时候,我们一定要注意边界条件的检查,即检查空指针。当树A或树B为空的时候,定义相应的输出。如果没有检查并做相应的处理,程序非常容易崩溃,这是面试时非常忌讳的事情。由于没有必要在每一次递归中做边界检查(每一次递归都做检查,增加了不必要的时间开销),上述代码只在HasSubtree中作了边界检查后,在HasSubtreeCore中作递归遍历。
接下来考虑第二步,判断以树A中以N为根结点的子树是不是和树B具有相同的结构。同样,我们也可以用递归的思路来考虑:如果结点N的值和树B的根结点不相同,则以N为根结点的子树和树B肯定不具有相同的结点;如果他们的值相同,则递归地判断他们的各自的左右结点的值是不是相同。递归的终止条件是我们到达了树A或者树B的叶结点。参考代码如下:
bool DoesTree1HaveAllNodesOfTree2(TreeNode* pTreeHead1, TreeNode* pTreeHead2)
{
if(pTreeHead2 == NULL)
return true;
if(pTreeHead1 == NULL)
return false;
if(pTreeHead1->m_nValue != pTreeHead2->m_nValue)
return false;
return DoesTree1HaveAllNodesOfTree2(pTreeHead1->m_pLeft, pTreeHead2->m_pLeft) &&
DoesTree1HaveAllNodesOfTree2(pTreeHead1->m_pRight, pTreeHead2->m_pRight);
}
分享到:
相关推荐
树结构,点击父结构,获取子结构数据。 通过lv.setSingle(false);设置是单选还是多选 List<TreeElement> treeElements = parser.getTreeElements_system(listSystemInfo, 1, true);// 解析读出的文件资源内容 最后...
树形结构之文件结构 简单代码,如何打开文件时在界面以树形方式显示子目录和文件
1. 定义并实现二叉树的数据结构(注:其中创建二叉树要求使用广义表或前序遍历方法创建、还要求一个是前序+中序的方法创建)。测试二叉树使用如下的树: A B C D E F 2. 实现哈夫曼树数据结构,使用...
springJpa单标递归树形结构
Vue实现树形结构,不采用tree组件,利用循环方式得到;实现全选,勾选父节点自动勾选子节点,勾选子节点反勾选相应父节点功能
用递归算法,返回以p结点为根的子树高度,后根次序遍历,返回左子树的高度,返回右子树的高度,高度较高子树的高度加1。 输出以p结点为根的一棵子树的广义表表示字符串,先根次序遍历,递归算法。如果为空,则输出...
4)分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 5) 格式就要按照我们作业的要求,对数据测试,分析,总结...
js树形结构。可以添加节点、删除选中节点
本文实例为大家分享了Element-ui表格实现树形结构表格的具体代码,供大家参考,具体内容如下 前端效果展示: 在el-table中,支持树类型的数据的显示。当 row 中包含 children 字段时,被视为树形数据。渲染树形...
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作: (1)访问结点本身(N), (2)遍历该结点的左子树(L), (3)遍历该...
该方法通过递归调用实现对树结构的动态添加节点和子节点,在项目中非常实用!!
此java类实现了对数据表的分类递归树的实现,为本人倾力之作,后期,会发布js版,敬请期待!
树的子结构.md
假设树的根为 root ,其子树森林 F = ( T1 , T2 , … , Tn ),设与该树对应的广义表为 L ,则 L =(原子,子表 1 ,子表 2 , … ,子表 n ),其中原子对应 root ,子表 i ( 1)对应 Ti 。广义表 (a,(b,(c)...
对一棵树的结点进行编码的步骤如下: 首先,对根节点编码,调用TreeCodeSet.root()可以获得根结点编码。 然后,按自上而下,自左而右的顺序遍历树,调用TreeCodeSet.child(code, i)依次对所有结点的子节点编号(可以...
树形结构以其操作便利、美观获得大家的认可与喜爱。此例可提供一个方案及构架,包括动态新增、删除子节点,是一个很不错的例子。
触发用户自定义的单击事件,将该 <li> 标签中的第一个超链接做为参数传递过去 * 2.修改当前菜单项所属的子菜单的显示状态(如果等于 true 将其设置为 false,否则将其设置为 true) * 3.重新初始化菜单 */ ...
主要是Ext JS 深入浅出 树形结构博客源代码实现,树形结构的节点实现,展开子叶设置等功能
本文实例讲述了js 递归json树实现根据子id查父id的方法。分享给大家供大家参考,具体如下: 最近做了一个类似用js实现思维导图的功能,作为思维导图,一定会有树状结构的数据产生,在操作里面的节点时会经常需要查找...
数据结构课程设计源码 图子系统 详细注释+图形界面操作 简单易操作