一.树型数据库结构 及 树的一些基础知识 首先我们来看一个简单的应用树-.数据库设计如下图: 表名: testTree 字段:id (主键 自动递增1) username (这个任意了.只是一个数据字段) parentid (父节点的ID值) id username parentid1 A 02 B 13 C 24 D 15 E 26 F 5 如果按树来排列这些数据 应该产生如下状态:A|____B| |____C| |____E| |____F||____D 如果按
T1是一棵含有几百万个节点的树,T2含有几百个节点.判断T2是否是T1 的子树. 首先考虑小数据量的情况,可以根据树的前序和中序遍历所得的字符串,来通过判断T2生成的字符串是否是T1字符串的子串,来判断T2是否是T1的子树.假设T1的节点数为N,T2的节点数为M.遍历两棵树算法时间复杂性是O(N + M), 判断字符串是否为另一个字符串的子串的复杂性也是O( N + M)(比如使用KMP算法).所需要的空间也是O(N + M). 这里有一个问题需要注意:对于左节点或者右节点为null的情况,需要