Question

二叉树的定义

Answer 1

二叉树（Binary Tree）是n（n>=0）个数据元素的有限集合，该集合可以为空（空二叉树），也可以由一个称为根（root）的元素及两个不相交的，被分别称为左子树和右子树的二叉树组成。

如下图中含有7个结点，其中A是根节点，左子树TL由{B，D，E}构成，右子树TR由{C，F，G}构成；而左子树TL中B是根结点，左子树是{D}，右子树是{E}。

右子树TR中，C是根结点，左子树为空，右子树为{F，G}；以此类推。由上述可以看出在二叉树中用到了递归的概念。即用二叉树来定义二叉树。

二叉树的性质

1、一颗非空二叉树的第i层上最多有2^（i-1）个结点（i>=1）。

2、一颗深度为k的二叉树中，最多有2^k-1个结点。

3、对于一颗非空二叉树，如果叶结点数为n0，度数为2的结点数为n2，则有n0=n2+1。

4、具有n个结点的完全二叉树的深度为 |lbn|+1。

5、对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中所有结点从1开始编号，则对于任意序号结点来说，有：

①如果i>1，则序号i的结点的双亲结点序号为i/2；如果i=1，则此时结点为根结点，无双亲结点。②如果2i<=n，则序号为i的结点的左孩子为2i；若2i>n，则序号为i的结点无左孩子。③如果2i+1<=n,则序号为i的结点的右孩子为2i+1；如果2i+1>n,则序号为i的结点无右孩子。