【数据结构】树

【数据结构】树

树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常见。树是以分支关系定义的层次结构。树的结构定义是一个递归的定义。

关于树的概念:

树的 结点 包含一个数据元素及若干指向其子树的分支。

结点拥有的子树数量成为结点的 

度为 0 的结点称为 叶子 或者 终端结点

度不为0的结点称为 非终端结点 或 分支结点,除根节点之外,分支结点也称为 内部结点

树的 度 是树内各节点的度的最大值。

树的 深度 是树中结点的最大层次,也称为树的 高度

有序树:如果将树中结点的各节点的子树看成从左至右是有次序的(即不能互换的),则称该树为有序树,否则是无序树。

森林:由m(m>=0)颗互不相交的树的集合。对树中的每一个节点而言,其子树的集合即为森林(即一棵树也是一个森林,它的子树都是这个森林的树)

二叉树

二叉树是另一种树型结构,它的特点是 每一个节点至多有两颗子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分(有序树)。

二叉树的性质:

性质1:在二叉树中,第 i 层的结点个数最多为 2^{i-1} 个结点(i>=1)。第 i 层的结点从 2^{i-1} 到 2^{i}-1 。 

性质2: 深度为 k 的二叉树至多有 2^{k}-1 个结点(k>=1)

性质3:对于任意一颗二叉树T,如果其终端结点数为 n_{0} ,度为2的结点数为 n_{2} ,则 n_{0} = n_{2} + 1 。

设 n1 为二叉树 T 中度为 1 的结点数,所以二叉树的结点的总个数为:n= n0 + n1 + n2 
再看二叉树的分支数,有多少个分支就有多少个结点(不包括根节点),所以:n= n1 + 2*n2+1
得: n0 + n1 + n2 = n1 + 2 * n2 + 1
得: n0 = n2 + 1

二叉树的种类

二叉树包括 完全二叉树  满二叉树 平衡二叉树  …..

满二叉树: 一颗深度为 k 且有 2^{k}-1 个结点的二叉树称为 满二叉树。这种树的特点就是 每一层的结点数都是最大数。

完全二叉树: 深度为 k , 有 n 个结点的二叉树,当且仅当 每一个结点都与深度为 k 的完全满二叉树的编号从 1 至 n 一一对应时,称为 完全二叉树。(满二叉树也是完全二叉树)

性质4 : 具有 n 个结点的完全二叉树的深度为 \log_{2} n + 1

      2^{k-1} - 1 < n <= 2^{k} -1     或   2^{k-1} <= n < 2^{k}

由于  k-1 < \log_{2}n < k ,因为 k 是整数,所以  k = \log_{2} n + 1  。

性质5: 完全二叉树的 i 结点的 父节点 为 i / 2 。 i 结点的左右节点为 (2* i)  和 (2 * i) + 1 。

遍历二叉树:

先序遍历: 根左右
中序遍历: 左根右
后序遍历: 左右根

遗留问题:

AVL树:平衡二叉树   平衡因子
B树:
红黑树:
赫夫曼树:

0 0 vote
Article Rating
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments