Atreeisa(possiblynon-linear)datastructuremadeupofnodesorverticesandedgeswithouthavinganycycle.Thetreewithnonodesiscalledthenulloremptytree.Atreethatisnotemptyconsistsofarootnodeandpotentiallymanylevelsofadditionalnodesthatformahierarchy.树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。
Asimpleunorderedtree;inthisdiagram,thenodelabeled7hastwochildren,labeled2and6,andoneparent,labeled2.Therootnode,atthetop,hasnoparent.上图是一棵无序的树示例。在上图中，标号为7的结点有两个孩子，分别是标号为2和6的结点。根结点，在最顶端，它没有双亲。1.2树的基本术语
2二叉树（BinaryTree)
2.1什么是二叉树（BinaryTree)
每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
2.2二叉树的性质
（1）若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个结点(i>=0)。
（2）高度为k的二叉树最多有2^(k+1)-1个结点(k>=-1)。(空树的高度为-1)
（3）对任何一棵二叉树，如果其叶子结点(度为0)数为m,度为2的结点数为n,则m=n+1。
2.3完美二叉树(PerfectBinaryTree)
APerfectBinaryTree(PBT)isatreewithallleafnodesatthesamedepth.Allinternalnodeshavedegree2.一个深度为k(>=-1)且有2^(k+1)-1个结点的二叉树称为完美二叉树。(注：国内的数据结构教材大多翻译为"满二叉树")
例如：
2.4完全二叉树(CompleteBinaryTree)
ACompleteBinaryTree（CBT)isabinarytreeinwhicheverylevel,exceptpossiblythelast,iscompletelyfilled,andallnodesareasfarleftaspossible.换句话说，完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
2.5完满二叉树(FullBinaryTree)
AFullBinaryTree(FBT)isatreeinwhicheverynodeotherthantheleaveshastwochildren.换句话说，所有非叶子结点的度都是2。（只要你有孩子，你就必然是有两个孩子。）
注：FullBinaryTree又叫做StrictlyBinaryTree。
2.6完美(Perfect)二叉树v.s.完全(Complete)二叉树
(1)一棵完美(Perfect)二叉树看起来是这个样儿的，【图2.6.1】
（2）那么，将编号为15,14,...,9的叶子结点从右到左依次拿掉或者拿掉部分，则是一棵完全(Complete)二叉树,
例如，将上图中的编号为15,14,13,12,11叶子结点都拿掉(从右到左的顺序)，【图2.6.2】
（3）下图就不是一棵完全(Complete)二叉树，【图2.6.3】，
如果将编号11(K)结点从编号6(E)的左儿子位置移动到编号5(E)的右儿子位置，则变成一棵完全(Complete)二叉树。
特别说明：其实，理解完全(Complete)二叉树可以借助于栈(stack)的思想。例如，把图2.6.1中的完美(Perfect)二叉树的所有结点按照编号1,2,3,...,15依次入栈(push)。那么，对栈的每一次出栈(pop)操作后，栈里保存的结点集对应到图2.6.1上去都是一棵完全(Complete)二叉树。
2.7完全(Complete)二叉树v.s.完满(Full)二叉树
2.8完满(Full)二叉树v.s.完全(Complete)二叉树v.s.完美(Perfect)二叉树
Everynodeexcepttheleafnodeshavetwochildrenandeverylevel(lastleveltoo)iscompletelyfilled.除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。