Question

几种特殊的二叉树

Answer 1

1、满二叉树：对于h层的结点有2^h-1个结点。叶子结点都集中在最下面一层，除了叶子结点，每个结点都有左右孩子。

2、完全二叉树：对于一个高为h有n个结点的二叉树，当且仅当每一个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。叶子结点集中在最下面两层，并且如果一个节点的度为1，那么一定有左孩子。

3、二叉排序树：一棵二叉树或者空二叉树或者：左子树上的结点的关键字都小于根节点的关键字，右子树上的结点的关键字都大于根节点的关键字。

4、二叉平衡树：任意一个结点的左右子树的深度只差不超过1。

1、非空二叉树上叶子结点数等于度为2的节点数加1：N0 = N2+1

2、对于完全二叉树：

             n个结点从左到右，从上到下进行从1编号，那么当i>1时，i/2为结点i的根节点编号。

             结点i所在的层次为(log2,i)+1

             具有N个结点的完全二叉树，高度为(log2,N)+1