“二叉树”？

Question

“二叉树”？
概念详解……

Answer 1

看个实例：应该属于BOM多级展开的范畴吧--建立測試環境
Create Table A
(IDInt,
 fatherIDInt,
 NameVarchar(10)
)
Insert A Select 1,        NULL,       'tt'
Union All Select 2,        1,          'aa'
Union All Select 3,        1,          'bb'
Union All Select 4,        2,          'cc'
Union All Select 5,        2,          'gg'
Union All Select 6,        4,          'yy'
Union All Select 7,        4,          'jj'
Union All Select 8,        7,           'll'
Union All Select 9,        NULL,  'uu'
Union All Select 10,       9,         'oo'
GO
--建立函數
Create Function GetChildren(@ID Int)
Returns @Tree Table (ID Int, fatherID Int, Name Varchar(10))
As
Begin
Insert @Tree Select ID, fatherID, Name From A Where fatherID = @ID
While @@Rowcount > 0
Insert @Tree Select A.ID, A.fatherID, A.Name From A A Inner Join @Tree B On A.fatherID = B.ID And A.ID Not In (Select ID From @Tree)
Return
End
GO
--測試
Select * From dbo.GetChildren(1)
GO
--刪除測試環境
Drop Table A
Drop Function GetChildren
--結果
/*
IDfatherIDName
21aa
31bb
42cc
52gg
64yy
74jj
87ll
*/

Answer 2

    二叉树的定义一根二叉树是节点的一个有限集合，该集合或者为空，或者是由一个根节点加上两根分别称为左子树和右子树的，互不相交的二叉树组成。2         树结构的基本术语 1)        结点：包括数据项及指向其他结点的分支。2)        结点的度(Degree) ：树中的一个结点拥有的子树数称为该结点的度(Degree)。 　Ø         一棵树的度是指该树中结点的最大度数。Ø         度为零的结点称为叶子(Leaf)或终端结点。 　度不为零的结点称分支结点或非终端结点。Ø         除根结点之外的分支结点统称为内部结点。Ø         根结点又称为开始结点。3)        孩子(Child)和双亲(Parents)：树中某个结点的子树之根称为该结点的孩子(Child)或儿子，相应地，该结点称为孩子的双亲(Parents)或父亲。同一个双亲的孩子称为兄弟(Sibling)。4)        祖先(Ancestor)：从根节点到该结点所经分支上的所有结点。5)        子孙(Descendant)：某一节点的子女，以及子女的子女都是该结点的子孙6)        结点的层数(Level)：结点的层数(Level)从根起算，根的层数为1，其余结点的层数等于其双亲结点的层数加1。7)        树的高度（Height）：树中结点的最大层数称为树的高度(Height)或深度(Depth)。8)        有序树(OrderedTree)和无序树(UnoderedTree)：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnoderedTree)。注意：若不特别指明，一般讨论的树都是有序树。9)        森林(Forest)：m(m≥0)棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。3        二叉树性质1)        二叉树第i层上的结点数目最多为2i-1(i≥1)。2)        深度为k的二叉树至多有2k-1个结点(k≥1)。3)        在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。4)        具有n个结点的完全二叉树的深度为：[log2(n+1)]-15.         两种特殊情形1)        满二叉树(FullBinaryTree) 一棵深度为k且有2k-1个结点的二又树称为满二叉树。Ø         每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。Ø         满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。2)        完全二叉树(Complete BinaryTree) 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。Ø         叶结点只在层次最大的两层出现。Ø         对任一节点，若其右子树的高度为L，那么左子树高度只能为L，或L+1。