数据结构：树与二叉树_二叉树_定义

二叉树的定义

      二叉树(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;