树

定义

（1）n > 0 时根结点是唯一的，不可能存在多个根结点。
（2）m >0 时，子树的个数吗没有限制，但他们一定是互不相交的。
森林
m棵互不相交数的集合
注：

树的抽象数据类型

树的存储结构
（1）双亲表示法

（2）孩子表示法
把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

（3）孩子兄弟表示法

二叉树

定义

是一棵或为空树，或树中每个结点的度数 <= 2有序树
特点
（1）每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
（2）左子树和右子树是有顺序的，次序不能任意颠倒。
（3）即使树中某结点只有一棵子树，也要区分它们是左子树还是右子树。

类型

满二叉树

定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

特点：
（1）叶子只能出现在最下一层，出现在其他层就不可能达成平衡。
（2）非叶子结点的度一定是2。
（3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

定义：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<i<n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这课二叉树称为完全二叉树。

特点
（1）叶子结点只能出现在下面两层
（2）最下层的叶子一定集中在左部连续位置
（3）倒数第二层，若有叶子结点，一定都在右部连续位置
（4）如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
（5）同样结点数的二叉树，完全二叉树的深度最小

性质

（1）在二叉树的第i层上至多有2^（i-1）个结点（i>=1）
（2）深度为k的二叉树至多有2^k-1个结点（k>=1）
（3）对任何一棵二叉树T，如果其终端结点数（叶子结点数）为n0，度为2的结点数为n2，则n0 = n2 + 1。
（4）具有n个结点的完全二叉树的深度为【log2n】+ 1
（5）如果对一棵有n个结点的完全二叉树（其深度为【log2n】+1）的结点按层编号（从第1层到第【log2n】+ 1层，每层从左到右），对任一结点i有：

存储结构

顺序存储
只用于二叉链表

二叉链表

遍历二叉树

定义

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

中序遍历

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

注：
已知前序遍历和中序遍历或已知中序遍历和后序遍历可以唯一确定一棵二叉树。

树转化为二叉树

森林转化为二叉树

赫夫曼树

定义：带权路径长度WPL最小的二叉树。
构造赫夫曼树

最后

以上就是怕孤独猎豹为你收集整理的6.树与二叉树树二叉树赫夫曼树的全部内容，希望文章能够帮你解决6.树与二叉树树二叉树赫夫曼树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。