数据结构与算法中二叉树子结构的详解
更新时间:2020年4月25日 17:32 点击:1742
数据结构与算法中二叉树子结构的详解
需求
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
树的描述:
class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }
解决思路
使用了栈将元素入栈,并不断的弹出元素,弹出一个元素的时候,拼接成字符串,并用特殊符号进行区分,该方法主要是按照先序遍历的方式将树节点的数据信息拼接为字符串,这样,两个树的节点拼接而成的串进行判断是不是包含。
不过,有的资料上说可以通过递归的方式进行,但是我感觉以及实践以后发现是错误的。后面会给出代码,读者自行尝试。
public static boolean HasSubtree2(TreeNode root1, TreeNode root2) { if (root2 == null) return false; String str = ""; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(null); stack.push(root1); TreeNode node = null; while ((node = stack.pop()) != null) { str += '_' + node.val + '_'; if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } String str2 = ""; node = null; stack.push(null); stack.push(root2); while ((node = stack.pop()) != null) { str2 += '_' + node.val + '_'; if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } if (str.contains(str2)) { return true; } else { return false; } }
树的构建
二叉树而言,可以通过数组的方式进行存放,首节点放在数组0号位置处,其左节点在1号位置处,其右节点在2号位置处。由此该index的映射关系为:
index_parent.left => 2* index_parent + 1;
index_parent.right=> 2* index_parent + 2;
构建思路,左节点和右节点分别构建,根节点的左节点就一直追溯其子节点,根节点的右节点一直追溯其子节点,由此,形成的是递归的结构。
代码如下:
注:这里数组中通过-1作为区分,读者可自行扩充。
public static TreeNode getTree(int[] node, int index) { if (index >= node.length) return null; TreeNode n = null; if (node[index] != -1) { n = new TreeNode(node[index]); n.left = getTree(node, index * 2 + 1); n.right = getTree(node, index * 2 + 2); } return n; }
完整代码
包括了资料中提供的代码,但是经过测试如下用例中是错误的,但是理论上说tree2应该是tree1的子结构才对。
import java.util.Stack; public class HasSubtree { public static void main(String[] args) { TreeNode tree = getTree(new int[] { 8, 8, 7, 9, 2, -1, -1, -1, -1, 4, 7 }, 0); TreeNode tree2 = getTree(new int[] { 2, 4, 7 }, 0); boolean bool = HasSubtree(tree, tree2); System.out.println(bool); boolean bool2 = HasSubtree2(tree, tree2); System.out.println(bool2); } public static boolean HasSubtree2(TreeNode root1, TreeNode root2) { if (root2 == null) return false; String str = ""; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(null); stack.push(root1); TreeNode node = null; while ((node = stack.pop()) != null) { str += '_' + node.val + '_'; if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } String str2 = ""; node = null; stack.push(null); stack.push(root2); while ((node = stack.pop()) != null) { str2 += '_' + node.val + '_'; if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } if (str.contains(str2)) { return true; } else { return false; } } public static TreeNode getTree(int[] node, int index) { if (index >= node.length) return null; TreeNode n = null; if (node[index] != -1) { n = new TreeNode(node[index]); n.left = getTree(node, index * 2 + 1); n.right = getTree(node, index * 2 + 2); } return n; } public static boolean HasSubtree(TreeNode root1, TreeNode root2) { boolean result = false; if (root1 != null && root2 != null) { if (root1.val == root2.val) { result = isSubTree(root1, root2); } if (!result) { result = isSubTree(root1.left, root2); } if (!result) { result = isSubTree(root1.right, root2); } } return result; } private static boolean isSubTree(TreeNode root1, TreeNode root2) { if (root1 == null) return false; if (root2 == null) return true; if (root1.val != root2.val) return false; return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right); } } class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
上一篇: C++ 字符串去重排序实例代码
下一篇: 浅谈c++中的while(cin)问题
相关文章
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了在C#中使用二叉树实时计算海量用户积分排名的实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 本文主要和大家分享几种Redis数据结构详解,希望文中的案例和代码,能帮助到大家。...2021-01-15
- 这篇文章主要为大家详细的介绍了Redis高效的原因以及分析了Redis高效的数据结构,有需要的朋友可以借鉴参考下,希望能够有所帮助...2021-09-27
- 上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构——线性结构...2020-06-25
- 这篇文章主要介绍了C语言数据结构递归之斐波那契数列的相关资料,希望通过本文能帮助到大家,让大家理解掌握这部分内容,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++数据结构与算法之哈夫曼树的实现方法,简单说明了哈夫曼树的原理,并结合具体实例形式分析了C++实现哈夫曼树的相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了基于JavaScript的数据结构队列动画实现示例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-06
- 这篇文章主要介绍了数据结构 双向链表的创建和读取详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之动态分配实现串的相关资料,希望通过本文能帮助到大家,让大家实现数据结构中动态分配实现串的实例,需要的朋友可以参考下...2020-04-25
- <? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){...2016-11-25
- 我们在进行编程时,往往会开发诸多的算法,那么我们怎么在那么多算法中找到最好的那个呢?本文主要介绍时间和空间复杂度概念及时间复杂度的求解,预祝读者学习愉快...2021-10-23
- 这篇文章主要介绍了举例讲解C语言程序中对二叉树数据结构的各种遍历方式,先序中序后序二叉树遍历几乎成了最老生常谈的数据结构基础知识,的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构树的双亲表示法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了一波二叉树遍历问题的C++解答实例分享,包括节点打印和转换为镜像等问题的解答,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统计相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中数据结构之链式基数排序的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之使用链表模拟栈的实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之二叉树的非递归后序遍历算法的相关资料,希望通过本文能帮助到大家,让大家实现这样的功能,需要的朋友可以参考下...2020-04-25