二叉树(binary tree)是指度为2的有序树。
在二叉树中，每个结点的左子树的根结点被称为该结点的左孩子(left child)，右子树的根结点被称为该结点的右孩子(right child)。
图中A结点的左孩子为B结点，右孩子为C结点；B结点的左孩子为D结点，右孩子为空；C结点的左孩子为空，右孩子为E结点，E结点左孩子为F结点，右孩子为G结点。
二叉树的性质
-
- 二叉树上的终端结点数等于双分支结点数加1
- 二叉树上第i层上至多有2i-1个结点(i>=1）
- 深度为h的二叉树至多有2h-1个结点
- 对一棵二叉树中顺序编号为i的结点，若它存在左孩子，则左孩子结点的编号为2i；若它存在右孩子，则右孩子结点编号为2i+1；若它存在双亲结点（即编号不等于1），则双亲结点的编号为?i/2?。
- 具有n个结点的理想二叉树的深度为?log2(n+1)?或?log2n?+1
二叉树的五种基本型态
a：空树
b：只有一个节点
c：只在左孩子
d：只有右孩子
e：左右孩子都有
特殊二叉树：
- 斜二叉树(Skewed Binary Tree)
全部节点只有左孩子，或全部只有右孩子。实际上斜二叉树就是一个链表。
- 完美二叉树(Perfect Binary Tree)满二叉树(Full Binary Tree)
每个结点都有左右孩子。
- 完全二叉树(complete Binary Tree)
有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为i(i<=i<=n)结点与满二叉树中编号为i结点在二叉树中位置相同
上图满二叉树中删除编号后的结点就是这成完全二叉树，如删除结点，15，14，13。但不能只删除中间结点如：9，如要变成完全二叉树，9后面的节点要全部删除。
注：左子树也叫左孩子，右子树也叫右孩子。文中都是用左右孩子来描述，这样会更容易理解。