二叉树的定义
二叉树(Binary Tree)是n(n>=0)个结点的有限集合，该集合或者为空集，或者由一个根节点和两颗互不相交的，分别称为根节点的左子树和右子树的二叉树组成。
二叉树的特点
1.每个节点最多有两颗子树，所有二叉树中不存在度大二2的结点。
2.左子树和右子树是有顺序的，次序不能颠倒
3.即使树中只有一颗子树，也要区分它是左子树还是右子树。
特殊的二叉树
1.满二叉树：在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上
2.完全二叉树：对一颗具有n个结点的二叉树按层序编号，如果编号为i（1=<n<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树。
二叉树的性质
性质1：在二叉树的第i层上至多有2的(i-1)方个结点(i>=1)
性质2：深度为k的二叉树至多有2的k方再减去1个结点(k>=1)
性质3：对任何一颗二叉树T，如果其终端结点数为
n
0，
度为2的结点数为
n
2，
则
n
0=
n
2
+1。
性质4：具有n个结点的完全二叉树的深度为![]()
,(![]()
表示不大于x的最大整数)
性质5：如果对一颗有n个结点的完全二叉树的结点按层序编号(从第一层到第![]()
每层从左到右)，对任何一结点i(1=<i<=n)有：
(1)如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点![]()
。
(2)如果2i>n，则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i
(3)如果2i+1>n，则结点无右孩子；否则其右孩子是结点2i+1;
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
