二叉树(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后面的节点要全部删除。
注:左子树也叫左孩子,右子树也叫右孩子。文中都是用左右孩子来描述,这样会更容易理解。