简述6种特殊二叉树

二叉树（Binary Tree)是n（n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。在二叉树中又有一些特殊的存在，各种有着基于二叉树特性之外的特点，我们称之为特殊二叉树。

为了更好的理解特殊二叉树，我们先来看看二叉树的特点：

（1）每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。

（2）左子树和右子树是由顺序的，次序不能颠倒。

（3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

我们结合着二叉树的一些特点来看看特殊二叉树。

1.斜树

所有结点都只有左子树的二叉树称之为左斜树，所有结点都只有右子树的二叉树称之为右斜树。

特点：

1）斜树每层只有一个结点

2）结点个数等于二叉树深度。

2.满二叉树

所有分支结点都存在左子树和右子树，且所有叶子都在同一层上的二叉树叫做满二叉树。

特点：

1) 叶子只出现在最下一层

2) 非叶子节点度一定为2

3) 同样深度二叉树中，满二叉树结点个数最多叶子树最多

4) 叶子结点数为2h

5) 第k层的结点数是：2k-1

3. 完全二叉树

对于具有n个结点的二叉树按层序编号，如果每个结点的编号与同样深度的满二叉树中对应编号的结点在二叉树中位置完全相同，则该二叉树称为完全二叉树。

特点：

1）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

2）叶子结点只出现在最下两层

3）最下层的叶子一定集中在左部连续位置

4）倒数二层若有叶子节点一定集中在右部连续位置如果结点度为1，则该结点只有左孩子

5）同样结点数的二叉树，完全二叉树的深度最小

4. 线索二叉树

二叉树的结点加上线索的二叉树叫做线索二叉树。

线索：指将二叉树中的空指针指向该节点的前驱或者后继

线索化：对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程

5. 霍夫曼树

霍夫曼树是指带权路径长度WPL最小的二叉树。

构建算法：

1）根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树的集合F={T1,T2,...,Tn},其中每棵二叉树Ti只有一个带权为wi根节点，左右子树均为空。

2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。

3）在F中删除这两棵树，同时将新得到的二叉树加入F中。

4）重复2和3步骤，直到F只含一棵树为止。得到的便是Huffman Tree

6. 二叉查找树（Binary Search Tree）又称二叉排序树（Binary Sort Tree）或二叉搜索树

二叉查找树是指一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

特点：

1）二叉排序树是为了提高查找和插入删除关键字的速度二叉排序树这样的非线性结构，也2）有利于插入和排序的实现。

3）二叉查找树的高度决定了二叉查找树的查找效率。

4）对二叉查找树进行中序遍历，即可得到有序的数列。

以上就是为大家简短介绍的6种特殊二叉树，特殊二叉树本质上还是二叉树，具有二叉树的一切特性，我们可以以二叉树为基点，慢慢去学习这些特殊二叉树。学好二叉树不是一朝一夕的事情，可以借助本站的数据结构和算法教程中的生动形象的二叉树图解来深入学习二叉树。