今天的面试题分享，等会放答案。。。

Question

设计一张表来表示一个二叉树中的节点。通过表中的一条数据就能确定这个节点在二叉树中的位置。
设计一个公司的员工数据库，其中公司只有这一个，部门有好多，每个部门中有好多员工。其中员工可以新来和辞职。部门可以设立也可以新增，部门还可以设立子部门，员工可以属于父部门也可以属于子部门。

Answer 1

第一题实际上就是节点的编码问题，看树的深度，int/bigint/binary类型可选。

Answer 2

create table 部门表(id int,name nvarchar(20),pid int)
create table 员工表(id int,name nvarchar(20),deptid int)

Answer 3

第一题，类似于导航栏的的功能实现create Table T1(ID int ,value varchar(50),ParentID)第二题 ，好像没有什么悬念吧

Answer 4

第二问用序列化比较好吧。xml的。
【员工可以属于父部门也可以属于子部门】——和模糊的条件。是只可以一个部门吗？还是可以多部门？

Answer 5

CREATE TABLE tb_test(ID INT PRIMARY KEY IDENTITY(1,1),content NVARCHAR(500),location nvarchar(500))content 字段用于存放二叉树节点的内容
location用于存放节点在二叉树中的位置，该字段的内容是一串由0和1组成的字符串，字符串是从根节点下的第一个子节点开始记录的。0表示在树的左边，1表示在树的右边,字符串的长度表示该节点在树中的深度。如location的值为011010则可以确定该节点的位置如下

Answer 6

location就是我所说的节点编码，不过他用的nvarchar(500)，我给出三种类型int/bigint/binary，一般来说bigint足够了，62层的深度，最顶级的电脑，处理这么一颗庞大的二叉树，都是一件很费力的事情。

Answer 7

select 500/8.0 -- 62.5恰恰是bigint可达的深度，nvarchar(500)对人眼直观，但对电脑不直观，当场我不会BS考官，面试完转身我也许会BS一下。

Answer 8

select 500/8.0 -- 62.5这个搞错，是binary(63)

Answer 9

上面是第一题答案，
这是第二题答案：
至于这个问题前期需求很重要，要收集该公司的信息，看这个公司的规模，如果该公司的部门总数（包括所有部门，父部门和子部门的总数）能确定在一个数量级才能设计表，这里假设需求是总部门数不会超过两位数（也就是100个部门以内），这很重要否则就会出错。
CREATE TABLE 部门表(ID INT PRIMARY KEY IDENTITY(1,1),NAME NVARCHAR(20),location NVARCHAR(50),PID INT)
CREATE TABLE 员工表(ID INT PRIMARY KEY IDENTITY(1,1),NAME NVARCHAR(20),DEPTID INT)
部门表：ID 主键，自增长； NAME 部门名称；PID 员工表外键; location 部门的位置
location 的格式为 011223 
举例说明：如ID 为50的记录的location值为011223则可以确定该部门在公司的位置。如果该公司的部门总数超过了100个那就会出错。因为在程序中获得location的内容后肯定是拆分，每两位表示一个部门，而有一个部门的位置是三位数，那这就会出错

Answer 10

呵呵，是我用的NVARCHAR，我忘记当时面试官说用什么类型了。

Answer 11

留名，明天看结果，对sql server 了解太浅了

Answer 12

第二道题的答案没有看明白，D 为50的记录的location值为011223则可以确定该部门在公司的位置 这个是怎么做到的

Answer 13

我已经忘了 是那个大神写的了
--测试数据
CREATE TABLE #Employees(
    EmployeeCode varchar(20) NOT NULL PRIMARY KEY CLUSTERED,
    ReportToCode varchar(20) NULL)
GO
INSERT INTO #Employees VALUES('A',NULL)
INSERT INTO #Employees VALUES('B','A')
INSERT INTO #Employees VALUES('C','A')
INSERT INTO #Employees VALUES('D','A')
INSERT INTO #Employees VALUES('E','B')
INSERT INTO #Employees VALUES('F','B')
INSERT INTO #Employees VALUES('G','C')
INSERT INTO #Employees VALUES('H','D')
INSERT INTO #Employees VALUES('I','D')
INSERT INTO #Employees VALUES('J','D')
INSERT INTO #Employees VALUES('K','J')
INSERT INTO #Employees VALUES('L','J')
INSERT INTO #Employees VALUES('M','J')
INSERT INTO #Employees VALUES('N','K')
GO
/*
可能遇到的查询问题：
1. 员工'D'的所有直接下属
2. 员工'D'的所有2级以内的下属（包括直接下属和直接下属的下属）
3. 员工'N'的所有上级（按报告线顺序列出）
4. 员工@EmployeeCode的所有@LevelDown级以内的下属（@EmployeeCode和@LevelDown以变量传入）
DECLARE @EmployeeCode varchar(20), @LevelDown int;
SET @EmployeeCode = 'D';
SET @LevelDown = 2;
5. 员工@EmployeeCode的所有@LevelUp级以内的上级（@EmployeeCode和@LevelUp以变量传入）
DECLARE @EmployeeCode varchar(20), @LevelUp int;
SET @EmployeeCode = 'N';
SET @LevelUp = 2;
*/
--用递归CTE实现员工树形关系表
WITH CTE AS(
    SELECT
        EmployeeCode,
        ReportToCode,
        ReportToDepth = 0,
        ReportToPath = CAST('/' + EmployeeCode + '/' AS varchar(200))
    FROM #Employees
    WHERE ReportToCode IS NULL
    UNION ALL
    SELECT
        e.EmployeeCode,
        e.ReportToCode,
        ReportToDepth = mgr.ReportToDepth + 1,
        ReportToPath = CAST(mgr.ReportToPath + e.EmployeeCode + '/' AS varchar(200))
    FROM #Employees e
    INNER JOIN CTE mgr
    ON e.ReportToCode = mgr.EmployeeCode
)
SELECT * FROM CTE ORDER BY ReportToPath

