二叉树的定义、性质和存储结构

算法与数据结构：二叉树 二叉树（Binary Tree）是一种重要的树型结构，它由n(n>=0)个结点的有限集合构成。此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树的每个结点最多只能有两个分支，度最大为2，左右子树有顺序，次序不能颠倒，可以有空的左子树或空的右子树。 二叉树有五种基本形态： 1. 空二叉树 2. 根和空的左右子树 3. 根和左子树 4. 根和右子树 5. 根和左右子树 对于三个节点的树，有五种形态对于三个节点的二叉树，有两种形态。 特殊的二叉树有三种： 1. 斜树：所有节点都只有左子树或右子树。左斜树：所有节点都只有左子树。右斜树：所有节点都只有右子树。 2. 满二叉树：所有分支结点都有左右子树，且所有叶子都在同一层的二叉树（深度为k，结点数为2k-1）。叶子只能出现在最下层，非叶子结点度=2。 3. 完全二叉树：对具有n个结点的二叉树按层序编号，若编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置相同，则为完全二叉树。叶子只能出现在最下面两层，倒数二层如有叶子结点，一定右部连续，度为1的结点只有左孩子。同样结点数的二叉树，完全二叉树的深度最小。 二叉树的性质： 1. 在二叉树的第i层上至多有2^(i-1)个结点。（i≥1） 2. 深度为k的二叉树上至多含2^k-1个结点。（k≥1） 3. 对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则n0=n2+1。 4. 具有n个结点的完全二叉树的深度为[log2(n+1)]。 5. 如果对一棵有n个结点的完全二叉树，结点按层序编号，则任一结点i（1<=i<=n)与其双亲及孩子结点的序号存在某种关系。 二叉树是一种重要的树型结构，它具有特殊性质，方便应用，任何树都可以转化成二叉树。