关于数据结构中一些二叉树的定义

悠悠 2022-06-11 07:36 320阅读 0赞

**1、满二叉树**

定义：除最后一层的结点外，每一层的所有结点都有两个子结点。

另外一个定义：深度为k且有2^k-1个结点的二叉树。

满二叉树是一颗树深度为h，最大层数为k，且深度与最大层数相同，即k=h;

它的叶子数是： 2^(h-1)

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

总结点数是： 2^k-1 (2的k次方减一)

总节点数一定是奇数。

**2、完全二叉树**

![SouthEast][]

如上图，完全二叉树只比满二叉树少了最后几个结点，所以满二叉树是一种特殊的完全二叉树。

完全二叉树是效率很高的数据结构，堆是一种完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

**3、最优二叉树（哈夫曼树，Huffman树）**

首先，介绍树的带权路径长度， 树的带权路径长度为树中所有叶子结点的带权路径长度之和。带权路径长度最小的二叉树称作 最优二叉树或赫夫曼树。

注意：哈夫曼树不一定是完全二叉树！！

** 4、二叉排序树**

二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树，对于任意一个结点P而言： （1）若结点P的左子树不空，则左子树上所有结点的值均小于结点P的值； （2）若右子树不空，则右子树上所有结点的值均大于结点P的值； （3）结点P的左、右子树也分别为二叉排序树；

![20130910224413609][]

简单的准则：值的大小，左<根<右

**5、二叉判定树**

描述折半查找过程的二叉树为判定树。

判定树首先是一个二叉排序树，具有n个结点的判定树具有与具有n个结点的完全二叉树的深度完全相同，其深度为： ![20130910223909343][]。

![20130910224602265][]

在折半查找时，查找成功不成功，和给定值比较的次数最多为

![20130910223909343][]

**6、平衡二叉树**

平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

转载自：http://blog.csdn.net/hehainan\_86/article/details/11538383

[SouthEast]: /images/20220611/d8f40d642c3c43418f53d960d5204e6f.png
[20130910224413609]: /images/20220611/13142703b11542e7808daf7bb0153037.png
[20130910223909343]: /images/20220611/4aaa3e32b9f64d299592a9ed62c6a346.png
[20130910224602265]: /images/20220611/a7e2d2e511f04e3e9ec61572afd5b18f.png