二元树

　　一棵二元树是结点的一个有限集合，该集合或者为空，或者是由一个根结点和两课分别称为左子树和右子树的、互不相交的二元树组成。

 集合　　令N*是正整数的全体，且N_n={1，2，3，……，n},如果存在一个正整数n，使得集合A与N_n一一对应，那么A叫做有限集合。

　　空集也被认为是有限集合。

　　说明：很多资料里有限集合也被称为有限集。

　　集合(简称集）是把人们的直观的或思维中的某些确定的能够区分的对象放在一起，成为命题中的“这些”“那些”，作为考虑问题的整体。组成一集合的那些对象称为这一集合的元素(或简称为元)。现代数学还用“公理”来规定集合。

集合是现代数学中一个重要的基本概念。集合论的基本理论直到十九世纪末才被创立，现在已经是数学教育中一个普遍存在的部分，在小学时就开始学习了。这里对被数学家们称为“直观的”或“朴素的”集合论进行一个简短而基本的介绍；更详细的分析可见朴素集合论。对集合进行严格的公理推导可见公理化集合论。

　　外延公理

　　对于任意的集合A和B，A=B当且仅当对于任意的对象a，都有若a∈A，则a∈B；若a∈B，则a∈A。

　　无序对集合存在公理

　　对于任意的对象a与b，都存在一个集合A，使得A恰有两个元素，一个是对象a，一个是对象b。由外延公理，由它们组成的无序对集合是唯一的，记做{a，b}。由于a，b是任意两个对象，它们可以相等，也可以不相等。当a=b时，{a，b}，可以记做{a}或{b}，并且称之为单元集合。空集合存在公理：存在一个集合，它没有任何元素。^[1]

　　在数据结构中的树

　　树的定义

　　树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给出树的递归定义如下:

　　单个结点是一棵树，树根就是该结点本身。

　　设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称n1,n2,..,nk为结点n的子树。

　　空集合也是树，称为空树。空树中没有结点。

　　数学规律

　　h树连通无回路的无向图.

　　h树的判别图,T是树的充分必要条件是(六个等价定义)(定理14):

　　(1)T是无回路的连通图；(2)图T无回路且m＝n－1；

　　(3)图T连通且m＝n－1

　　(4)图T无回路，若增加一条边，就得到一条且仅一条回路；

　　(5)图T连通，若删去任一边，G则不连通；

　　(6)图T的每一对结点之间有一条且仅有一条通路.

　　h生成树图G的生成子图是树，该树就是生成树.

　　h权与带权图n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图.G的生成树T的所有边的权之和是生成树T的权，记作W(T).

　　h最小生成树带权最小的生成树.

　　h有向树有向图删去边的方向为树，该有向图就是有向树.

　　h根树与树根非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树.

　　h每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的根树为二元完全树(二叉完全树)；每个结点的出度等于2的根树称为正则二元树(正则二叉树).