Answer 14

第二个题我就不说了，
第一个题，如果你做过简单的CRM的权限管理可能就知道了。
N01
N0101
N010101
N010102
N0102
N010201
N010202
N010203
N02
这样的话不就可以通过这个表的数据知道所在二叉树的位置了吗？看的明白吧

Answer 15

hao  gaoshen  a /////////

Answer 16

设计一张表来表示一个二叉树中的节点。通过表中的一条数据就能确定这个节点在二叉树中的位置。
这个题目,我有点搞不清楚,什么叫"确定节点在二叉树中的位置".树本来的结构就是无限制扩展的,位置是有一个倚赖关系的,必须通过其他的数据来寻求位置,何况,在一个动态的树里面标示一个节点的位置,除非对整个树在新数据进入的时候重新进行计算.
但是如果说如何表示一个节点就简单的多.我想或许出题的人是这个意思吧?
基于如上的推测,那么我的解决方式是:id,data,leftid,rightid.就怎么简单.....
如果出题的非要说是前者,那么本身树是一种2纬结构,任意一个节点都有纵横的坐标,就加个deepx,deepy.只不过在任意一个数据进入的时候,都要重新计算所有被影响的数据的坐标,这简直是种灾难.这样做不外乎反嘲笑下出题的人而已.设计一个公司的员工数据库，其中公司只有这一个，部门有好多，每个部门中有好多员工。其中员工可以新来和辞职。部门可以设立也可以新增，部门还可以设立子部门，员工可以属于父部门也可以属于子部门。我个人的理解吧,任意的实体都应该作为表结构的基础构件.那么,再分析部门和子部门,其实都是部门而已.
我个人看法结构或许如此:
部门表(加个字段表明上层部门)
员工表
员工部门关系表
不过这样的结构,如果要寻找一个属于多级嵌套的子部门员工归属的某层级的部门,会是种计算的灾难,尤其是涉及到统计数据的时候.如此的话,再加个深度吧,如果不是确定的对某个层级进行统计,那么对表进行拆分也没什么意义。

Answer 17

额..抱歉,没看你后面的东西.你说的10的标示码,是可以标示寻找树结构中数据的点的路径.只是理解不了这样做有什么意义.....除非是不经常变化的树结构,然后....这个码能做什么呢?都拿到了节点,何必再去关心寻找它的路径呢?难道是拿到之后,再去树里寻找一遍?或许是在寻找节点的前驱时候有一定的意义.但是如果数据经常这样使用,还不如另做一个数组结构重新存储一遍.这样虽然多维护个结构,但是,所有问题都简单了.额...对你的问题寻求现实case的求解.是什么样的环境才需要这样一个东西?没看到要用定位部门的东西.额....

Answer 18

顶下 学习思路~ 我最近做的是 菜单栏  也是这种情况  我设计的  ID  NAME  PID~~

Answer 19

看具体的应用场景了，是否是查询非常多，并且速度要求很快，也可以考虑采用左右值码的方式来快速定位，即：
id,pid,leftValue,rightValue
就如61楼说的一样。不过这种设计，维护leftValue,rightValue,在新增、修改和删除的时候，会增加较大的消耗。基本就是这样:
         root(0,3)
         |       |
    ------       -------
    |                   |
    A(1,2)              B(4,5)支持无限级的，查询速度绝对是非常快，维护的时候是硬伤。
在mysql官网上也能找到这种应用的设计示例。另外，还有一种有些人用到的是：路径码，搜一下应该有这种说明。

Answer 20

对于存储树，SQLServer2008有一个新的系统数据类型可以完美的支持：hierarchyid
hierarchyid 数据类型的值表示树层次结构中的位置
CREATE TABLE testTable(
[NodeID] [hierarchyid] NOT NULL,
[Level]  AS ([NodeID].[GetLevel]()),
[Path]  AS ([NodeID].[ToString]())
）
用这个方便多了

Answer 21

-- 1
CREATE TABLE BinTree(
[id] INT IDENTITY  PRIMARY KEY NOT NULL
,[pid] INT NOT NULL -- 父级id
,[date] VARCHAR(10) -- 数据
,[isLeft] BIT DEFAULT(1) -- 是否是左节点 否则右
)-- 确定位置
SELECT * FROM BinTree WHERE pid=0 --假设以0为起始
-- 2 
CREATE TABLE [Emplyee](
[eid] INT IDENTITY PRIMARY KEY NOT NULL
,[name] NVARCHAR(128)
-- ...
)
CREATE TABLE [Department](
[did] INT IDENTITY PRIMARY KEY 
,[pdid] INT
,[name] NVARCHAR(128)
-- ..
)CREATE TABLE [HR](
[hid] INT IDENTITY PRIMARY KEY
,[eid] INT 
,[did] INT
,[status] INT -- 当前状态 记录，入职，离职，在职等状态
)-- 上面人力资源的记录，表示哪一清
CREATE TABLE [HrItem](
[line] INT IDENTITY PRIMARY KEY
,[hid] INT
,[status] INT -- 状态 的记录
,[date] DATETIME
)-- 看看是否有差异，
-- 请高手指点

Answer 22

第二题可以建立
部门表      table department员工表      table employee
员工信息表  table employee_profile